Дискретно-непрерывная математика (стр. 30 )

Перемножим, например, подстановки

и

В силу первой подстановки единица заменится двойкой, в силу второй подстановки эта двойка останется на месте; итак, после последовательного осуществления обеих подстановок единица перейдет в двойку. Точно так же после последовательного осуществления обеих подстановок двойка перейдет в тройку, тройка перейдет в единицу:

•= (2.11)

Таким же точно образом можно перемножить любые две подстановки. Для того чтобы удобно записать результаты всех этих перемножений, введем следующие обозначения:

Р0= , Р1= , Р2= ,

Р3= , Р4= , Р5= ,

Р0 — тождественная подстановка.

Тогда имеем следующую таблицу умножения:

Таблица 2.4

Для того чтобы найти произведение двух подстановок, например,

P2•P4, необходимо взять строку, в заголовке которой («первый сомножитель») стоит первая подстановка (в нашем случае Р2), и столбец, в заголовке которого («второй сомножитель») стоит вторая подстановка (в нашем случае Р4). В пересечении выбранной строки с выбранным столбцом и будет стоять искомое произведение: P2• P4 = P1.

Проведем вычисление в развернутом виде; пусть

P2= , P4= ;

с помощью тех же соображений, что и в случае равенства (2.11), получаем

• =

т. е. действительно:

P2• P4 = P1.

Непосредственной проверкой можно убедиться в том, что наше умножение удовлетворяет ассоциативному закону.

Тождественная подстановка Р0 есть единственная подстановка, которая удовлетворяет условию

P0• Pі =Pі• P0 = Pі

для любой подстановки Рі.

Наконец, к каждой подстановке есть обратная к ней, которая дает в произведении с данной тождественную подстановку: обратная подстановка к данной ставит все числа, смещенные подстановкой, на их прежние места. Так, например,

= .

Чтобы в таблице умножения найти сразу подстановку, обратную к данной подстановке, надо в строке, отмеченной слева данной подстановкой, найти элемент Р0; в заголовке столбца, в котором лежит этот элемент, и стоит подстановка, обратная данной. Имеем, как легко видеть:

P-10= Р0 , Рз-1 = Р3,

P-11 = P1, P4-1=P4,

Р-12=Р2, Р5-1= Р5.

Итак, умножение подстановок удовлетворяет всем групповым аксиомам и, следовательно, совокупность всех подстановок из трех элементов есть группа. Мы обозначим эту группу через S3. Группа S3 конечна, ее порядок равен 6.

Заметим, что умножение подстановок, вообще говоря, не обладает свойством переместительности (коммутативности): произведение двух подстановок зависит, в общем случае, от порядка множителей. Так, мы имеем, например,

P2• P3 =P5, P3• P2 =P1.

Подгруппы. Возникает вопрос: нельзя ли получить группу, взяв не все, а только некоторые из числа наших подстановок (из трех чисел) и сохранив для них тот же закон умножения? Нетрудно убедиться, что ответ на этот вопрос утвердительная.

В самом деле, рассмотрим, например, пары элементов Р0 и Р1. Наша таблица умножения дает нам непосредственно:

P0• Г0=Р0, Р0• P1=Р1, P1• P0 = P1, P1• P1=P0.

Мы видим, что все групповые аксиомы выполнены (в частности, P-10 = Р0 и P-11=Р1), значит, два элемента Р0 и Р1 образуют группу, которая составляет часть группы всех подстановок из трех чисел.

Точно так же можно убедиться, что пары элементов Р0 и Р2 в свою очередь образуют группу, как и пары Р0 и Р5.

Что же касается пары Р0 и P3 (и также пары Р0 и Р4), то она группы не образует, так как Р3• Р3= Р4 (т. е. произведение элемента Р3 с самим собой не есть элемент нашей пары). Эти простые соображения оправдывают введение следующего общего определения.

Определение. Пусть задана какая-нибудь группа G; тогда, если множество Н, которое состоит из некоторых элементов группы G, образует (при законе умножения, заданном в G) группу, то такая группа Н называется подгруппой группы G.

Таким образом, пары элементов (Р0, P1), (Р0, Р2), (Р0, Р5), каждая, являются подгруппами порядка 2 группы S3. Других подгрупп порядка 2 группа S3 не имеет: из определения подгруппы следует, что всякая подгруппа Н группы G содержит нейтральный элемент группы G, значит, всякая подгруппа порядка 2 группы S3 имеет вид (Р0, Рі), где і - одно из чисел 1, 2, 3, 4, 5; но мы видели, что i не может равняться ни 3, ни 4, значит, остаются только рассмотренные подгруппы

(Р0, P1), (Р0, Р2), (Р0, Р5).

В группе S3 есть также подгруппа, которая состоит из трех элементов (подгруппа порядка 3). Это будет подгруппа (Р0, P3, P4). Читателю предлагается самому убедиться, что эта подгруппа есть единственная подгруппа порядка 3, которая содержится в S3. Подгрупп порядка 4 и 5 в группе S3 не имеется вовсе.

Замечание. В том что подгрупп порядка 4 и 5 в группе S3 не имеется вовсе, можно убедиться, разобрав все 10 подмножеств группы S3, которые содержат элемент Р0 и состоят из четырех элементов, а также все 5 подмножеств, которые содержат 5 элементов, включая непременно Р0. Однако отсутствие подгрупп порядка 4 и 5 в группе вытекает непосредственно из следующей общей теоремы, которую будет доказано позже: порядок всякой подгруппы Н конечной группы G есть делитель порядка G.

Итак, подгруппы порядка S3 суть: три подгруппы порядка 2, а именно: (Р0, Р1), (Р0, Р2), (Р0, Р5), одна подгруппа порядка 3, а именно: (Р0, Р3, Р4).

Таким же образом, как мы изучили группу S3, можно было бы изучить группу S4, состоящую из всех подстановок из четырех чисел.

Группа S 4 имеет порядок 1 • 2 • 3• 4 = 24.

Да и вообще, при любом п подстановки из п чисел образуют группу Sn порядка 1• 2• 3• .. . •п=п!

Закон умножения во всех этих группах тот самый: умножить две подстановки из п чисел, означает, последовательно сделать эти подстановки одну за другой.

Отметим, наконец, что группа Sn всех подстановок из п элементов называется симметрической группой (подстановок из п элементов).

Любая подгруппа группы Sn называется группой подстановок из п элементов.

Для того, чтобы подмножество группы было подгруппой необходимо выполнить ряд условий.

При доказательстве того, что некоторое подмножество Н группы G является подгруппой, удобнее всего бывает пользоваться следующей общей теоремой:

Подмножество Н группы G тогда и только тогда является подгруппой группы G, когда выполнены следующие условия:

1. Произведение двух элементов а и b из Н (в смысле умножения, определенного в G) есть элемент множества Н.

2. Нейтральный элемент группы G есть элемент множества Н.

3. Элемент, обратный к какого-нибудь элементу множества Н, есть элемент множества Н.

Для доказательства достаточно заметить, что наши условия выражают в точности требования, чтобы операция умножения, которая определена в G, но применяемая лишь к элементам множества Н, удовлетворяла всем аксиомам группы (ассоциативности требовать не нужно: будучи выполнена при умножении любых элементов множества G, она тем более выполнена в частном случае, когда эти элементы являются элементами множества Н).

Подстановки как отображения. Мы изложили понятие подстановки тем элементарным и несколько кустарным способом, каким это обычно и делается. Если не бояться общематематических терминов, то подстановку из п элементов следует определить просто как взаимно однозначное отображение f множества данных п элементов на себя.

Если наши элементы суть числа 1, 2, 3,... ... , п, тo подстановка

задается как функция

ak = f(k), k=1, 2, ... , п,

причем и значения аргумента и значения функции суть числа 1, 2, 3, .... п.

Для двух данных значений аргумента значения функции всегда различны.

В частности, подстановка целиком определена, если для каждого k указано значение f(k), т. е. ak.