Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
1. Сложение ассоциативно: для любых элементов а, Ь, с из G
(а+Ь)+с=а+ (Ь+с).
2. Существует такой нулевой элемент 0, что для любого элемента а из G
а+0=0+а=а.
3. Для каждого элемента а существует такой противоположный элемент (—а), что
а+ (—а)= (—о)+а=0.
Группа подстановок, определенная выше, является, как мы видим, одним из примеров группы. Вообще взаимно однозначные преобразования любого множества образуют группу относительно операции умножения преобразований (эти группы сыграли основную роль в формировании общего понятия группы).
Читатель обнаружит далее, что многие примеры групп ему уже известны. Перечислим некоторые из них:
*) В виде, близком к современному, определение группы было впервые сформулировано английским математиком A1 Кэли в 1854 году.1. Множество всех ненулевых действительных чисел относительно операции умножения — «мультипликативная группа действительных чисел» R*.
2. Множество всех целых чисел относительно операции сложения — «аддитивная группа целых] чисел»
3. Множество всех векторов в пространстве относительно операции сложения векторов.
4. Множество всех многочленов с действительными коэффициентами относительно операции сложения многочленов.
Группы в примерах 1—4 имеют бесконечно много элементов, а группа S — конечная (6 элементов). Число элементов конечной группы называется ее порядком.
Из аксиом группы можно вывести, что в группе существует только один единичный элемент. Можно доказать также и единственность обратного элемента для всякого элемента группы.
Пример группы подстановок показывает, что умножение в группе может быть некоммутативным. Те группы, для которых операция коммутативна, так и называются коммутативными (примеры 1—4).
Если некоторое подмножество H группы G само образует группу относительно операции, определенной в G, то подмножество H называют подгруппой группы С.
Например, подмножества II1= (O1-, сг2} и H2= Io1, сг4, оГ)} группы S являются подгруппами этой группы. Подмножество четных целых чисел есть подгруппа аддитивной группы 2 всех целых чисел, а подмножество нечетных чисел не будет подгруппой этой группы (сложение на 2 не задает операцию на этом подмножестве, так как сумма двух нечетных чисел есть число четное).
Имеет место следующая теорема.
Для того чтобы подмножество H являлось подгруппой группы G, необходимо и достаточно, чтобы выполнялись два условия:
1) произведение любых элементов Ii1, h2 из подмножества H такоке является элементом из H (Zi1Zi2 ? H);
2) если h ? II, то и обратный к нему элемент принадлежит Il (H-1^H).
Наиболее просты так называемые циклические подгруппы, которыми обладает любая группа С. Со всяким элементом g?G можно связать «порожденную» им циклическую подгруппу, которая, по существу,^ представляет собой наименьшую из подгрупп, содержащую данный элемент. Чтобы определить ее, введем понятие степени элемента g, полагая g°=e и для любого натурального k
gA = gg---g, g-ft = (gft)-1. к сомножителей
При таком определении степени выполняются хорошо знакомые
,123нам правила действий со степенями: для любых целых чисел тип gmgn=gm+n, (gm)n=gmn.
Ясно, что всякая подгруппа, содержащая элемент g, должна содержать люСые его степени. С другой стороны, уже само множество степеней образует, как нетрудно убедиться, группу.
Указанную группу называют циклической подгруппой, порожденной элементом g; ее обозначают символом (g), а сам элемент g называется образующим элементом этой группы.
Может случиться, что для некоторого элемента g циклическая подгруппа (g) совпадает со всей группой G, и тогда группа G также называется циклической. Например, аддитивная группа целых чисел есть циклическая группа с образующим элементом 1 (или —1), а ее подгруппа четных чисел — циклическая с образующим элементом 2. Являясь наиболее простыми, циклические группы служат важным инструментом для изучения групп, имеющих более сложное строение.
Между группой и любой ее подгруппой существует определенная связь, которую можно охарактеризовать с помощью понятия смежного класса по подгруппе.
Пусть H — подгруппа группы G и g?G — произвольный элемент группы G (мы не требуем, чтобы он обязательно принадлежал подгруппе). Множество всевозможных произведений ghj где h — любой элемент подгруппы H-, называется смежным классом (точнее, левым смежным классом) по подгруппе Н, а элемент g — с-го представителем. Обозначая левый смежный класс через gH, имеем, следовательно,
gH=[eh\h?H).
Аналогично определяются правые смежные классы Hg. Если группа G — коммутативная, то Hg=gH.
Для смежных классов, безразлично, левых или правых, справедливы два основных факта.
1. В случае конечной подгруппы H число элементов в любом смежном классе одно и то же и совпадает с порядком подгруппы.
2. Любые два смежных класса ^1W и g2H либо совпадают, либо вовсе не имеют общих элементов.
Для иллюстрации понятия смежного класса рассмотрим следующий пример. Пусть 2 — аддитивная группа целых чисел, а Я — ее подгруппа, состоящая из чисел, кратных пяти. Тогда можно «выписать» следующие смежные классы: