Головна

Гомоморфізми і ізоморфізми

безліч M разом із заданим на ньому операціями {j1, j2, ..., Jm} Називається алгеброю. позначення алгебри:

A = (M; j1, j2, ..., Jm),

де M називається основним безліччю (несучим безліччю, носієм), А S = {j1, j2, ..., Jm} - сигнатурою алгебри A.

Прикладом алгебри є півгрупа - безліч M із заданою на ньому однієї бінарної асоціативної операцією (позначається: ? ), Т. Е. A = {M; ? , Наприклад безліч натуральних чисел N з операцією додавання + на ньому, т. е. A = {N; +} Є полугруппой.

Типом алгебри A називається вектор арность операцій сигнатури. Наприклад, в алгебрі A =  де  - Безліч дійсних чисел, + і '- відповідно операції додавання і множення (така алгебра називається полем дійсних чисел), сигнатура S = {+,'} включає дві бінарні операції - додавання і множення. Тому тип даної алгебри (2, 2).

безліч M разом із заданими на ньому відносинами {R1, R2, ..., Rn} називається моделлю. Позначимо моделі:

M = (M; R1, R2, ..., Rn),

де M - Несе безліч (універсум), S = {R1, R2, ...,Rn} - Сигнатура моделі M. Наприклад, моделлю M1 є безліч M1 чисел з відносинами: "бути більше" (>) і "бути рівним" (=), т. е. M1= (M1; >, =), Або деякий безліч M2 людей з відношенням R - "Бути керівником", т. Е. M 2= (M2; R), і т.д.

безліч M разом із заданими на ньому операціями {j1, j2, ..., Jm} І відносинами {R1, R2, ..., Rn} називається алгебраїчної системою, або структурою алгебри. Позначення алгебраїчної структури:

M = (M; j1, j2, ..., Jm, R1, R2, ..., Rn).

Таким чином, алгебри - це алгебраїчні структури з порожнім безліччю відносин. Іншим окремим випадком алгебраїчних структур є моделі, т. Е. Безлічі, на яких задані тільки відносини.

Нехай між множинами A и B встановлено відповідність Г - відображення A в B, Т. Е. Г: A®B. Це означає, що кожному елементу а з A поставлений у відповідність Г єдиний елемент a з B, Т. Е. Г (а) = A. Нехай також на безлічі A задана операція j, на безлічі B - Операція y, обидві однаковою арності, наприклад обидві бінарні, так що a j b=c, a,b,cIA, І a y b = g, a, b, gIB. Таким чином, маємо дві алгебри (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; j1, j2, ..., Jm) І (B; y1, y2, ..., Ym), Відображення Г: A®B є гомоморфизмом алгебри (A; j1, j2, ..., Jm) В алгебру (B; y1, y2, ..., Ym), Якщо умови, аналогічні (3.1), Виконується для кожної пари операцій j1 і y1, ..., Jm і ym.

В силу взаємної однозначності відповідності Г: A®B при з-морфізма потужності основних множин ізоморфних алгебр рівні. Тому перевірка алгебр на ізоморфізм зводиться до перевірки умови гомоморфизма для кожної пари операцій і встановлення взаємної однозначності відповідності Г (рівній потужності множин A и B).

Аналогічно визначається гомоморфізм (ізоморфізм) множин з відносинами - моделей (A; R1, R2, ..., Rn) І (B; R1?, R2?, ..., Rn?).

Нехай, наприклад, на безлічі A задано бінарне відношення R(a, b), a,bIA, І на безлічі B - Бінарне відношення R? (a, b), a, bIB. Тоді відображення Г: A®B є гомоморфизмом моделі (A; R) В модель (B; R?), якщо для будь-якої пари елементів a, b з А такий, що a и b перебувають у відношенні R, Слід, що їх відображення г (а) = A і г (b) = B перебувають у відношенні R? (див. Рис 3.6), т. Е.

a R b тягне г (а) R? г (b) Для будь-яких a,bIA. (3.2)

 
 

Якщо при цьому відображення Г: A®B є взаємно однозначним відповідністю, воно називається изоморфизмом моделі (A; R) На модель (B; R?). У цьому випадку існує і зворотне відображення Г-1: B®A, Також є ізоморфізмом:

a R? b тягне Г-1(A) R Г-1(B) для будь-яких a, bIB.

При цьому моделі (A; R) І (B; R?) називаються ізоморфними.

важливим прикладом ізоморфних алгебр є так звані булеві алгебри, в тому числі:

1) (B (U); C, E, -) - булева алгебра множин;

Тут (b (U) - Безліч всіх підмножин (булеан) безлічі U;

{C, E, -} - відповідно операції перетину, об'єднання, доповнення над множинами;

2)(Bn; &, U, -) - булева алгебра довічних векторів довжини n.

тут Bn - Безліч всіх двійкових векторів довжини n, Т. Е.

Bn=B?B'...'B=Bn, де B= {0, 1};

{&, U, -} - операції логічного (покомпонентного) множення, додавання і доповнення відповідно, певні наступним чином:

для будь-яких векторів a = (a1, a2, ..., An) І b = (b1, b2, ..., Bn):

а) a & b = (a1& b1, a2& b2, ..., An& bn), при цьому  = 1, якщо =  = 1, і  = 0 - в будь-якому іншому випадку, т. Е.

б) aUb = (a1Ub1, a2Ub2, ..., AnUbn), при цьому  = 0, якщо =  = 0, і  = 1 - в будь-якому іншому випадку, т. Е.

в)

де

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

Приклад 1.нехай M1 - Безліч співробітників організації і R1 - Заданий на ньому відношення "бути старше" (  ); M2 - Кінцеве безліч натуральних чисел (обмежене, наприклад, числом 100) та R2 - Заданий на ньому відношення "бути більше" (>). Гомоморфності (ізоморфні) чи моделі:

A = (M1;  ) І B = (M2; >)?

1. Визначимо відображення Г: M1®M2 наступним чином: кожному співробітнику організації з M1 поставимо у відповідність Г число з M2, Відповідно до свого віку (в роках). Встановлене таким чином відображення Г: M1®M2 є гомоморфизмом моделей A = (M1;  ) І B = (M2; >), Так як очевидно виконується умова (3.2). Дійсно, якщо 'Іванов', 37 років, старше'Петрова', 26 років, т. Е.

'Іванов' 'Петрова'І г ('Іванов') = 37,

г ('Петров') = 26, то і 37> 26.

2. Однак встановлене відображення Г: M1®M2 не є ізоморфізмом моделей A = (M1;  ) І B = (M2; >), Так як не є в загальному випадку взаємно однозначним (якщо в організації є співробітники одного віку, наприклад 'Петров'26 років і'Сидоров' 26 років. В цьому випадку зворотне відповідність Г-1 не є відображенням, оскільки не функціонально (відсутній єдиність способу 26 на безліч співробітників організації).

Таким чином, задані моделі A = (M1;  ) І B = (M2; >) гомоморфності, але НЕ ізоморфні.

Приклад 2.нехай Zn - Безліч всіх цілих чисел, Z2n - Безліч всіх парних цілих чисел. Ізоморфні чи такі алгебри:

а) A = (Zn; +) І B = (Z2n; +) При відображенні Г: n®2n,

б) A = (Zn; +) І B = (Zn; +) При відображенні Г: n® (-n),

в) A = (Zn; ') І B = (Zn; ') При відображенні Г: n® (-n),

г) A = (Zn; ') І B = (Z2n; ') При відображенні Г: n®2n,

д) A = (Zn; +, ') І B = (Z2n; +, ') При відображенні Г: n®2n,

де +, '- операції арифметичного додавання і множення відповідно.

а) Умова гомоморфизма для алгебр A = (Zn; +) І B = (Z2n; +) Проілюстровано на рис. 3.7, де зображені два безлічі Zn, Z2n і в Zn виділені довільні два елементи a, b.

Відповідно до ле-виття частиною умови (3.1) гомоморфизма для бінару-них операцій виконаємо над a и b операцію складання + алгебри A і відобразимо результат с=a+b в безлічі Z2n алгебри B. При заданий-ном відображенні Г: n®2n елементу з мно-дружність Zn відповідає елемент 2с безлічі Z2n, Т. Е. Ліва частина умови (3.1) набуде вигляду:

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

Права частина умови (3.1) вимагає спочатку відображення елементів a, b в безліч Z2n (Отримуємо г (а) = 2а, Г (b) = 2b), А потім здійснення над їх відображеннями операції додавання (+) алгебри B, т. Е. Права частина умови (3.1) набуде вигляду:

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

Таким чином, умова гомоморфизма (3.1) для алгебр A = (Zn; +) І B = (Z2n; +) При відображенні Г: n®2n має вигляд:

г (a+b) = Г (а) + Г (b), Т. Е.

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

Так як дана умова виконується, алгебри A і B гомо- морфних, А в силу взаємної однозначності відображення Г: n®2n вони та ізоморфні.

б) Відображення Г: n® (-n) Для алгебр A = (Zn; +) І B = (Zn; +) Є ізоморфізмом. Дійсно, умова (3.1) має вигляд:

- (a+b) = (-a) + (-b)

і, крім того, відображення Г: n® (-n) (Кожному цілому числу n в алгебрі A відповідає той же ціле число, але з протилежним знаком (-n) В алгебрі B) - взаємно однозначно.

в) Відображення Г: n® (-n) Для алгебр A = (Zn; ') І B = (Zn; ') Не є ні изоморфизмом, ні гомоморфизмом, тому що не виконується умова (3.1) гомоморфизма:

- (a?b) ? (-a) ? (-b).

г) Алгебри A = (Zn; ') І B = (Z2n; ') Не є гомоморфності, а значить, і ізоморфними при відображенні Г: n®2n, Оскільки для них не виконується умова гомоморфизма (3.1):

2 (a?b) ? 2a?2b.

д) Для алгебр A = (Zn; +, ') І B = (Z2n; +, ') При відображенні Г: n®2n умова гомоморфизма виконується для операцій додавання і не виконується для операцій множення [см. а) і г)], тому алгебри A і B не є гомоморфності.

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

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

log (a?b) =log a + log b

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

Приклад 4.Ізоморфні чи булеві алгебри множин (b (U); C, E, -) і (b (U?); C, E, -), утворені двома різними множинами U и U? однакової потужності?

Алгебри (b (U); C, E, -) і (b (U?); C, E, -), де |U| = |U? |, ізоморфні, так як операції у них просто однакові, а відображенням Г може служити будь-який взаємно однозначна відповідність між U и U?. Наприклад, безлічі U= {1, 2, 3} і U? = {a, b, c} Однакової потужності, |U| = |U? | = 3. Тоді відображення Г: {1®a, 2®b, 3®c} Задає ізоморфізм алгебр (b (U); C, E, -) і (b (U?); C, E, -).

Приклад 5.Нехай алгебри A = (N; +) І B = (N3; A), де A - додавання за модулем 3 і N3= {0, 1, 2}, і відображення Г: N®N3 визначене в такий спосіб: г (n) Дорівнює залишку від ділення n на 3. Інакше кажучи,

якщо n= 3a+b, де b<3, то г (n) =b.

Наприклад, 2A1 = 0, 2A2 = 1 і т. Д.

Гомоморфності (ізоморфні) чи алгебри A = (N; +) І B = (N3; A)?

нехай n1= 3a1+b1 и n2= 3a2+b2 - Два довільних натуральних числа з N; b1, b2<3. перевіримо умову (3.1):

г (n1+n2) = Г (n1) A г (n2),

г (3a1+b1+3a2+b2) = Г (3a1+b1) A г (3a2+b2),

г (b1+b2) = Г (b1) A г (b2),

г (b1+b2) =b1Ab2.

Очевидно ця умова виконується. Наприклад, нехай n1= 56, n2= 37. Тоді 56 = 3?18 + 2, 37 = 3?12 + 1; підставивши в отримане умова гомо-морфізма, переконаємося в його здійсненності:

г (2 + 1) = 2A1,

0 = 0.

Таким чином, відображення Г - гомоморфізм. Але воно не є ізоморфізмом, так як немає взаємної однозначності для Г: N®N3.

Цей приклад показує, що можливий гомоморфізм нескінченної алгебри (т. Е. Алгебри з нескінченним основним безліччю) в конеч-ву алгебру.

Приклад 6. Ізоморфні чи моделі (b (U); I) і (B3; ?), де:

b (U) - Безліч всіх підмножин (булеан) безлічі U= {a, b, c};

B3 - Безліч всіх двійкових векторів довжини 3;

I - відношення несуворого включення;

? - відношення несуворого порядку над векторами таке, що для двох довічних векторів t = (t1, t2, t3) І s = (s1, s2, s3);

t ? s, т. е. (t1, t2, t3) ? (s1, s2, s3);

якщо і тільки якщо t1? s1, t2? s2, t3? s3.

Наприклад, (100) ? (101), але (101) і (011) непорівнянні.

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

B3= {(000), (001), (010), (011), (100), (101), (110), (111)} (для спрощена-ня позначень коми між компонентами векторів опущені).

Потужності цих множин рівні: | b (U) | = |B3| = 8. Відображення Г: b (U) ®B3 є взаємно однозначним (див. також приклад 4 з параграфа 3.1):

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

Залишається показати, що умова гомоморфизма (3.2) виконується для заданих відносин:

АIB тягне г (А) ? г (B) Для будь-яких А,ВIb (U); A,BIU.

Сенс цієї умови полягає у наступному. Якщо два безлічі A, B з b (U) Можна порівняти по відношенню включення I, то відпо-ють їм вектори t і s з B3 такі, що г (А) = T і г (В) = S, можна порівняти по відношенню нерівності ? і з того, що АIВ, Випливає, що t ? s.

Очевидно, що дана умова виконується. Наприклад, з того, що {a} I {a, c} Слід (100) ? (101). А в силу взаємної однозначності відображення Г справедливо і зворотне, наприклад з того, що (010) ? (111), слід, що {b} I {a, b, c}:

t ? s тягне Г-1(T) I Г-1(S) для будь-яких t, sIB3.

Таким чином, встановлений відображення Г: b (U) ®B3 є ізоморфізмом; моделі (b (U); I) і (B3; ?) ізоморфні. Відзначимо, що ізоморфними будуть і інші аналогічні моделі (b (U); I) і (Bn; ?), якщо потужність несе безлічі |U| і довжина векторів n з Bn рівні, т. е. |U| =n. У цьому випадку виконується взаємно однозначна відповідність

Г: b (U) ®Bn , | B (U) | = |Bn|.

Приклад 7.Використовуючи встановлений у попередньому прикладі взаємно однозначна відповідність між множинами з b (U), Де U= {a, b, c}, І двійковими векторами довжини 3 і B3, Проілюструвати на прикладі конкретних множин А= {a, c} і B= {b, c}, A,BIU, Ізоморфізм між булеві алгебра множин (b (U); C, E, -), |U| = 3, і довічних векторів довжини 3 (B3; &, U, -).

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

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

при n= 3 | b (U) | = |B3| = 8:

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

Встановлене в прикладі 6 взаємно однозначна відповідність Г: b (U) ®B3 для заданих множин А= {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,BIU:

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

б) г (АEВ) = Г ({a, c} E {b, c}) = Г ({a, b, c}) = (111) = (101) U (011) = aUb;

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

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

а) г (АCВ) = A & b;

б) г (АEВ) = AUb;

в) .

Алгебри (b (U); C, E, -) і (B3; &, U, -) гомоморфності, і відображення множин Г: b (U) ®B3 взаємно однозначно. Отже, дані алгебри також і ізоморфні при даному відображенні.

Питання для самоперевірки та вправи:

1. нехай M2n - Безліч ступенів двійки; M2n- Безліч парних чисел, nIN. Гомоморфності (ізоморфні) чи алгебри A і B, якщо:

а) A = (N; +) І B = (M2n; +) При відображенні Г: n®2n,

б) A = (N; +) І B = (M2n; ') При відображенні Г: n®2n,

в) A = (N; +) І B = (M2n; +) При відображенні Г: n®2n,

г) A = (N; ') І B = (M2n; ') При відображенні Г: n®2n,

д) A = (N; +, ') І B = (M2n; +, ') При відображенні Г: n®2n?

2. Гомоморфності (ізоморфні) чи алгебри A і B при відображенні Г: N®N5, Якщо:

а) A = (N; +), B = (N5; A);

б) A = (N; '), B = (N5; A);

в) A = (N; +, '), B = (N5; A, A);

Примітки: а) N5= {0, 1, 2, 3, 4} I N;

б) відображення Г: N®N5 таке, що для nIN, n= 5a+b, де b<5, г (n) =b;

в) бінарні операції додавання і множення по модулю 5 (A, A) такі, що:

 - Залишки від ділення на 5 відповідно суми і твори чисел

г) при перевірці умови гомоморфизма зручно уявити:

n1= 5a1+b1, n2= 5a2+b2.

3. Чи є для заданої множини U алгебра (b (U); C, E) изоморфной алгебри (b (U); C, E) при відображенні Г: А®  , де А - Елемент безлічі b (U),  - Його доповнення.

4. Нехай алгебри A = (N4; A) і B = (N4; A '), де N4= {0, 1, 2, 3} і операції A і A 'задані таблицями Келі, (рис. 3.8).

Чи є відображення

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

5. У булевої алгебри довічних векторів довжини 6 (B6; &, U, -) виконати операції над векторами a і b, певні на стор. 57, якщо:

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

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

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

6. Задати таблицями Келі операції булевих алгебр:

а) (b (U); C, E, -) при |U| = 2;

б) (B2; &, U, -).

7. Проілюструвати на конкретному прикладі ізоморфізм булевих алгебр (b (U); C, E, -) і (Bn; &, U, -) на прикладі множин A,BIU, Якщо:

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}.

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

 операції |  Підручники і навчальні посібники


 Основні позначення |  Діаграми (кола) Ейлера-Венна |  докази |  Вектори, прямі твори, проекції векторів |  Бінарні відносини. Основні визначення |  Властивості бінарних відносин |  Еквівалентність і порядок |  Операції над бінарними відносинами |  Відповідності та їх властивості. Основні визначення |  Функції та відображення |

© 2016-2022  um.co.ua - учбові матеріали та реферати