Если множество A конечно, алгебраическую операцию на этом множестве можно определить в виде таблицы. Если операция бинарная, то такое определение особенно удобно.
Пример 1 (таблица операции).
Составим таблицу операции (+ mod 5) на множестве
{0, 1, 2, 3, 4}
| (+ mod 5) | |||||
Кроме того, что таблица даёт определение операции, она наглядно выражает некоторые свойства операции. В частности, коммутативность операции соответствует симметричности таблицы относительно главной диагонали.
Определение 3 (Алгебраическая система). Алгебраической системой <A; W F; W R> называется объект, состоящий из трёх множеств: непустого множества A, множества алгебраических операций W F, определёных на A, и множества отношений W R, определёных на A. Множество A называется носителем алгебраической системы. Если алгебраическая система не содержит операций, она называется моделью, если не содержит отношений, то – алгеброй.
Символы алгебраических операций и отношений (каждый из которых имеет определённую арность) составляют сигнатуру алгебраической системы.
Мы будем иметь дело с алгебраическими системами, содержащими конечное число операций и отношений. Алгебраические системы мы будем записывать в виде: <A;f 1 ,...,fk;r 1 ,...,rl>, где { f 1 ,...,fk } = W F, { r 1 ,...,rl } = W R.
Определение 4 (Тип алгебраической системы). Типом алгебраической системы <A;f 1 ,...,fk;r 1 ,...,rl> называется пара наборов (n (f 1) ,...,n (fk)) и (n (r 1) ,...,n (rl)), состоящих из арностей операций и отношений. Тип будем записывать в виде <n (f 1) ,...,n (fk); n (r 1) ,...,n (rl)>.
Пример 2 (алгебраическая система).
< N ;+,·;<> является алгебраической системой типа <2, 2; 2>, так как операции +,· определены для любых двух натуральных чисел и результат снова является натуральным числом. < N ;+,-;<> не является алгебраической системой, так как результат операции -, применённой к натуральным числам – не всегда натуральное число.
Группой называется множество G, на котором
определена ассоциативная бинарная операция ◦,
содержащее элемент е такой, что для любого элемента
a∈G выполняется
e ◦ а = а ◦ е = а,
и существует элемент a– 1 такой, что
а ◦ a– 1
= a– 1◦ а =e.
Указанный элемент е называется единицей группы.
Элемент a– 1 называется обратным к элементу а. Легко
показать, что единица группы единственна и что
элемент, обратный к данному элементу, также
определяется однозначно. Если операция ◦
коммутативна, то группа называется коммутативной,
или абелевой.
Заметим, что не все коммутативные
операции ассоциативны. Например, если в
качестве операции ◦ использовать среднее
арифметическое двух вещественных чисел, то эта
коммутативная операция не ассоциативна.
Действительно:
(a◦a)◦b = a◦b = (a+b)/2,
a◦(a◦b) = a◦((a+b)/2) = (3a+b)/4. Примерами абелевых групп являются:
• множества Z целых, Q рациональных, R
действительных и С комплексных чисел с
соответствующими операциями сложения;
• множества Q\{0}, R\{0} и С\{0} отличных от нуля
рациональных, действительных и комплексных
чисел с соответствующими операциями умножения.
В теории групп используется две равноправных и
эквивалентных друг другу терминологических системы:
аддитивная и мультипликативная. В аддитивной
системе групповую операцию называют операцией
сложения, а группы в аддитивной записи для краткости
иногда будем назвать аддитивными. Группы,
операцию в которых называют умножением, иногда
именуются мультипликативными группами.
Операцию аддитивной группы принято обозначать
знаком +, операцию мультипликативной группы
обозначают знаком умножения x, или • (или ее
обозначение, по умолчанию, опускают).
Единичный элемент аддитивной группы
обозначается 0 и называется нулем. Элемент
аддитивной группы, обратный к элементу а,
обозначается
– а и называется противоположным к этому
элементу. Единичный элемент мультипликативной
группы обозначается 1 и называется единицей. А
элемент обратный к a обозначается через а– 1
.
Ассоциативность операции ◦ позволяет записывать
кратное произведение
(· · ·((а ◦ а) ◦ а) ◦· · ·а) ◦ а,
опуская скобки
а ◦ а ◦ а ◦… ◦а.
Такая формула называется k-ой степенью
элемента а. В аддитивных группах k-я степень элементаа обозначается k · a, в мультипликативных группах
используется обозначение аk
. По определению,
0 · a = 0 и a (0)
= 1.
В аддитивной группе определяется операция
вычитания a – b по следующей формуле
a – b= а + (–b)
Результат a – b называется разностью элементов а и
b.
В мультипликативной группе определяется
операция деления a/b по следующей формуле
a/b = а · b- 1
.
Результат а/b, или называется частным от деления
элемента a на элемент b.
Кольцом называется множество R с операциями
сложения и умножения такими, что R является абелевой
группой относительно сложения и умножения
ассоциативна и дистрибутивна относительно операции
сложения:
(а · b) · с = a · (b · с),
a · (b + c)=a · b + a · c,
(b + c) · a = b · a + c · a.
Следствием определения кольца является свойство –
для любого а
а · 0 = 0 · а = 0.
Примерами колец служат множества Z целых, Q
рациональных и R действительных чисел с операциями
сложения и умножения. Кольцо, в котором из уравнения
a Ч b = 0 следует, что а = 0 или b = 0, называется
областью целостности. Если в кольце имеетсямультипликативная единица, то кольцо называется
кольцом с единицей. Ниже рассматриваются
только кольца с единицей.
Элемент а' кольца с единицей такой, что а · а' = 1,
называется обратным к элементу a. Элемент,
обратный к элементу а кольца обозначается а- 1
. Каждый
элемент кольца имеет не более одного обратного к нему
элемента. Элемента, обратного к нулевому элементу
кольца, не существует. Множество элементов кольца,
имеющих обратный элемент, составляет
мультипликативную группу кольца R, которая
обозначается R*.
Полем называется кольцо F с единицей,
множество ненулевых элементов которого с операцией
умножения является абелевой группой. Эта группа
называется мультипликативной группой поля.
Примерами бесконечных полей являются поля Q
рациональных, R действительных и С комплексных
чисел.
Подмножество F поля Q, замкнутое относительно
обеих операций и являющееся полем, называется
подполем, что обозначается Fￎ Q. Поле, которое не
имеет подполя, не совпадающего с самим полем,
называется простым полем. Существует единственное
простое бесконечное поле.– это поле Q рациональных
чисел.
Конечные поля называются полями Галуа –
по имени французского математика Эвариста Галуа.
Далее рассматриваются и используются, как правило,
конечные поля.
Порядком поля называется число элементов.
Конечное поле порядка q обозначается GF(q), или Fq
.
Пример. Простейшим полем является поле из двух
элементов – поле GF(2). Операции этого поля
определяются таблицами, из которых следует, что
сложение соответствует булевой функции сложения по
модулю 2, а умножение – конъюнкции.+ A · A
B 0 1 b 0 1
0 0 1 0 0 0
1 1 0 1 0 1
Пример. Если p – простое число, то целые числа {0,
1, 2, …, p – 1} образуют поле G(p). При этом все
операции (сложения, вычитания, умножения, деления)
выполняются по модулю p.
Пример. Если p – простое число, а n – натуральное,
то поле, которое содержит N = pn
элементов, не может
быть образовано из совокупности целых чисел по
модулю N. Действительно, для p = 2 и n = 2 число
элементов N = pn
= = 22
= 4. В множестве классов
вычетов по модулю 4 элемент 2 не имеет обратного, так
как 2 · 2=0 mod 4. Т. е. множество, состоящее из
четырех элементов, совсем не похоже на поле G(N),
которое состоит из pn
= N элементов. Элементами поля,
которое состоит из pn
элементов, являются все
многочлены степени не более (n – 1) с коэффициентами
из поля G(p). Чтобы подчеркнуть эту разницу между
представленными полями, поля из pn
элементов
обозначают через G(pn
) (вместо G(N)). Поля G(pn
) будут
рассматриваться ниже. Мультипликативная группа
конечного поля порядка q обозначается GF(q)* и имеет
порядок на единицу меньше порядка поля
