Новиков Ф.А. Дискретная математика для программистов (860615), страница 15
Текст из файла (страница 15)
Алгебраические структурыназывается типом; множество операций Е называется сигнатурой. Запись: (М; Е)или (М; </?i,..., <рт). Операции ipi конечноместны, сигнатура Е конечна. Носитель не обязательно конечен, но пе пуст.ЗАМЕЧАНИЕДалее для обозначения алгебры везде, где это возможно, используется прописная рукописная буква, а для обозначения её носителя — соответствующая обычная прописнаябуква: А = (А;£). Такое соглашение позволяет использовать вольности в обозначениях,пе вводя явно две буквы для алгебры и для носителя, а подразумевая одну из них поумолчанию. Например, выражение «алгебра А» означает алгебру А с носителем А и сигнатурой, которая ясна из контекста, а запись а е А означает элемент а из носителя Аалгебры А.Если в качестве ipi допускаются не только функции, но и отношения, то множество М вместе с набором операций и отношений называется моделью. В приложениях обычно используется следующее обобщение попятия алгебры. ПустьМ — { M i , .
. . , Мп} — множество основ, Е = {(^i,..., <pm} — сигнатура, причём<pi: М^ х • • • х Mi n —> Mj. Тогда (M; Е) называется многоосновной алгеброй.Другими словами, мпогоосновная алгебра имеет несколько носителей, а операциясигнатуры действует из прямого произведения некоторых носителей в некоторыйноситель.2.1.2. Замыкания и подалгебрыПодмножество носителя X с М называется замкнутым относительно операции(р, еслиV x i , . . .
,х п G X (ip(x\,..., х п ) G X ) .Если X замкнуто относительно всех у? е Е, то ( Х ; Е х ) называется подалгеброй(М;Е), где Е х =Ч>* = 4>i\ x ^ k = n iПримеры1. Алгебра (R;+, •) — поле вещественных чисел. Тип — (2,2). Все конечные подмножества, кроме {0}, не замкнуты относительно сложения, и все конечныеподмножества, кроме {0} и {0,1}, не замкнуты относительно умножения.
Полерациональных чисел (Q;+, ) образует подалгебру. Кольцо целых чисел (Z;+, •)образует подалгебру алгебры рациональных и, соответственно, вещественныхчисел.2. Алгебра ( 2 м ; U, П, _ ) — алгебра подмножеств над множеством М. Тип — (2,2,1).При этом VX с М ( ( 2 х ; U,П, _ )) — её подалгебра.3. Алгебра гладких функций ( { / | / : К —> R} ;где ^ — операция дифференцирования.
Множество полипомов одной переменной х образует подалгебру,которая обозначается772.1. Алгебры и морфизмыНепустое пересечение подалгебр некоторой алгебры образует подалгебру этой же алгебры.ТЕОРЕМАДОКАЗАТЕЛЬСТВОПусть ( Х ^ Е ^ ) — подалгебра (М;Е). ТогдаV* ( V j (v**{xu...,xnj)EX,;))(^'(цin j)ef|^)-DЗамыканием множества X с M относительно сигнатуры Е (обозначается [Х]Е)называется множество всех элементов (включая сами элементы множества X),которые можно получить, применяя операции из Е. Если сигнатура подразумевается, её можно пе указывать.Пример В кольце целых чисел (Z; +, •) замыканием числа 2 являются чётныечисла, то есть [{2}] = {п е Ъ | п = 2к к к е Z}.Свойства замыкания:1.
X с У =ф- [X] с [У].2. X с [X].3. [[X]] = [X].4. [X] U [Y] с [X U Y).Пусть А = (А; Е) — некоторая алгебра и X i , . . . , X n с А — некоторые подмножества носителя, а (р € Е — одна из операций алгебры. Тогда используетсяследующее соглашение об обозначениях:<р{Х\,..., Хп) = f {ч>{х\,... ,хп) I Xi е Xi к ...
к хп ехп},то есть алгебраические операции можно применять не только к отдельным элементам, по и к множествам (подмножествам носителя), получая, соответственно,не отдельные элементы, а множества (подмножества носителя), подобно тому,как это определено в подразделе 1.6.3.2.1.3. Система образующихМножество М' с М называется системой образующих алгебры (М;Е), если[М']Е = М. Если алгебра имеет конечную систему образующих, то алгебра называется конечно-порождённой. Бесконечные алгебры могут иметь конечные системы образующих.Пример Алгебра натуральных чисел — (N; +) — имеет конечную систему образующих 1 е N.78Глава 2.
Алгебраические структурыПусть заданы набор функциональных символов Ф =. . . , <рт}, служащих обозначениями функций некоторой сигнатуры Е типа N = ( n i , . . . , ПТ), и множествопеременных V = {х\,х2,.. •}. Определим множество термов Т индуктивнымобразом:1. V с Т;2.гт<Pi(tu...,tni)е т.Алгебра (Т; Ф) называется свободной алгеброй термов. Носителем этой алгебры является множество термов, то есть формальных выражений, построенныхс помощью знаков операций сигнатуры Е. Заметим, что множество V являетсясистемой образующих свободной алгебры термов.Пример Если V = {х} и Е = {+,•}. то свободная алгебра термов — этомножество всех выражений, которые можно построить из переменной х с помощью операций сложения и умножения, то есть алгебра полиномов от однойпеременной с натуральными коэффициентами.ОТСТУПЛЕНИЕАлгебры термов используются в программировании для определения абстрактных типовданных.2.1.4.
Свойства операцийНекоторые часто встречающиеся свойства операций имеют специальные названия. Пусть задана алгебра (М; Е) и а, Ь, с е М\ о,о е Е; о, о: М х М —> М.Тогда:1. Ассоциативность: (а о Ь) о с = а о (6 о с).2. Коммутативность: а о Ь — Ь о а.3. Дистрибутивность о относительно о слева: а о (Ь о с) = (а о Ь) о (а о с).4.
Дистрибутивность о относительно о справа: {аоЬ)ос—(а о с) о (Ь о с).5. Поглощение (о поглощает о): (а о Ь) о а = а.6. Идемпотентность: а о а = а.Примеры1. Ассоциативные операции: сложение и умножение чисел, объединение и пересечение множеств, композиция отношений.
Неассоциативные операции: возведение чисел в степень, вычитание множеств.2. Коммутативные операции: сложение и умножение чисел, объединение и пересечение множеств. Некоммутативные операции: умножение матриц, композиция отношений, возведение в степень.3. Дистрибутивные операции: умножение относительно сложения чисел.
Недистрибутивные операции: возведение в степень дистрибутивно относительноумножения справа, по не слева: ((а6)с = асЬс,аЬс ф аьас).792.1. Алгебры и морфизмы4. Пересечение поглощает объединение, объединение поглощает пересечение. Сложение и умножение не поглощают друг друга.5. Идемпотентные операции: наибольший общий делитель натуральных чисел,объединение и пересечение множеств. Неидемпотентные операции: сложениеи умножение чисел.2.1.5.
ГомоморфизмыПонятие гомоморфизма является одним из ключевых понятий алгебры. Каждаяалгебраическая структура определённым образом выделяет класс «разумных»отображений между объектами с данной структурой, согласованных с операциями этой структуры. Алгебры с различными типами имеют различное строение.Гомоморфизм определяется для алгебр одного тина. Пусть А = (A;.
. . , ipm)и Ъ = (Л;-01,.. •, Фт) — две алгебры одного типа. Если существует функция/: А —• В, такая, чтоУг G l..m (f((fii(au...,an))= ?A;(/(aj),..., f(an))),то говорят, что / — гомоморфизм из Л в В.ЗАМЕЧАНИЕОбразно говорят, что гомоморфизм «уважает» операции.Пусть А = {А]ф)} Ъ = (B\ip), тип = (1) и / : А —> В. Действие функцийможно изобразить с помощью следующей диаграммы:АfАfВВПусть / — гомоморфизм. Тогда если взять конкретное значение а е А и двигаться по двум различным путям на диаграмме, то получится один и тот жеэлемент Ь е В (так как /(<^(a)) = ip(f(a))). В таком случае диаграмма называется коммутативной.
Коммутативной диаграмма называется потому, что условиегомоморфизма можно переписать так:/ о V = ip о / ,где о — суперпозиция функций.Пример Пусть А = (N; +), Ъ = (Ni0; +ю), где N10 = {0,1,2,3,4,5,6,7,8,9}, а+ю — сложение по модулю 10. Тогда / : а(a mod 10) — гомоморфизм изАвЪ.Гомоморфизмы, обладающие дополнительными свойствами, имеют специальныеназвания:• Гомоморфизм, который является инъекцией, называется мономорфизмом.• Гомоморфизм, который является сюръекцией, называется эпиморфизмом.80Глава 2. Алгебраические структуры• Гомоморфизм, который является биекцией, называется изоморфизмом.
Другими словами, изоморфизм является одновременно мономорфизмом и эпиморфизмом.• Если А — В, то гомоморфизм называется эндоморфизмом, а изоморфизмназывается автоморфизмом.2.1.6. ИзоморфизмыПусть А = (А\ </?i,..., (рт) и Ъ = (В\ф\,...и f: АВ — изоморфизм.ТЕОРЕМА 1,фт) — две алгебры одного типаЕсли f : А —> В — изоморфизм, то f~l:В —• А — тоже изоморфизм.ДОКАЗАТЕЛЬСТВОРассмотрим произвольную операцию ip из сигнатуры алгебрыА и соответствующую ей операцию ф из сигнатуры алгебры Ъ.
Пусть вместимость этих операций п. Рассмотрим произвольные элементы a i , . . . , a n G А.Обозначим &i: = / ( a i ) , . . . ,bn : = f(an), где b\,... ,bn £ В. Поскольку / — биекция,имеем ai = f~l{b\),...,а„ = / _ 1 (Ь П ). ТогдаГ1{ф(Ьи...,Ъп)) = Г1 ( i K / ( a i ) , . . •, / Ы ) ) = Г= ¥>(аь ..., an) = ipir'ih),...,1(/Иаь..., ап))) =Г\Ьп)).•Если / : А —> Вf — изоморфизм, то алгебры А и 23 называют изоморфными и обозначают так: А ~ Ъ.
Если / ясно из контекста или просто неважно в конкретномрассуждении, то пишут А ~ Ъ.Отношение изоморфизма на множестве однотипных алгебр являет ся эквивалентностью.ТЕОРЕМА 2ДОКАЗАТЕЛЬСТВО[ Рефлексивность ]Аг~А, где / — тождественное отображение./[ Симметричность ] А ~ ЪЪ/_1~А.[ Транзитивность ] А ~ Ъ к Ъ ~ 9 = $ > А9~ 5 .•Примеры1. Пусть А = (N; +), Ъ = ({n | п = 2k, к е N} ; +) — чётные числа. Тогда А х ~2 Ъ.2. А = ( 2 м ; П, U) ~ Ъ = ( 2 м ; U, П>, f ( X ) = X.3. А — (К+; •)Ъ = (М; +).812.3. Алгебры сдвумяоперациямиПонятие изоморфизма является одним из центральных понятий, оправдывающих применимость алгебраических методов в различных областях. Действительгно, пусть Л = (А;£<р), Ъ =и Л ~ Ъ.
Пусть в алгебре Л установленосвойство Ф1 =где Ф1 и Ф2 — некоторые формулы в сигнатуре Е^. Посколькуалгебры А и Ъ изоморфны, отсюда немедленно следует, что в алгебре Ъ спра-ведливо свойство Ф1 = Ф2, где Ф1 и Ф2 — формулы, полученные из формулФ1 и Ф2 заменой операций из сигнатуры Е^, соответствующими операциями изсигнатуры Е^.
Таким образом, достаточно установить некоторое свойство в одной алгебре, и оно автоматически распространяется на все изоморфные алгебры.Алгебраические структуры принято рассматривать с точностью до изоморфизма.Понятие изоморфизма применяется не только в алгебре, но и практически вовсех областях математики.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
