Свойства операций и отношений

Если множество 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;f1,...,f_k;r1,...,r_l> , где {f1,...,f_k} = W_F, {r1,...,r_l} = W_R.

Определение 4 (Тип алгебраической системы).Типом алгебраической системы <A;f1,...,f_k;r1,...,r_l> называется пара наборов (n(f1),...,n(f_k)) и (n(r1),...,n(r_l)), состоящих из арностей операций и отношений. Тип будем записывать в виде <n(f1),...,n(f_k); n(r1),...,n(r_l)> .

Пример 2 (алгебраическая система).

<N ;+,·;<> является алгебраической системой типа <2, 2; 2>, так как операции +,· определены для любых двух натуральных чисел и результат снова является натуральным числом. <N;+,-;<> не является алгебраической системой, так как результат операции -, применённой к натуральным числам – не всегда натуральное число.

Группой называется множество G, на котором

определена ассоциативная бинарная операция ,

содержащее элемент е такой, что для любого элемента

aG выполняется

e а = а е = а,

и существует элемент a– 1 такой, что

а a– 1

= a– 1 а =e.

Указанный элемент е называется единицей группы.

Элемент a– 1 называется обратным к элементу а. Легко

показать, что единица группы единственна и что

элемент, обратный к данному элементу, также

определяется однозначно. Если операция

коммутативна, то группа называется коммутативной,

или абелевой.

Заметим, что не все коммутативные

операции ассоциативны. Например, если в

качестве операции использовать среднее

арифметическое двух вещественных чисел, то эта

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

Действительно:

(aa)b = ab = (a+b)/2,

a(ab) = 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)* и имеет

порядок на единицу меньше порядка поля