Гомоморфизмы и изоморфизмы

Множество M вместе с заданным на нем операциями {j₁, j₂, …,j _m } называется алгеброй. Обозначение алгебры:

A=(M; j₁, j₂, …,j _m),

где M называется основным множеством (несущим множеством, носителем), а S={j₁, j₂, …,j _m } – сигнатурой алгебры A.

Примером алгебры является полугруппа – множество M с заданной на нем одной бинарной ассоциативной операцией (обозначается: ×), т.е. A={ M; ×, например множество натуральных чисел N с операцией сложения + на нем, т.е. A={ N; +} является полугруппой.

Типом алгебры A называется вектор арностей операций сигнатуры. Например, в алгебре A= где – множество действительных чисел, + и ´ – соответственно операции сложения и умножения (такая алгебра называется полем действительных чисел), сигнатура S={+, ´} включает две бинарные операции – сложение и умножение. Поэтому тип данной алгебры (2, 2).

Множество M вместе с заданными на нем отношениями { R ₁, R ₂, …, R_n } называется моделью. Обозначим модели:

M =(M; R ₁, R ₂, …, R_n),

где M – несущее множество (универсум), S={ R ₁, R ₂, …, R_n } – сигнатура модели M. Например, моделью M₁ является множество M ₁ чисел с отношениями: “быть больше” (>) и “быть равным” (=), т.е. M₁=(M ₁; >, =), или некоторое множество M₂ людей с отношением R – “быть руководителем”, т.е. M ₂=(M ₂; R), и т.д.

Множество M вместе с заданными на нем операциями {j₁, j₂, …,j _m } и отношениями { R ₁, R ₂, …, R_n } называется алгебраической системой, или алгебраической структурой. Обозначение алгебраической структуры:

M=(M; j₁, j₂, …, j _m, R ₁, R ₂, …, R_n).

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

Пусть между множествами A и B установлено соответствие Г – отображение A в B, т.е. Г: A ® B. Это означает, что каждому элементу а из A поставлен в соответствие Г единственный элемент a из B, т.е. Г(а)=a. Пусть также на множестве A задана операция j, на множестве B – операция y, обе одинаковой арности, например обе бинарные, так что a j b = c, a, b, c Î A, и a y b=g, a,b,gÎ B. Таким образом, имеем две алгебры (A; j) и (B; y).

Тогда отображение Г: A ® B называется гомоморфизмом алгебры (A; j) в алгебру (B; y), если выполняется условие:

Г(a j b)=Г(а) y Г(b). (3.1)

Если при этом отображение Г: A ® B является взаимно однозначным соответствием, оно называется изоморфизмом алгебры (A; j) на алгеб-ру (B; y). В этом случае существует обратное отображение Г^–1: B ® A, также взаимно однозначное:

Г^–1(a y b)=Г^–1(a) j Г^–1(b).

Отображение Г^–1 – это, в свою очередь, изоморфизм B на A. Итак, если существует изоморфизм A на B, то существует изоморфизм B на A. При этом алгебры (A; j) и (B; y) называются изоморфными.

В более общем случае, если на множествах A и B заданы несколько операций соответственно (A; j₁, j₂, …, j _m) и (B; y₁, y₂, …, y _m), отображение Г: A ® B является гомоморфизмом алгебры (A; j₁, j₂, …, j _m) в алгебру (B; y₁, y₂, …, y _m), если условия, аналогичные (3.1), выполняется для каждой пары операций j₁ и y₁, …, j _m и y _m.

В силу взаимной однозначности соответствия Г: A ® B при изо-морфизме мощности основных множеств изоморфных алгебр равны. Поэтому проверка алгебр на изоморфизм сводится к проверке условия гомоморфизма для каждой пары операций и установления взаимной однозначности соответствия Г (равной мощности множеств A и B).

Аналогично определяется гомоморфизм (изоморфизм) множеств с отношениями – моделей (A; R ₁, R ₂, …, R_n) и (B; R ₁¢, R ₂¢, …, R_n ¢).

Пусть, например, на множестве A задано бинарное отношение R (a, b), a, b Î A, и на множестве B – бинарное отношение R ¢(a, b), a,bÎ B. Тогда отображение Г: A ® B является гомоморфизмом модели (A; R) в модель (B; R ¢), если для любой пары элементов a, b из А такой, что a и b находятся в отношении R, следует, что их отображения Г(а)=a и Г(b)=b находятся в отношении R ¢ (см. рис 3.6), т.е.

a R b влечет Г(а) R ¢ Г(b) для любых a, b Î A. (3.2)

Если при этом отображение Г: A ® B является взаимно однозначным соответствием, оно называется изоморфизмом модели (A; R) на модель (B; R ¢). В этом случае существует и обратное отображение Г^–1: B ® A, также являющееся изоморфизмом:

a R ¢ b влечет Г^–1(a) R Г^–1(b) для любых a,bÎ B.

При этом модели (A; R) и (B; R ¢) называются изоморфными.

Важным примером изоморфных алгебр являются так называемые булевы алгебры, в том числе:

1) (b(U); Ç, È, –) – булева алгебра множеств;

Здесь (b(U) – множество всех подмножеств (булеан) множества U;

{Ç, È, –} – соответственно операции пересечения, объединения, дополнения над множествами;

2) (B_n; &, Ú, –) – булева алгебра двоичных векторов длины n.

Здесь B_n – множество всех двоичных векторов длины n, т.е.

B_n = B ´ B ´…´ B = Bⁿ, где B ={0, 1};

{&, Ú, –} – операции логического (покомпонентного) умножения, сложения и дополнения соответственно, определенные следующим образом:

для любых векторов a=(a₁, a₂, …, a _n) и b=(b₁, b₂, …, b _n):

а) a&b=(a₁&b₁, a₂&b₂, …, a _n &b _n), при этом =1, если = =1, и =0 – в любом другом случае, т.е.

б) aÚb=(a₁Úb₁, a₂Úb₂, …, a _n Úb _n), при этом =0, если = =0, и =1 – в любом другом случае, т.е.

в)

где

Изоморфизм булевых алгебр широко используется в компьютерных вычислениях, например, при необходимости выполнения операций над множествами с применением соответствующих и легко реализуемых на компьютере поразрядных операций над соответствующими двоич-ными векторами.

Пример 1. Пусть M ₁ – множество сотрудников организации и R ₁ – заданное на нем отношение “быть старше” (); M ₂ – конечное множество натуральных чисел (ограниченное, например, числом 100) и R ₂ – заданное на нем отношение “быть больше” (>). Гомоморфны (изоморфны) ли модели:

A=(M ₁; ) и B=(M ₂; >)?

1. Определим отображение Г: M ₁® M ₂ следующим образом: каждому сотруднику организации из M ₁ поставим в соответствие Г число из M ₂, соответствующим его возрасту (в годах). Установленное таким образом отображение Г: M ₁® M ₂ является гомоморфизмом моделей A=(M ₁; ) и B=(M ₂; >), так как очевидно выполняется условие (3.2). Действительно, если ‘ Иванов ’, 37 лет, старше ‘ Петрова ’, 26 лет, т.е.

‘ Иванов ’ ‘ Петрова ’ и Г(‘ Иванов ’)=37,

Г(‘ Петров ’)=26, то и 37>26.

2. Однако установленное отображение Г: M ₁® M ₂ не является изоморфизмом моделей A=(M ₁; ) и B=(M ₂; >), так как не является в общем случае взаимно однозначным (если в организации имеются сотрудники одного возраста, например ‘ Петров ’ 26 лет и ‘ Сидоров ’ 26 лет. В этом случае обратное соответствие Г^–1 не является отображением, поскольку не функционально (отсутствует единственность образа 26 на множество сотрудников организации).

Таким образом, заданные модели A=(M ₁; ) и B=(M ₂; >) гомоморфны, но не изоморфны.

Пример 2. Пусть Z_n – множество всех целых чисел, Z _{2 n} – множество всех четных целых чисел. Изоморфны ли следующие алгебры:

а) A=(Z_n;+) и B=(Z _{2 n}; +) при отображении Г: n ®2 n,

б) A=(Z_n;+) и B=(Z_n; +) при отображении Г: n ®(– n),

в) A=(Z_n; ´) и B=(Z_n; ´) при отображении Г: n ®(– n),

г) A=(Z_n; ´) и B=(Z _{2 n}; ´) при отображении Г: n ®2 n,

д) A=(Z_n; +, ´) и B=(Z _{2 n}; +, ´) при отображении Г: n ®2 n,

где +, ´ – операции арифметического сложения и умножения соответственно.

а) Условие гомоморфизма для алгебр A=(Z_n;+) и B=(Z _{2 n}; +) проиллюстрировано на рис. 3.7, где изображены два множества Z_n, Z _{2 n} и в Z_n выделены произвольные два элемента a, b.

В соответствии с ле-вой частью условия (3.1) гомоморфизма для бинар-ных операций выполним над a и b операцию сложения + алгебры A и отобразим результат с = a + b в множестве Z _{2 n} алгебры B. При задан-ном отображении Г: n ®2 n элементу с мно-жества Z_n соответствует элемент 2 с множества Z _{2 n}, т.е. левая часть условия (3.1) примет вид:

Г(a + b)=2(a + b).

Правая часть условия (3.1) требует сначала отображения элементов a, b в множество Z _{2 n} (получаем Г(а)=2 а, Г(b)=2 b), а затем осуществления над их отображениями операции сложения (+) алгебры B, т.е. правая часть условия (3.1) примет вид:

Г(а)+Г(b)=2 a +2 b.

Таким образом, условие гомоморфизма (3.1) для алгебр A=(Z_n;+) и B=(Z _{2 n}; +) при отображении Г: n ®2 n имеет вид:

Г(a + b)=Г(а)+Г(b), т.е.

2(a + b)=2 a +2 b.

Так как данное условие выполняется, алгебры A и B гомо- морфны, а в силу взаимной однозначности отображения Г: n ®2 n они и изоморфны.

б) Отображение Г: n ®(– n) для алгебр A=(Z_n;+) и B=(Z_n; +) является изоморфизмом. Действительно, условие (3.1) имеет вид:

–(a + b)=(– a)+(– b)

и, кроме того, отображение Г: n ®(– n) (каждому целому числу n в алгебре A соответствует то же целое число, но с противоположным знаком (– n) в алгебре B) – взаимно однозначно.

в) Отображение Г: n ®(– n) для алгебр A=(Z_n; ´) и B=(Z_n; ´) не является ни изоморфизмом, ни гомоморфизмом, так как не выполняется условие (3.1) гомоморфизма:

– (a × b)¹(– a) × (– b).

г) Алгебры A=(Z_n; ´) и B=(Z _{2 n}; ´) не являются гомоморфными, а значит, и изоморфными при отображении Г: n ®2 n, поскольку для них не выполняется условие гомоморфизма (3.1):

2(a × b)¹ 2 a × 2 b.

д) Для алгебр A=(Z_n; +, ´) и B=(Z _{2 n}; +, ´) при отображении Г: n ®2 n условие гомоморфизма выполняется для операций сложения и не выполняется для операций умножения [см. а) и г)], поэтому алгебры A и B не являются гомоморфными.

Пример 3. Гомоморфны (изоморфны) ли алгебры и при отображении Г: a ® loga множества действительных и положительных чисел соответственно)?

Алгебры и изоморфны при заданном отображении Г: a ® log a, так как выполняется условие (3.1):

log (a × b)= log a + log b

и отображение Г: a ® loga взаимно однозначно. В частности, этот принцип (изоморфизм указанных алгебр при данном отображении) используется при вычислениях с помощью логарифмической линейки.

Пример 4. Изоморфны ли булевы алгебры множеств (b(U); Ç, È, –) и (b(U ¢); Ç, È, –), образованные двумя различными множествами U и U ¢ одинаковой мощности?

Алгебры (b(U); Ç, È, –) и (b(U ¢); Ç, È, –), где | U |=| U ¢|, изоморфны, так как операции у них просто одинаковы, а отображением Г может служить любое взаимно однозначное соответствие между U и U ¢. Например, множества U ={1, 2, 3} и U ¢={ a, b, c } одинаковой мощности, | U |=| U ¢|=3. Тогда отображение Г: {1® a, 2® b, 3® c } задает изоморфизм алгебр (b(U); Ç, È, –) и (b(U ¢); Ç, È, –).

Пример 5. Пусть алгебры A=(N; +) и B=(N ₃; Å), где Å – сложение по модулю 3 и N ₃={0, 1, 2}, и отображение Г: N ® N ₃ определено следующим образом: Г(n) равно остатку от деления n на 3. Иначе говоря,

Если n =3 a + b, где b <3, то Г(n)= b.

Например, 2Å1=0, 2Å2=1 и т.д.

Гомоморфны (изоморфны) ли алгебры A=(N; +) и B=(N ₃; Å)?

Пусть n ₁=3 a ₁+ b ₁ и n ₂=3 a ₂+ b ₂ – два произвольных натуральных числа из N; b ₁, b ₂<3. Проверим условие (3.1):

Г(n ₁+ n ₂)=Г(n ₁) Å Г(n ₂),

Г(3 a ₁+ b ₁+3 a ₂+ b ₂)=Г(3 a ₁+ b ₁) Å Г(3 a ₂+ b ₂),

Г(b ₁+ b ₂)=Г(b ₁) Å Г(b ₂),

Г(b ₁+ b ₂)= b ₁Å b ₂.

Очевидно это условие выполняется. Например, пусть n ₁=56, n ₂=37. Тогда 56=3 × 18+2, 37=3 × 12+1; подставив в полученное условие гомо-морфизма, убедимся в его выполнимости:

Г(2+1)=2Å1,

0=0.

Таким образом, отображение Г – гомоморфизм. Но оно не является изоморфизмом, так как нет взаимной однозначности для Г: N ® N ₃.

Этот пример показывает, что возможен гомоморфизм бесконечной алгебры (т.е. алгебры с бесконечным основным множеством) в конеч-ную алгебру.

Пример 6. Изоморфны ли модели (b(U); Í) и (B ₃; £), где:

b(U) – множество всех подмножеств (булеан) множества U ={ a, b, c };

B ₃ – множество всех двоичных векторов длины 3;

Í – отношение нестрогого включения;

£ – отношение нестрогого порядка над векторами такое, что для двух двоичных векторов t=(t₁, t₂, t₃) и s=(s₁, s₂, s₃);

t£s, т.е. (t₁, t₂, t₃)£(s₁, s₂, s₃);

если и только если t₁£s₁, t₂£s₂, t₃£s₃.

Например, (100)£(101), но (101) и (011) несравнимы.

b(U)={Æ, { a }, { b }, { c }, { a, b }, { a, c }, { b, c }, { a, b, c }};

B ₃={(000), (001), (010), (011), (100), (101), (110), (111)} (для упроще-ния обозначений запятые между компонентами векторов опущены).

Мощности этих множеств равны: |b(U)|=| B ₃|=8. Отображение Г: b(U)® B ₃ является взаимно однозначным (см. также пример 4 из параграфа 3.1):

Г: Æ®(000), { a }®(100), { b }®(010), …, { a, c }®(101), …, { a, b, c }®(111).

Остается показать, что условие гомоморфизма (3.2) выполняется для заданных отношений:

А Í B влечет Г(А)£Г(B) для любых А, В Îb(U); A, B Í U.

Смысл этого условия заключатся в следующем. Если два множества A, B из b(U) сравнимы по отношению включения Í, то соответст-вующие им векторы t и s из B ₃ такие, что Г(А)=t и Г(В)=s, сравнимы по отношению неравенства £ и из того, что А Í В, следует, что t£s.

Очевидно, что данное условие выполняется. Например, из того, что { a }Í{ a, c } следует (100)£(101). А в силу взаимной однозначности отображения Г справедливо и обратное, например из того, что (010)£(111), следует, что { b }Í{ a, b, c }:

t£s влечет Г^–1(t)Í Г^–1(s) для любых t,sÎ B ₃.

Таким образом, установленное отображение Г: b(U)® B ₃ является изоморфизмом; модели (b(U); Í) и (B ₃; £) изоморфны. Отметим, что изоморфными будут и другие аналогичные модели (b(U); Í) и (B_n; £), если мощность несущего множества | U | и длина векторов n из B_n равны, т.е. | U |= n. В этом случае выполняется взаимно однозначное соответствие

Г: b(U)® B_n, |b(U)|=| B_n |.

Пример 7. Используя установленное в предыдущем примере взаимно однозначное соответствие между множествами из b(U), где U ={ a, b, c }, и двоичными векторами длины 3 и B ₃, проиллюстрировать на примере конкретных множеств А ={ a, c } и B ={ b, c }, A, B Í U, изоморфизм между булевыми алгебрами множеств (b(U); Ç, È, –), | U |=3, и двоичных векторов длины 3 (B ₃; &, Ú, –).

Для U ={ a, b, c }:

b(U)={Æ, { a }, { b }, { c }, { a, b }, { a, c }, { b, c }, { a, b, c }}.

При n =3 |b(U)|=| B ₃|=8:

B ₃={(000), (001), (010), (011), (100), (101), (110), (111)}.

Установленное в примере 6 взаимно однозначное соответствие Г: b(U)® B ₃ для заданных множеств А ={ a, c } и B ={ b, c } имеет вид:

1) Г(А)=Г({ a, c })=(101)=a, Г(В)=Г({ b, c })=(011)=b и наоборот

Г^–1(a)=Г^–1((101))={ a, c }; Г^–1(b)=Г^–1((011))={ b, c }.

2) Подтвердим теперь выполнение условия гомоморфизма для каждой пары операций булевых алгебр на примере множеств A, B Í U:

а) Г(А Ç В)=Г({ a, c }Ç{ b, c })=Г({ c })=(001)=(101)&(011)=a&b;

б) Г(А È В)=Г({ a, c }È{ b, c })=Г({ a, b, c })=(111)=(101)Ú(011)=aÚb;

в) Г(U \ A)=Г({ a, b, c }\{ a, c })=Г({ b })=(010)= .

Таким образом, для трех пар булевых операций имеет место выполнение условия гомоморфизма:

а) Г(А Ç В)=a&b;

б) Г(А È В)=aÚb;

в) .

Алгебры (b(U); Ç, È, –) и (B ₃; &, Ú, –) гомоморфны, и отображение множеств Г: b(U)® B ₃ взаимно однозначно. Следовательно, данные алгебры также и изоморфны при данном отображении.

Вопросы для самопроверки и упражнения:

1. Пусть M ₂ n – множество степеней двойки; M ₂ n – множество четных чисел, n Î N. Гомоморфны (изоморфны) ли алгебры A и B, если:

а) A=(N; +) и B=(M ₂ n; +) при отображении Г: n ®2 ⁿ,

б) A=(N; +) и B=(M ₂ n; ´) при отображении Г: n ®2 ⁿ,

в) A=(N; +) и B=(M ₂ n; +) при отображении Г: n ®2 n,

г) A=(N; ´) и B=(M ₂ n; ´) при отображении Г: n ®2 n,

д) A=(N; +, ´) и B=(M ₂ n; +, ´) при отображении Г: n ®2 n?

2. Гомоморфны (изоморфны) ли алгебры A и B при отображении Г: N ® N ₅, если:

а) A=(N; +), B=(N ₅; Å);

б) A=(N; ´), B=(N ₅; Ä);

в) A=(N; +, ´), B=(N ₅; Å, Ä);

Примечания: а) N ₅={0, 1, 2, 3, 4}Ì N;

б) отображение Г: N ® N ₅ такое, что для n Î N, n =5 a + b, где b <5, Г(n)= b;

в) бинарные операции сложения и умножения по модулю 5 (Å, Ä) такие, что:

– остатки от деления на 5 соответственно суммы и произведения чисел

г) при проверке условия гомоморфизма удобно представить:

n ₁=5 a ₁+ b ₁, n ₂=5 a ₂+ b ₂.

3. Является ли для заданного множества U алгебра (b(U); Ç, È) изоморфной алгебре (b(U); Ç, È) при отображении Г: А ® , где А – элемент множества b(U), – его дополнение.

4. Пусть алгебры A=(N ₄; Ä) и B=(N ₄; Ä′), где N ₄={0, 1, 2, 3} и операции Ä и Ä′ заданы таблицами Кэли, (рис. 3.8).

Является ли отображение

Г: 0®1, 1®2, 2®0, 3®3 гомоморфизмом, изоморфизмом?

5. В булевой алгебре двоичных векторов длины 6 (B ₆; &, Ú, –) выполнить операции над векторами a и b, определенные на стр. 57, если:

а) a=(101100), b=(100101);

б) a=(011010), b=(010010);

в) a=(001101), b=(010101).

6. Задать таблицами Кэли операции булевых алгебр:

а) (b(U); Ç, È, –) при | U |=2;

б) (B ₂; &, Ú, –).

7. Проиллюстрировать на конкретном примере изоморфизм булевых алгебр (b(U); Ç, È, –) и (B_n; &, Ú, –) на примере множеств A, B Í U, если:

a) A ={2, 3, 6}, B ={ 1, 2, 4, 6}, U ={1, 2, 3, 4, 5, 6};

б) A ={ a, b, c, d, f }, B ={ b, c, e, f }, U ={ a, b, c, d, e, f };

в) A ={1, 2, 4 6}, B ={2, 3, 5, 6}, U ={1, 2, 3, 4, 5, 6};

г) A ={ a, c, d, e }, B ={ a, b, c, f }, U ={ a, b, c, d, e, f }.

СПИСОК ЛИТЕРАТУРЫ