Алгебры. Подалгебры. Гомоморфизмы алгебр.
Условимся упорядоченную пару из двух множеств А иВобозначать через <А, В>.
Определение 1.Пусть А - непустое множество, и {fi iÎI} -множество n-арных операций fi заданных на А. Упорядоченную пару <А, { fi | iÎI }> называют универсальной алгеброй с множеством операций { fi | iÎI }, а множество А - основным множеством или носителем алгебры.
Пишут <А, { fi }>.
Замечание 1.Хотя понятия алгебра <А, { fi }> и множество А различны, в том случае, когда ясно, какие операции заданы на А, говорят просто - алгебра А, т.е. алгебру отождествляют с ее носителем.
Замечание 2.В том случае, когда множество операций { fi | iÎI } в универсальной алгебре А - конечно, его задают перечислением элементов { fi , f2 ,...., fK } и в записи алгебры опускают фигурные скобки, то есть пишут <А, fi , f2 ,...., fK >.
Пример 1.<N, +, × , 1> - алгебра натуральных чисел. Здесь множество N рассматривается вместе с бинарными операциями сложения, умножения, а также с нуль-арной операцией фиксации единицы.
Пример 2.<Z, -, 0> - алгебра целых чисел. На основном множестве Z рассматриваемой алгебры заданы две операции: бинарная - вычитание и нулъ-арная - фиксация нуля.
Пример 3. Следующие пары <N, ->, <Z, :>, <Q, :>, <R, i> не являются алгебрами, так как рассматриваемые операции не выполняются на данных множествах.
Определение 2. Пусть на множествах А и В задано одно и то же множество операций. Алгебра <В, { fi }> называется подалгеброй алгебры <А, { fi }>. если множество В является непустым подмножеством множества А.
Пример 4. Алгебра <Н, + > является подалгеброй алгебры <Z, +>, так как N Ì Z, и множества их операций совпадают.
Теорема 1. Для того, чтобы непустое подмножество В множества А могло служить основным множеством для некоторой подалгебры универсальной алгебры <А, { fi }> необходимо и достаточно, чтобы подмножество В было замкнуто относительно каждой операции fi.
Доказательство:
Необходимость. Пусть ВÌА и <В,{ fi }> - подалгебра алгебры <А, { fi }>. Так как <B, { fi }> - алгебра, то каждая операция fi выполнима на В, т. е. множество В замкнуто относительно всех операций fi .
Достаточность. Пусть ВÌА и В замкнуто относительно каждой операции fi заданной на А. Это значит, что все операции fi выполнимы на В.
Кроме того, так как ВÌА, каждая операция fi будучи однозначной на А, однозначна и на В. Следовательно, <В, { fi }> - алгебра, более того -подалгебра алгебры <A, { fi } >. Теорема доказана.
Пример 5. Рассмотрим алгебру <Z, ×>. Подмножество Z-отрицательных чисел множества Z не является подалгеброй, так как Z-незамкнуто относительно заданной бинарной операции умножения.
Пример 6. Рассмотрим алгебру <Z, ×, 0>. Подмножество N не является подалгеброй, так как в N нет нуля, т.е. N незамкнуто относительно нуль-арной операции.
Определение 3. Пусть <А, f> и <В, g> - алгебры с n-арными операциями f и g. Отображение j: А®В множества А в множество В называется гомоморфизмом алгебры А в алгебру В, если выполняется условие:
"a1…., аnÎ А, j(f(a1 ,….,аn)) = g(j (а1),....,j( аn)) (*),
которое назовем - условием гомоморфности. Говорят также, что отображение j сохраняет операцию f алгебры А.
Замечание 1. Если f – нуль-арная операция, то она выделяет какой-то элемент (а) алгебры А, и операция g - также нуль-арная - выделяет какой-то элемент (b) алгебры В, то в этом случае условие гомоморфности (*) примет вид: j(а) =b .
Замечание 2. Если <А, *> и <В, #> - алгебры с бинар-ными операциями, то условие гомоморфности запишется в виде: "a, bÎ А, j(а*b) = j(а) # j(b).
Пример 7. Отображение lg: R+ ®R является гомоморфизмом алгебры <R+,×> на алгебру <R, +>. Действительно, " a, bÎR+ , lg (a×b) = lg a + lg b.
Определение 4. Алгебры <A, {fi}> и <В, {gi}> называ-ются: однотипными, если существует биективное отображение множества {fi} на множество {gi}, при котором соответственные операции fi и gi имеют один и тот же ранг.
В случае, если множества операций, заданных на А и В- конечны, определение однотипных алгебр можно сформу-лировать так:
Определение 4*. Алгебры <А, f1...,fk> и <В, g1...,gm> называются однотипными, если число их операций одинаково (k = m) и эти операции можно упорядочить так, что fi и gi (i = 1,..., к) будут иметь одинаковые ранги.
Пример 8. Алгебры <Q, +, :> и <С, ×, -> являются однотипными, а алгебры <Z, +, × > и <R, +, ×, :> однотипными не являются, так как число операций, заданных на Z и R, различно.
Пример 9. Алгебры <N, +, ×> и <Z, - , 1> разнотипны, так как на N обе операции бинарные, а на Z операция вычитания - бинарная, а операция фиксации единицы - нуль-арная.
Определение 5. Гомоморфизмом алгебры <А, {fi }> в однотипную ей алгебру <В, {gi}> называется отображение j: А® B такое, что при каждом iÎI выполняется условие гомоморфности:
"iÎI, "a1...,an ÎA j(fi(a1,...,an)) = gi(j(a1,...,an)). (**)
Говорят также, что отображение j сохраняет все операции, заданные на множестве А.
Определение 6. Алгебры А и В называются гомоморфнымиалгебрами, если существует гомоморфизм j алгебры А в алгебру В. Пишут, j: А®В — гомоморфизм.
Пример 10. Отображение lg:R+®R является гомоморфизмом алгебры <R+, ×, :> в алгебру <R+, ->, так как
" a, bÎR+ , lg (a×b) = lg a + lg b, т. е. образ произведения двух элементов равен сумме образов;
lg (a:b) = lg a - lg b - образ частного двух элементов равен разности образов;
lg a-1= -lg a - образ обратного элемента равен проти-воположному элементу;
lg 1 = 0 - образ единичного элемента равен нулевому элементу.
Следовательно, алгебры R+ и R гомоморфны.
В зависимости от свойств отображений определяются различные виды гомоморфизмов.
Определение7. Гомоморфизм j: А®В алгебры А в алгебру В называется:
1) Мономорфизмом (или вложением А в В), если отображение j -инъективно;
2) Эпиморфизмом (наложением А на В), если отображение j -сюръективно;
3) Изоморфизмом, если отображение j- биективно.
Если алгебра А изоморфна алгебре В, то пишут А @ В.
Определение 8.Гомоморфизм j: А®B алгебры А на себя называется:
1) Эндоморфизмом, если отображение j - инъективно:
2) Автоморфизмом, если отображение j - биективно;
Замечание:Отношение изоморфизма на множестве однотипных алгебр А, В, С, ... является отношением эквивален-тности, т. е.
а) "A, А@А - отношение @ рефлексивно,
б) "A, B (A @ B=>B@A)- отношение @ симметрично,
в) " А, В, С, ((А @ В) & (В @ С)) => (А @ С) - отношение @ транзитивно.
Следовательно, множество однотипных алгебр разбивается на классы эквивалентности. Изоморфные алгебры считаются различными моделями одной и той же абстрактной алгебры, т.е. изоморфные алгебры по существу считаются одинаковыми относительно свойств рассматриваемых операций на множествах-носителях и могут отличаться лишь обозначениями своих элементов и их названиями. Как мы не различаем экземпляры одного и того же литературного романа, напечатанные разными шрифтами и на разной бумаге, если интересуемся только содержанием романа, так и изоморфные алгебры рассматривают в математике как своеобразные копии друг друга, и часто, вместо изучения свойств некоторой алгебры, исследуют свойства изоморфной ей алгебры.
Понятие изоморфизма играет фундаментальную роль в математике. Это отношение позволяет классифицировать математические объекты с точки зрения свойств операций, заданных на множестве произвольной природы.
Указание 1. Для доказательства изоморфизма двух однотипных алгебр А и В нужно, либо указать конкретный изоморфизм, либо доказать существование такого изоморфизма. Исходя из определения понятия изоморфизма, укажем алгоритм решения задач такого типа. Он состоит из следующих шагов:
1. Задаем отображение j: А®В так, что " а, j(а) = b;
2. Доказываем, что отображение j является биекцией, т.е. j удовлетворяет двум условиям:
" b ÎВ, $ аÎА | j(а) =b - условие сюрьективности,
" a1, а2 Î A, (j(a1) = j(а2)) => (a1 = а2) - условие иньективности.
3.Проверяем, что j удовлетворяет условию гомоморфности (**).
Пример 11. Доказать, что алгебры <Z, +> и <2Z, +>, где 2Z -множество четных чисел, изоморфны. Для доказательства воспользуемся указанием 1.
1) Зададим отображение j: Z®2Z следующим образом:
"aÎZ, j(а) = 2а.
2) Докажем, что j - сюръективно. Для любого элемента 2nÎZ всегда можно указать его прообраз nÎZ, т.е. j - сюръективно.
Докажем, что j -инъективно Пусть "a, bÎZ, j(а) = j(b), значит 2а = 2b или а = b, т.е. j -инъективно.
3) Остается доказать, что j- гомоморфизм. Для этого нужно проверить выполнимость условия гомоморфности:
"a, bÎZ, j(а+b) = j(а) + j(b). (1)
Находим образ суммы, стоящей в левой части равенства (1). Получаем j(а+b) = 2(а + b) = 2а + 2b. (2)
Затем находим сумму образов, стоящих в правой части равенства (1):
j(а) + j(b)=2а + 2b.
Сравнивая (2) и (3), видим, что образ суммы равен сумме образов, т.е. выполняется условие (1). Следовательно, j - гомоморфизм.
Таким образом, все три шага алгоритма выполнены. Следовательно,
<Z, +> @<2Z, +>.
Указание 2. Для того, чтобы доказать, что алгебры А и_В неизоморфны нужно указать такое свойство, формулируемое в терминах некоторой операции одной из алгебр, которым другая алгебра не обладает.
Пример 12. Доказать, что алгебры <Q, +> и <Q, ×> неизоморфны.
Для доказательства воспользуемся указанием 2. Предположим, что эти алгебры изоморфны. В алгебре <Q, +> операция + обладает свойством: "aÎQ, а = а/2 + а/2, где а/2 - число рациональное.
Это же свойство в алгебре <Q, ×> записывается так : "bÎQ, b = Öb ×Öb.
Однако, не для всех рациональных b число Öb - рациональное. Следовательно, предположение о том, что данные алгебры изоморфны, неверно.