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

Презентация:



Advertisements
Похожие презентации
Элементы общей алгебры Алгебра, гомомофризм, изоморфизм, полугруппа, группа.
Advertisements

Элементы общей алгебры Подгруппа, кольцо, поле, тело, решетка.
Элементы общей алгебры Группа, кольцо, поле, тело, решетка.
Элементы общей алгебры Алгебра, гомомофризм, изоморфизм, полугруппа, группа.
§12. Основные алгебраические структуры Пусть M некоторое множество. ОПРЕДЕЛЕНИЕ. Говорят, что на множестве M задана бинарная алгебраическая операция если.
1. Множества, отношения, функции, операции Множество базовое неопределяемое понятие математики Множество состоит из элементов Декартово произведение множеств:
Линейная алгебра Матрицы. Основные понятия. Действия над матрицами Метод обратной матрицы решения систем линейных уравнений.
1 1. Множества Понятие множества. Логические символы Под множеством понимают совокупность определенных и отличных друг от друга объектов, объединенных.
1 Кубенский А.А. Дискретная математика Глава 1. Множества и отношения Решетки Решетка – это множество M с определенными на нем двумя бинарными операциями.
1 2. Матрицы. 2.1 Матрицы и их виды. Действия над матрицами. Джеймс Джозеф Сильвестр.
План лекции: 1. Векторы. Линейные операции над векторами. 2. Линейная зависимость и независимость векторов. 3.Понятие базиса. Координаты вектора. 4. Разложение.
Функции и отображения Отображения. N-местные функции. Понятие образов и прообразов элементов. Свойства функций: инъекция, сюръекция и биекция. Обратные.
1 Кубенский А.А. Дискретная математика Глава 1. Множества и отношения Отношения Декартово произведение множеств: A B = { (a, b) | a A, b B } B A.
Натуральные числа Целые числа Рациональные числа Вещественные числа Комплексные числа Множества и массивы.
Содержание: Натуральные числа и действия над ними Натуральные числа и действия над ними Натуральные числа и действия над ними Натуральные числа и действия.
Теория множеств. Определение Множество одно из ключевых понятий математики, в частности, теории множеств и логики. Понятие множества является одним из.
ЭЛЕМЕНТЫ ВЕКТОРНОЙ АЛГЕБРЫ Лекция 3. План лекции: Понятие вектора. Действия над векторами. Линейно зависимые и линейно независимые векторы. Размерность.
Теория матриц Лекция 5. План лекции: Понятие матрицы. Операции с матрицами. Определители, их свойства. Обратная матрица. Характеристическое уравнение.
МАТРИЦЫ Ельшина А.О. ФИСМО, социология, 1 курс. ОПРЕДЕЛЕНИЕ Матрицей Матрицей размером m×n называется совокупность m·n чисел, расположенных в виде прямоугольной.
После изучения темы «Комплексные числа учащиеся должны: Знать: алгебраическую, геометрическую и тригонометрическую формы комплексного числа. Уметь: производить.
Транксрипт:

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

Алгебраическая операция На множестве А определена алгебраическая операция, если каждым двум элементам этого множества, взятым в определенном порядке, однозначным образом поставлен в соответствие некоторый третий элемент из этого же множества. Пример: 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 их наибольший общий делитель.

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