Элементы общей алгебры Алгебра, гомомофризм, изоморфизм, полугруппа, группа

Алгебраическая операция На множестве А определена алгебраическая операция, если каждым двум элементам этого множества, взятым в определенном порядке, однозначным образом поставлен в соответствие некоторый третий элемент из этого же множества. Пример: 3+2=5 (3,2)5

n-арная операция n-арной операцией на множестве М будем называть функцию типа φ: M nM. Число n называется арностью операции. Операция α, отображающая любой элемент множества M в себя, называется тождественной операцией. Тождественной операцией на множестве R, например, является умножение на единицу.

Коммутативность Функциональный вид φ(a,b) Запись арифметических операций aφb Операция φ называется коммутативной, если для любых элементов a,b выполняется: aφb = bφa.

Ассоциативность Операция φ называется ассоциативной, если для любых элементов a,b,c выполняется: (aφb)φc=aφ(bφc). Выполнение условия ассоциативности означает, что скобки в выражении (aφb)φc можно не расставлять.

Дистрибутивность Операция φ называется дистрибутивной слева относительно операции ψ, если для любых a,b,c выполняется: aφ(bψc)=(aφb)ψ(aφc), и дистрибутивной справа относительно операции ψ, если для любых a,b,c выполняется: (aψb)φc=(aφc)ψ(bφc).

Наличие свойства дистрибутивности позволяет раскрывать скобки. Например, умножение дистрибутивно относительно сложения (и вычитания) и справа, и слева: (b+c)a=a(b+x)=a(b+c)=ab+ac. Возведение в степень дистрибутивно относительно умножения справа (ab) c =a c b c, но не слева: a bca b a c. Сложение (и вычитание) чисел недистрибутивно относительно умножения: a+bc(a+b)(a+c).

Алгебра Пусть дано некоторое множество M, на котором задана совокупность операций Ω={φ 1, φ 2,…, φ m }. Структура вида A=(M; Ω) называется алгеброй; множество M называется несущим множеством, совокупность операций Ω - сигнатурой, вектор арностей операций (n 1, n 2,…, n m ) называется типом. Пример. A={R, +, *}

Гомоморфизм Пусть даны две алгебры A=(M 1 ; φ 1, φ 2,…, φ n ) и B=(M 2 ; ψ 1, ψ 2,…, ψ n ). Гомоморфизмом алгебры A в алгебру B называется функция f : M 1M 2, такая, что для всех a M 1 выполняется условие: f(φ i (a))= ψ i (f(a)) для любого i=1,…, n. (*)

Гомоморфизм Г: ln x=y ln (ab)=ln a+ln b (R+; φ), (R; φ+)

Виды гомоморфизма Гомоморфизм, который является инъекцией, называется мономорфизмом. Гомоморфизм, который является сюръекцией, называется эпиморфизмом. Гомоморфизм, который является биекцией, называется изоморфизмом.

Примеры Пусть N - множество натуральных чисел, N 2 – множество натуральных чётных чисел. Алгебры (N; +) и (N 2 ; +) изоморфны; изоморфизмом является отображение f : n2n, причём условие здесь имеет вид 2(a + b)=2a + 2b. Поскольку N 2 N, то данный изоморфизм есть изоморфизм алгебры (N; +) в себя.

Примеры Рассмотрим алгебры: A=(N,+,*), B(N 7,, ). N 7 множество классов остатков (вычетов) по модулю 7, N 7 ={K 0, K 1, …, K 6 }. Покажем, что эти алгебры гомоморфные: Г(13)=К 6, Г(28)=К 0, Г(13+28)=Г(41)=К 6, Г(13+28)=Г(13)+Г(28)=К 6 +К 0 =К 6, Г(13*28)=Г(264)=К 0 =Г(13)*Г(28)=К 6 *К 0 =К 0

Примеры Изоморфизмом между алгебрами (R+;*) и (R;+) является, например, отображение alg a. lg ab=lg a+lg b. Булевы алгебры, образованные двумя различными множествами одинаковой мощности, изоморфны: операции у них просто одинаковы, а отображением f может служить любое взаимно- однозначное соответствие.

Изоморфизм Эквивалентность = рефлексивность + + симметричность + +транзитивность A~A – рефлексивность, A~DB~A – симметричность, (A~B) (B~C)(A~C) – транзитивность.

Полугруппа Полугруппой называется алгебра вида (M; φ) с одной ассоциативной бинарной операцией φ. (a φ b) φ c=a φ (b φ c)=abc

Полугруппа Как правило, в качестве такой операции φ используется умножение. Поэтому результат её применения к двум различным элементам записывают в виде ab или ab, а результат неоднократного применения к одному элементу записывают в виде a 2, a 3 и так далее. Такая запись называется мультипликативной. Полугруппу часто обозначают записью P=( M; ).

Абелева полугруппа В общем случае, abba (как, например, произведение матриц), то есть данная операция некоммутативна. Если же умножение коммутативно, то полугруппа называется коммутативной или абелевой полугруппой.

Моноид Если множество-носитель полугруппы содержит такой элемент e, что для любого a выполняется a ae=ea=a, то этот элемент называется единицей (нейтральным элементом), а такая полугруппа называется моноидом.

Нейтральный элемент Легко показать, что если полугруппа содержит единицу, то она единственна. Действительно, допустим, существуют две единицы e 1 и e 2. Тогда e 1 e 2 =e 1 и e 1 e 2 =e 2, следовательно e 1 =e 2.

Примеры а) Алгебра (N 2 ;*), где N 2 – множество чётных чисел является абелевой полугруппой. Однако, очевидно, она не имеет единицы. б) Алгебра (M;*), где M – множество квадратных матриц одинаковой размерности образует некоммутативную полугруппу. Причём эта полугруппа является моноидом, а роль единицы в ней выполняет единичная матрица E. в) Алгебра (N;*) является коммутативной полугруппой с единицей.

Порождающее множество Если любой элемент полугруппы P=( M; ) можно представить в виде произведения конечного числа элементов множества M 0 M, то множество M 0 называется порождающим множеством или системой образующих полугруппы, а его элементы называются образующими. Например, в полугруппе (N;*) порождающим множеством служит бесконечное множество простых чисел.

Циклическая полугруппа Полугруппа, которая имеет только одну образующую, называется циклической. Можно показать, что в циклической полугруппе все элементы являются степенями (в смысле имеющейся операции) этой образующей. Например, циклической полугруппой является полугруппа (N;+), поскольку любое натуральное число – это сумма некоторого количества единиц.

Пусть полугруппа P=( M; ) имеет конечное число образующих {a 1, a 2,…, a n }. Слова в алфавите {a1, a 2,…, a n }. Причём некоторые различные слова могут оказаться равными, как элементы (равные элементы 2 4 =2*8=16*1 записаны различными словами). В коммутативной полугруппе для двух любых элементов выполняется равенство ab=ba, позволяющее устанавливать равенство элементов, в том числе, записанных различными словами. Подобные равенства называются определяющими соотношениями.

Свободная полугруппа Полугруппа, в которой нет определяющих соотношений, и любые два различных слова обозначают различные элементы группы, называется свободной. Доказано, что каждую полугруппу можно получить из некоторой свободной полугруппы введением некоторых определяющих соотношений.

Пример А={a, b, c, …} A* - слова, сложенные из А, алгебра. Введем алгебраическую операцию конкатенация, которая состоит в приписывании одному слову другого. Abba*cab=abbacab. Данная полугруппа имеет 1 – пустое слово (моноид), т.к. приписываем его справа (слева), не меняет слово.

Группа Группой называется полугруппа с единицей, в которой для каждого элемента a существует элемент a –1, называемый обратным к элементу a и удовлетворяющий условию aa –1 =e.

Группа Множество А с определенной на нем алгебраической операцией (например, умножением) называется группой, если выполнены следующие условия: 1. для любых трех элементов a, b, c A выполняется свойство ассоциативности: a(bc)=(ab)c Ассоциативность (всякая группа есть подгруппа) – (g 1 °g 2 )°g 3 =g 1 °(g 2 °g 3 )

Группа 2. в множестве А существует такой элемент е, что для любого элемента а из этого множества выполняется равенство: ae=ea=a Существование единицы e G g G (e°g=g°e=g - моноид) 3. для любого элемента а существует элемент а -1 из этого же множества такой, что aa –1 =a –1 a=e Существование обратного элемента g G g –1 G (g°g –1 =g –1 °g=e)

Группы Число элементов в множестве-носителе называется порядком группы. Группа, в которой операция коммутативна, называется коммутативной или абелевой. Группа, в которой все элементы являются степенями одного элемента, называется циклической. Для абелевых групп часто применяется аддитивная форма записи: операция обозначается, как сложение, а единица обозначается, как 0. Существуют конечные и бесконечные группы. Если группа конечная, т.е. |G|=n, то n –порядок группы.

Свойства групп Обратный к данному элемент всегда определяется однозначно. (a 1)-1 = a, a m a n = a m+n, (a m ) n = a mn. (ab) 1 =b 1 a 1. Законы сокращения: ca=cb a=b, ac=bc a=b. Обратный элемент к нейтральному есть сам нейтральный элемент. Группа содержит единственное решение x любого уравнения x · c = b или c · x = b; то есть в группе возможны однозначно определённые правое и левое «деление». Пересечение двух подгрупп группы G есть подгруппа группы G.

Примеры а) Алгебра (Z;+) является абелевой циклической группой, в которой роль единицы играет 0, а роль элемента, обратного к элементу a играет (– a). б) Алгебра (Q \0 ;), где Q \0 – множество рациональных чисел без нуля, является абелевой группой. Обратным к элементу a является 1/a. в) Множество невырожденных квадратных матриц порядка n с определителем, отличным от нуля с операцией умножения является некоммутативной группой. г) Множество матриц одинакового порядка m×n с операцией сложения образует абелеву группу.

Нахождение элемента, обратного данному, в общем случае, есть унарная операция. Поэтому тип любой группы (2,1). Иногда, при записи конкретной группы указывают в скобках кроме бинарной операции ещё и эту унарную операцию, либо (чаще) нейтральный элемент группы. Например, для группы из примера а соответствующая запись имеет вид (Z;+;0), а для группы из примера б - (Q \0 ;;1).

Пусть M и N – подмножества группы, т.е. M G, N G, тогда введем множество M -1 ={x G| h M,x=h -1 }, MN={x G| h 1 M, h 2 N,x=h 1 *h 2 } NMMN в силу некоммуникативности.

Рассмотрим элемент а из группы G: a 0 =e, а k+1 =a k *a=a*a k. Порядок элемента а группы G – минимальное натуральное число n такое, что a n = e. В случае, если такого n не существует, считается, что a имеет бесконечный порядок

Подгруппа Подгруппа подмножество H группы G, само являющееся группой относительно операции, определяющей G. Подмножество H группы G является её подгруппой тогда и только тогда, когда: 1. содержит единичный элемент из G, 2. содержит произведение любых двух элементов из H, 3. содержит вместе со всяким своим элементом h обратный к нему элемент h 1. Более подробно это означает, что h,h H h*h H, e H и h H h –1 H.

Коммутативная операция Если операция в группе коммутативна, она обозначается (+) и называется сложением. В этом случае нейтральный элемент называется нулем и удовлетворяет условию: g+0=g. Обратный элемент в этом случае называется противоположным и обозначается (–g). Степени элемента g имеют вид g+g+...+g, называются кратными элемента g и обозначаются ng.

Пример Рассмотрим множество несобственных матриц – линейную группу порядка n. Рассмотрим матрицы, определители которых равны единице. L n (1) L n. det (A 1 *A 2 )=det A 1 *det A 2. Отсюда следует, что определитель произведения двух матриц из L n (1) равен единице, поэтому L n (1) подгруппа группы L n.

Пример Пример конечной подгруппы L n : {E,-E} L n. Докажем, что это подгруппа. замкнутость относительно операций E*E=E, E*-E=-E, -E*-E=E E {E,-E}. Если условия выполняются, значит, мы имеем дело с подгруппой.

Истинная подгруппа Каждая группа G обладает единичной подгруппой E={e}. Всякая подгруппа, отличная от всей группы, называется истинной (нетривиальной) подгруппой этой группы. Истинная подгруппа некоторой бесконечной группы может быть изоморфна самой группе. Сама группа G и единичная подгруппа называется несобственными (тривиальными) подгруппами группы G, все остальные собственными.

Циклическая группа Пересечение всех подгрупп группы G, содержащих все элементы некоторого непустого множества M, называется подгруппой, порожденной множеством M, и обозначается. Если M состоит из одного элемента a, то называется циклической подгруппой элемента a. Группа, совпадающая с одной из своих циклических подгрупп, называется циклической группой. Если группа G 1 изоморфна некоторой подгруппе H группы G, то говорят, что группа G 1 может быть вложена в группу G.

Рассмотрим элемент а из группы G: a 0 =e, а k+1 =a k a=a a k. Порядок элемента а группы G – минимальное натуральное число n такое, что a n = e. В случае, если такого n не существует, считается, что a имеет бесконечный порядок

Подгруппа Подгруппа подмножество H группы G, само являющееся группой относительно операции, определяющей G. Подмножество H группы G является её подгруппой тогда и только тогда, когда: 1. содержит единичный элемент из G, 2. содержит произведение любых двух элементов из H, 3. содержит вместе со всяким своим элементом h обратный к нему элемент h 1. Более подробно это означает, что h,h H h*h H, e H и h H h –1 H.

Коммутативная операция Если операция в группе коммутативна, она обозначается (+) и называется сложением. В этом случае нейтральный элемент называется нулем и удовлетворяет условию: g+0=g. Обратный элемент в этом случае называется противоположным и обозначается (–g). Степени элемента g имеют вид g+g+...+g, называются кратными элемента g и обозначаются ng.

Пример Рассмотрим множество невырожденных матриц – линейную группу порядка n. Рассмотрим матрицы, определители которых равны единице. L n (1) L n. det (A 1 *A 2 )=det A 1 *det A 2. Отсюда следует, что определитель произведения двух матриц из L n (1) равен единице, поэтому L n (1) подгруппа группы L n.

Пример Пример конечной подгруппы L n : {E,-E} L n. Докажем, что это подгруппа. замкнутость относительно операций E*E=E, E*-E=-E, -E*-E=E E {E,-E}. Если условия выполняются, значит, мы имеем дело с подгруппой.

Истинная подгруппа Каждая группа G обладает единичной подгруппой E={e}. Всякая подгруппа, отличная от всей группы, называется истинной (нетривиальной) подгруппой этой группы. Истинная подгруппа некоторой бесконечной группы может быть изоморфна самой группе. Сама группа G и единичная подгруппа называется несобственными (тривиальными) подгруппами группы G, все остальные собственными.

Циклическая группа Пересечение всех подгрупп группы G, содержащих все элементы некоторого непустого множества M, называется подгруппой, порожденной множеством M, и обозначается. Если M состоит из одного элемента a, то называется циклической подгруппой элемента a. Группа, совпадающая с одной из своих циклических подгрупп, называется циклической группой. Если группа G 1 изоморфна некоторой подгруппе H группы G, то говорят, что группа G 1 может быть вложена в группу G.

Кольцо Множество R с двумя определенными в нем алгебраическими операциями, сложением и умножением, называется кольцом, если относительно операции сложения оно является абелевой группой, а операция умножения дистрибутивна, т.е. для любых элементов a, b и с R справедливы равенства a(b+c)=ab+ac; (b+c)a=ba+ca.

Коммутативное кольцо Если операция умножения, определенная в кольце коммутативна, то такое кольцо называется коммутативным кольцом. Из определения следует, что любое кольцо имеет две бинарные и одну унарную операцию, поэтому его тип – (2,2,1).

Тело Когда группа коммутативна, ее единица называется нулем кольца. Но в кольце может быть единица, т.е. нейтральный элемент по отношению к умножению. Если при этом в кольце R элементы не равны нулю и образуют относительно операции умножения группу, она называется телом. Единица этой группы называется единицей тела. Рассмотрим множество целых чисел – кольцо с единицей, не тело, т.к. нет обратного кроме единицы по отношению к умножению.

Поле Полем называется коммутативное кольцо, в котором для любого ненулевого элемента a 0 и любого элемента b существует единственный элемент х такой, что ax = b. Другими словами, для любой пары элементов a 0 и b уравнение ax = b имеет единственный корень. Практически это определяет в поле существование операции деления.

Пример Алгебра (Z;+) является кольцом и называется кольцом целых чисел. Она, однако, не является полем, поскольку, например, уравнение 2х=3 в ней неразрешимо. Алгебра (Q;+;*) является полем и называется полем рациональных чисел. Все остатки от деления на натуральное число образуют кольцо, а от деления на простое число поле.

Алгебра вычетов Все остатки от деления на натуральное число образуют кольцо, а от деления на простое число поле. Деление: остаток меньше модуля m, остаток (0, 1, …, m-1) {K 0 ; K 1 ;…, K 8 }=M – остаток при делении на девять. Построим на этом множестве М алгебру K s K i =K p

Таблица Кэли Чтобы задать операцию, зададим таблицу Кэли. Таблица Кэли в абстрактной алгебре таблица, которая описывает структуру конечных алгебраических систем с одной бинарной операцией. Названа в честь английского математика Артура Кэли.

k 3 =C*9+3 k 5 =C*9+5 k 3 +k 5 =(C+C) mod 9=8 5 8 mod 9=4 6 5 mod 9=2

m=5 a b mod m=

Умножение по модулю m a b mod 5 k 3 =C5+3 k 2 =C5+2 k 1 =k 2 k 3 =CC25+(C+C)5+6

Свойства колец с единицей 0*x=x*0=0 Если y R, то (-x)y=x(-y)=-xy, где - обозначение обратной операции в аддитивной группе кольца. Доказательство: (-x)y+xy=(- x+x)y=0*y=0, x(-y)+xy=x(-y+y)=x*0=0. Значит, (-x)y=x(-y)=-xy

Решетка Решёткой называется множество M, частично упорядоченное отношением нестрогого порядка, с двумя бинарными операциями и, такое что выполнены следующие условия (аксиомы решётки): 1. a a=a; aa=a (идемподентность); 2. a b=b a; ab=ba (коммутативность); 3. (a b) c=a (b c); (ab)c=a(bc) (ассоциативность); 4. ab) a=a, (a b)a=a (поглощение).

Решетки Решётка называется дистрибутивной, если выполняются два следующих условия a (bc)=(a b)(a c), и a(b c)=(ab) (ac). Если в решётке существует элемент 0, такой что для любого выполняется, то он называется нижней гранью (нулём) решётки. Если в решётке существует элемент 1, такой что для любого выполняется, то он называется верхней гранью (единицей) решётки. Решётка, имеющая верхнюю и нижнюю грани, называется ограниченной.

Дополнение Теорема. Если нижняя (верхняя) грань решётки существует, то она единственная. В ограниченной решётке элемент a –1 называется дополнением элемента a, если aa –1 =0 и a a –1 =1.

Примеры Любое полностью упорядоченное множество, например, множество целых чисел, можно превратить в решётку, определив для любых a,b M, что a b=max(a,b) и ab=min(a,b). Определим на множестве натуральных чисел отношение частичного порядка следующим образом: ab, если a является делителем b. Тогда a b есть наименьшее общее кратное этих чисел, а ab их наибольший общий делитель.

Решётка, в которой пересечение и объединение существуют для любого подмножества её элементов, называется полной. Конечная решётка всегда полна.