Головна |
Гомоморфізми і ізоморфізмибезліч 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}. СПИСОК ЛІТЕРАТУРИ операції | Підручники і навчальні посібники Основні позначення | Діаграми (кола) Ейлера-Венна | докази | Вектори, прямі твори, проекції векторів | Бінарні відносини. Основні визначення | Властивості бінарних відносин | Еквівалентність і порядок | Операції над бінарними відносинами | Відповідності та їх властивості. Основні визначення | Функції та відображення | |