Множество с операциями. Алгебраические структуры. Полугруппа. Моноид. Группа

Определение и примеры.
10. Группа подстановок.
Определение 2.1. Бинарной операцией на множестве X называется правило, по которому любым двум элементам x, y из множества X ставится в соответствие некоторый, однозначно определенный, элемент из X, обозначаемый х * у.
Заметим, что на множестве X могут быть определены и так называемые унарные операции: каждому элементу множества X ставится в соответствие некоторый, однозначно определенный, элемент множества X. Таким образом задание унарной операции - это задание некоторого отображения f : X —> X. Точно также на множестве определяются нуль-арные операции: выделение какого-то элемента множества. По аналогии можно определить п-арную операцию на множестве X как некоторое отображение f : Хп → X.
На одном и том же множестве могут быть определены несколько операций. Например, на множестве Z определены две бинарные операции: сложение и умножение; унарная операция: каждому элементу z множества Z ставится в соответствие элемент (—z); две нуль-арные операции: выделение 0 и 1.
Определение 2.2. Операция * на множестве X называется
1) ассоциативной, если для любых элементов х, у, z X выполняется равенство (x*y)*z=х* (y*z);
2)коммутативной, если для любых элементов х,у X выполняется равенство х*у = у*х.
Определение 2.3. Элемент e в множестве X называется нейтральным, единицей, относительно операции * на X, если для любого элемента х из множества X выполняется равенство х*е=е*х= х.
Заметим, что выделение нейтрального элемента в множестве задает нуль-арную операцию на этом множестве. Если операция * - обычное умножение на множестве N, Z или R, то е = 1 называют единицей; если же * - обычное сложение, то е = 0 называют нулем.
Примеры.
1) Бинарные операции сложения и умножения на множестве Z - ассоциативны и коммутативны. Нейтральным эл-ом относительно операции сложения яв-ся 0, а относительно умножения – 1.
2) Рассмотрим множество матриц порядка 2×2 (таблица, состоящая из действительных чисел), такое множество обычно обозначают M2(R). На этом множестве определены две бинарные операции: сложение и умножение. Операция сложения - ассоциативна и коммутативна; операция умножения - ассоциативна, но не коммутативна. Нейтральным элементом относительно сложения является матрица

относительно операции умножения – матрица

Определение 2.4. Непустое множество X с заданной на нем ассоциативной операцией *, обозначаем (X, *), называется полугруппой. Полугруппу (X, *), в которой относительно операции * существует нейтральный элемент, называют моноидом.
Пример. Рассмотрим набор букв (алфавит) и множество слов в этом алфавите, которое обозначим М. На множестве М зададим бинарную операцию * следующим образом: для любых слов u иvиз мн-ва М определим и * v = uv, то есть слово и * v получено приписыванием к слову и слова v. Тогда (М, *) - полугруппа. Доб. к мн-ву М пустое слово е, тогда ({М, е}, *) - моноид.
Теорема 2.5. Нейтральный элемент в моноиде - единственен.
Доказательство. Пусть (М, *) - моноид; е, f - два нейтральных элемента в (М, *). Тогда е = е*f = f по определению.
Определение 2.6. Пусть (М, *, е) - моноид. Элемент b называется обратным к элементу а, если а*b=b*а=е. Элемент а в этом случае называют обратимым элементом; элемент b обозначают а -1.
Заметим, что, если * - операция сложения, то вместо а -1 пишут — а и называют этот элемент противоположным к элементу а. Например, в моноиде (Z, +,0) любой элемент z имеет противоположный элемент — z, то есть на множестве Z определена унарная операция: f(z) = —z. В моноиде (Z, ∙, 1) обратимы только два элемента: 1 и -1.
Теорема 2.7. Пусть (М, *,е) - моноид. Тогда:
1) для любого элемента а М обратный элемент, если он существует, - единственен;
2) элемент е - обратим и е -1 = е;
3) обратный элемент a -1 к элементу а, если он существует, обратим и (а -1) -1 = а;
4) если а, b - обратимые элементы в М, то (а * b) -1 = b -1 * a -1.
Доказательство. 1) Предположим b1, b2 - обратные элементы к элементу а М. Тогда
b1 = b1 * e = b1 * (a * b2) = (b1 * a) * b2 = e * b2 = b2.
Утверждения 2) и 3) - очевидны.
4) Так как (а * b) * (b -1 * а -1) = а * (b * (b -1 * b -1)) = а * ((b * b -1) * a -1) = а * (е * a -1) = а * a -1 = е, то 4) доказано.
Определение 2.8. Алгебраической системой называют непустое множество с семейством операций и отношений, заданных на нем.
Мы уже рассматривали примеры алгебраических систем: полугруппы, моноиды, линейно или частично упорядоченные множества, множества с отношением эквивалентности. Пример более богатой структуры: (Z, +, ∙, 0,1, ≤).Здесь определены две бинарные операции: + и ∙ ; две 0-арные операции: выделены 0 и 1 ; определено также отношение порядка ≤
Рассмотрим три основных способа построения новых алгебраических из уже имеющихся.
Определение 2.9. Пусть М - алгебраическая система, N является подмножеством множества М, N ≠ Ø. N называется подсистемой алгебраической системы М, если
1) N замкнута относительно всех операций, определенных на N: для любой n-арной операции f(a1,..., ап), определенной на множестве М, и любого набора элементов {m1,..., тп} из множества N элемент f(m1,..., тп) N;
2) для любого отношения S, заданного на множестве М в данной алгебраической системе, определено сужение SN ЭТОГО отношения на подмножестве N: если n1, n2 N, то n1 SN n2 тогда и только тогда, когда n1 Sn2
Заметим, что, если алгебраическая система имеет специальное название: моноид, группа, кольцо, поле, то подсистема называется соответственно: подмоноид, подгруппа, подкольцо, подполе.
Определение 2.10. Пусть М и N - алгебраические системы с одинаковым набором операций и без отношений. Тогда декартово произведение М × N будет такой же алгебраической структурой, если для любой k-арной операции f(a1,..., ak), определенной на множествах М и N, на множестве М × N следующим образом определим операцию:
f((m1, n1), . . . , (mk, nk)) = (f(m1, . . . ,mk), f(n1, . . . , nk)).
Аналогично опеделяются операции на произведении п алгебраических систем.
Определение 2.11. Пусть М - алгебраическая система, в которой нет отношений. Предположим, что на М можно задать отношение эквивалентности ~, согласованное с операциями на М, а именно: для любой n-арной операции f(a1,... ,ап), определенной в алгебраической системе М и любых элементов из М таких, что m1 ~ т1’,..., тп ~ тп’ выполняется отношение f(m1,..., тп) ~ f(rn1’,..., тп’). Тогда множество классов эквивалентности (М/ ~) превращается в алгебраическую систему с теми же операциями, что действуют на множестве М :
f([m1]~ , [m2]~, . . . , [m2]~) = [f(m1,m2, . . . ,mn)]~.
Такая алгебраическая система называется фактор-системой алгебраической системы М по отношению эквивалентности ~.
Пример. Всем с детства известна алгебраическая система, где множество М = {чет, нечет}; задана бинарная операция + : чет + чет = нечет + нечет = чет, чет + нечет = нечет + чет = нечет; выделен нулевой элемент: 0 = чет. Такая алгебраическая система фактически является фактор-системой алгебраической системы (Z, +, 0) по отношению эквивалентности ~:
z1 ~ z2 тогда и только тогда, когда z1 - z2 делится нацело на 2.
Определение 2.12. Группой называется множество G с бинарной операцией, обозначаемой обычно ∙, удовлетворяющей трем условиям:
1)операция ∙ - ассоциативна;
2)существует единичный элемент е такой, что g • е = е • g = g для любого g G;
3)все элементы множества G обратимы, то есть для любого g G найдется такой элемент g -1 G, что g ∙ g -1 = g -1 ∙ g = е.
Итак, группа - это моноид, в котором каждый элемент обратим. Заметим, что группа G называется абелевой, если операция ∙ коммутативна.
В группе G можно решить любое уравнение вида а∙х = b или х∙а = b (a,b G). Решением первого уравнения будет х = а -1∙b, а второго - х = b ∙ а -1. Если операция в группе - сложение, то рассмотренные выше уравнения имеют вид: а + х = b или х + а = b; соответственно решениями будут х = (-а) + b или х=b+(-а), где (-а) - противоположный (обратный) элемент к элементу а.
Примеры.
1) Алгебраические системы (Z, +, 0), (R, +, 0) являются абелевыми группами по сложению.
2) Множество всех невырожденных матриц размера п х п над R относительно обычной операции умножения матриц является группой, которую обозначают GLn(R).
3) Множество SLn(R) = {А GLn(R) | detA = 1} - группа относительно обычной операции умножения матриц, являющаяся подгруппой группы GLn(R). Такая группа называется специальной линейной группой.
4) Алгебраическая система ({е},-|е∙е = е) является группой, состоящей только из одного единичного элемента. Такая группа называется единичной. Заметим, что в любой группе есть единичная подгруппа.
5) Алгебраическая система ({1,-1} | 1,-1 Z, ∙) - группа из двух элементов относительно обычной операции умножения на Z.
6) Пусть X = {1,2,..., n}. Тогда алгебраическая система (BiXX,o) является группой всех биективных отображений множества X на себя относительно операции композиции.
Такую группу называют группой подстановок на множестве X. Рассмотрим ее более подробно. Пусть σ ВiХX и σ(1) = i1, σ(2) = i2,..., σ(п) = in. Отображение σ назовем подстановкой и обозначим (i1, i2,..., in). Подстановка е = (1, 2,..., п), называемая тождественной подстановкой, будет нейтральным элементом, или единицей в группе подстановок на множестве X. Для любого элемента а = (i1, i2,..., in) из группы подстановок определен обратный элемент σ -1 так, что σ−1(ij) = j, (j {1, 2,…, n}).
Группу подстановок на множестве из п элементов обозначают Sn. Таким образом, BiXX = Sn. Известен порядок этой конечной группы: |Sn| = |ВiХX| = п!. Если п > 3, то группа Sn не является абелевой группой.

Powered by Drupal - Design by artinet