Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
Мы обнаруживаем, далее, что используя операции сложения и умножения чисел, можно производить аналогичные операции и над классами вычетов.
В самом деле, пусть г(иг; — два класса вычетов. Выберем любые два числа из этих классов: а^г-^, а2?г2. Пусть оказалось, что сумма o1-I-o2 имеет вычет г, а произведение O1O2 — вычет s:
ai + a2?r, O1O2^s.
Тогда будем считать, что «сумма» классов г\ и г2 равна г, а их «произведение» равно s:
ri + r2 = r, n-r2 = s.
Законность этого определения обосновывается тем, что класс, которому принадлежит сумма ai+a2 (соответственно произведение аха2) не зависит от выбора элементов of и а2 в -классах гі и г2.
Поясним данное определение на примере, взяв за модуль сравнения число п= 2. В этом случае имеем два класса вычетов — О и 1, а операции над ними выглядят так:
0 + 0=0; ЇЇ+!=!+0=7; 7+7 = 0; О • (T= (Т; О. 7=7 • 0 = 0; 7 ¦ 7=7.
Часто, когда это не вызывает путаницы, в обозначениях классов вычетов опускают черту, записывая их как обычные натуральные числа. В основном тексте книги это делается без специальных оговорок. Выпишем, например, таблиц« сложения и умножения классов по
,119 модулю 4 в этих упрощенных обозначениях:
+ 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2
• 0 1 2 3
0 0 0 0 0
1 0 1 2 3
2 0 2 0 2
3 0 3 2 1
Эти таблицы можно понимать и буквально, считая, что они определяют две операции нл множестве {0, 1, 2, 3} — сложение и умножение по модулю А.
2. Группы
Прежде чем дать определение группы, рассмотрим один
важный пример.
Будем исходить из понятия взаимно однозначного отображения множества на себя. В случае конечного множества такое отображение называют обычно подстановкой. Пусть множество M состоит из чисел 1, 2, 3: /VJ= {1, 2, 3}. Чтобы задать какую-либо подстановку множества М, достаточно указать для каждого из чисел 1, 2, 3 то число, в которое оно отображается этой подстановкой. Удобнее всего сделать это, использовав таблицу из двух строк,— в первой строке выписываются (в любом порядке) числа 1, 2, 3, а во второй под каждым из них пишется соответствующее ему при данной подстановке число. Скажем, обе таблицы
/1 2 3\ (2 3 П \2 3 1 / ' (,З 1 2)
задают одну и ту же подстановку: число 1 переходит в число 2, 2— в 3, 3 — в 1. Нетрудно указать все различные подстановки множества ЛІ; их будет шесть:
°1 = (! 2 з) ' 0,= (І З I) ' °3=G 1 з) '
n /1 2 3\ „ (1 2 3\ (\ 2 3\
°'=42 3 \)> 1 2j 1 0^3 2 lj-
,120 Определим теперь на множестве S= {о?, а2, . . a?) всех подстановок операцию умножения (или композицию) подстановок. Именно, произведением подстановок а; и Oy будем называть подстановку ofc, получающуюся в результате последовательного выполнения сначала подстановки а/, а затем Oj (записывается: OiOy=Ofc). Например,
(\ 2 3\ /1 2 3\_/1 2 3\
U 1 2) Vl 3 2) U 1 З)
(первая подстановка переводит число 1 в число 3, после чего вторая подстановка переводит число 2 в число 3, так что в результате последовательного выполнения подстановок число 1 перейдет в число 2 и т, д.). Читатель может проверить, что
/I 2 3\ /1 2 3\_/1 2 3\
Vl 3 2J V3 1 2) V3 2 IJ'
и тем самым убедиться, что произведение двух подстановок зависит, вообще говоря, от порядка сомножителей.
Множество S с определенной выше операцией умножения называют группой подстановок множества M.
Операция умножения на S обладает следующими свойствами. Во-первых, эта операция ассоциативна: для любых -Oi-, Oy, ай
(OiOy) Ofc=O,- (OyOfc).
Во-вторых, тождественная подстановка
1 2 3>
< 2 3
переводящая каждый элемент в себя, играет роль единицы в обычном умножении, а именно, для любой подстановки о,-
o1Oi- = O1O1 = О/.
Наконец, вместе с каждой подстановкой О; множество S содержит обратную ей подстановку Oy, которая переводит число а в число b тогда и только тогда, когда о,- переводит число b в число а. При этом, понятно, каждое из произведений а,Оу и OyO1- будет тождественной подстановкой
OiOy = OyOi = O1.
Эти три свойства сохранятся, если распространить определение умножения подстановок множества {1, 2, 3} на случай подстановок любого конечного множества.
Более того, выяснилось, что имеются самые разнообразные системы объектов с операцией, обладающей указанными свойствами.
,121 Это привело к следующему (общему) определению группы *).
< Множество G, на котором определено умножение элементов, называется группой, если выполняются три аксиомы:
1. Умножение ассоциативно: для любых элементов а, Ь> с из О
a (be)= (ab)c.
2. В множестве G существует такой единичный элемент е, что
еа=ае=а.
3. Для каждого элемента а множества G существует в G такой обратный элемент а'1, что
аа~1 = а~1а = е.
Обращаем внимание читателя на то, что в приведенном определении говорится об умножении элементов и используется связанная с обычным умножением терминология и символика. Этой «мультипликативной» терминологии мы и будем в дальнейшем придерживаться. Однако термин «умножение» нельзя понимать буквально; речь идет о любой операции, удовлетворяющей данным аксиомам. В частности, в ряде случаев естественнее называть операцию сложением и соответственно переформулировать аксиомы группы, пользуясь терминологией, связанной со сложением («аддитивной» терминологией):
