§ 4. ГРУППА ПЕРЕСТАНОВОК И ПОЛУГРУППА ПРЕОБРАЗОВАНИЙ

Как было установлено, операция умножения преобразований произвольного множества М имеет ряд свойств, которые не зависят от природы элементов множества М. Эти свойства могут быть разными для разных совокупностей преобразований множества М. Например, в множестве всех преобразований не для каждого преобразования существует обратное, а в множестве биективных преобразований это имеет место.

Операция умножения произвольных преобразований некоммутативна, а операция умножения (последовательного выполнения) параллельных переносов на плоскости коммутативна. Изучать свойства отдельных классов преобразований относительно операции умножения бывает нужно очень часто. А потому удобно разработать определенную общую схему изучения таких свойств.

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

Это наводит на мысль рассмотреть общее понятие операции. Из приведенных примеров видно, что операция, заданная на некотором множестве D, произвольной паре элементов из D ставит в соответствие определенный элемент из D (результат применения операции). Например, операция сложения целых чисел паре (2, 3) ставит в соответствие число 5, а паре (-2, 1) — число —1; операция умножения перестановок на множестве {1, 2, 3} паре перестановок

ставит в соответствие перестановку

Следовательно, естественно дать такое определение:

Операцией на множестве D называется соответствие, при котором с каждой парой элементов из D сопоставлен определенный элемент этого же множества.

Операции обозначают разными символами, например и т. д. Если операция на множестве D обозначена символом и паре (а, b) элементов из D она ставит в соответствие элемент с, то коротко это записывают так:

Элемент с называют композицией или, чаще, произведением элементов а, b, а операцию в этом случае называют умножением (это оправдано тем, что очень часто операцию понимают как умножение перестановок).

Примерами множеств с операциями являются множество целых чисел с операцией сложения, множество параллельных переносов на плоскости с операцией их последовательного выполнения, множество положительных действительных чисел с операцией возведения в степепь (паре положительных чисел ) ставится в соответствие число множество перестановок первых 100 натуральных чисел с операцией умножения перестановок.

Рассматриваются множества с операциями, которые имеют определенные свойства. Из сказанного в предыдущем параграфе вытекает, что естественно выделять два совокупности преобразований — множество Есех преобразований и множество перестановок. Запишем отдельно свойства операции умножения произвольных преобразований и свойства операции умножения перестановок на множестве М. Будем обозначать совокупность всех преобразований множества М символом , а совокупность всех перестановок на этом множестве — символом

А. Свойства операции умножения преобразований из Р(М).

. Произведение двух преобразований множества М — тоже преобразование этого множества:

Иными словами, множество Р(М) замкнуто относительно операции умножения преобразований.

. Операция умножения преобразований имеет свойство ассоциативностиу т. е. для каждых справедливо равенство

Существует единственное преобразование такое, что для каждого

Б. Свойства операции умножения перестановок из

Если , то

Операция умножения перестановок ассоциативна.

Существует единственная перестановка такая, что для каждой перестановки имеем

Для каждой перестановки существует такая перестановка , что

Общая схема, по которой изучаются совокупности преобразований с операциями умножения, должна как-то учитывать серию свойств А или серию свойств Б. Это достигается введением общих понятий группы и полугруппы.

Определение. Произвольное множество D с заданной на нем операцией называется полугруппой, если:

а) для каждых произведение принадлежит

б) для каждых трех элементов выполняется равенство

т. е. операция умножения, заданная на D, ассоциативна;

в) существует такой элемент что для каждого имеем

Элемент называется нейтральным для операции

Ч Примеры. 1. Множество Z всех целых чисел для сложения — полугруппа.

Действительно, сумма целых чисел — снова целое число. Операция сложения целых чисел имеет ассоциативное свойство. Нейтральным элементом для операции сложения целых чисел служит число 0, потому что для каждого имеем

2. Множество всех положительных рациональных чисел для операции умножения — полугруппа.

3. Множество преобразований для операции последовательного выполнения преобразований — полугруппа.

Множество положительных действительных чисел с заданной на нем операцией не будет полугруппой, так как эта операция не ассоциативна, т. е. для чисел из не всегда выполняется равенство (1). Например,

(потому что )

Определение. Множество D с заданной на операцией называется группой, если удовлетворяются требования а) — в) определения полугруппы и, кроме того, такое требование:

г) для каждого элемента существует такой элемент , что

Примеры. 4. Множество Z всех целых чисел для операции сложения — группа.

Действительно, в примере 1 было проверено выполнение требований а) — в). Кроме того, для каждого числа существует такое число (противоположное к а), что а Следовательно, выполняется и последнее требование определения группы.

5. Множество положительных действительных чисел для операции умножения — группа.

Действительно, произведение положительных чисел — снова положительное число; операция умножения чисел ассоциативна; нейтральным элементом является число 1; для каждого числа существует обратное к нему

6. Множество всех поворотов плоскости вокруг фиксированной точки на произвольные углы для операции последовательного выполнения поворотов — группа.

Действительно, произведение поворотов плоскости вокруг точки- О на углы является поворотом вокруг этой точки или на угол р, или на угол операция умножения поворотов ассоциативна, так как таковой является операция умножения произвольных преобразований; нейтральный элемент — тождественное преобразование плоскости, которое можно рассматривать как поворот вокруг точки О на 0 радианов; обратным к повороту на угол а будет поворот на угол — а.

Совокупность всех перестановок на множестве М = {1, 2, 3, ..., n} для операции умножения перестановок образует группу Эта группа называется симметрической группой перестановок на множестве М. Выполнение всех требований определения группы вытекает из свойств

Каждая группа будет также и полугруппой, но не наоборот. Например, множество целых неотрицательных чисел для действия сложения — полугруппа, но не группа.

Операции сложения и умножения чисел имеют свойство коммутативности. Однако требование коммутативности не включено в определение полугруппы и группы. Это объясняется тем, что операция умножения преобразований не коммутативна, а исторически понятие группы возникло именно на основе изучёния свойств операции умножения перестановок на конечных множествах (понятие полугруппы появилось значительно позднее). Отдельно рассматриваются группы, для которых выполняется требование коммутативности. Они называются абелевыми (в честь норвежского математика Н. Г. Абеля (1802—1829), установившего роль таких групп в теории разрешимости алгебраических уравнений в радикалах).

Для множеств с заданными на них операциями проверять выполнение свойств группы бывает довольно трудно. Если множество конечно, для такой проверки можно воспользоваться так называемой таблицей умножения группы. Эту таблицу составляют подобно таблице умножения целых чисел. Строят ее так. Пусть

— все элементы группы G. Запишем их в первом ряду и в первом столбце подготовленной таблицы.

Затем заполним клетки таблицы, записывая в них произведения соответствующих элементов первого ряда и первого столбца в указанном порядке. В результате получим

Примеры. 7. Пусть G — множество перестановок

Непосредственно перемножая их, легко убеждаемся, что таблица умножения элементов из G будет такая:

8. Пусть Н — множество преобразований

Перемножая эти преобразования получим такую таблицу:

Пользуясь двумя последними таблицами, легко убедиться, что множества G и Н для операции умножения преобразований образуют соответственно группу и полугруппу. Убедимся, например, что G — группа. Поскольку все клетки первой из отмеченных таблиц заполнены только символами множество G замкнуто относительно умножения заданных перестановок. Условие ассоциативности для умножения элементов из G выполняется автоматически, потому что оно выполняется для умножения произвольных преобразований. Перестановка является нейтральным элементом группы. Из таблицы также видно, что каждый из элементов имеет обратный, а именно

Упражнения

1. Образуют ли полугруппы такие множества с заданными на них операциями:

а) множество натуральных чисел с операцией, которая каждой паре чисел ставит в соответствие их наибольший общий делитель;

б) множество всех многочленов произвольной ненулевой степени для суперпозиции многочленов;

в) множество нечетных целых чисел для операции умножения?

2. Являются ли группами такие множества с заданными на них операциями:

а) множество действительных чисел для операции умножения;

б) совокупность функций определенных на множестве действительных чисел без нуля, для суперпозиции функций;

в) множество функций для суперпозиции функций;

г) множества с операциями из упражнения 1?

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

4. Какое свойство таблиц умножения абелевой группы не имеет места для таблиц умножения неабелевых групп?

5. Составить таблицу умножения:

а) для группы где

б) для группы из упражнения 2, б);

в) для полугруппы Р(М), где

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