Фактор-алгебри

Означення 9. Нехай G = (А,W) – алгебра, RÍA², R – конгруенція. Фактор-алгеброю алгебри G за конгруенцією R (позначається G/R) називається алгебра, що визначається таким чином. Носієм цієї алгебри є фактор-множина множини А за відношенням R (А/R). За кожною операцією fⁿ з сигнатури W алгебри G побудуємо операцію (для якої залишаємо те саме ім’я fⁿ): нехай А₁,…,А_nÎА/R; нехай A₁=[a₁],…,A_n=[a_n], де a₁ÎA₁, …, a_nÎA_n; покладемо fⁿ([a₁],…,[a_n])=[fⁿ(a₁,…,a_n)]. Позначимо множину усіх побудованих таким чином операцій через W. G/R=(А/R,W). Покажемо, що операції на множині А/R визначені коректно у тому сенсі, що результат операції (тобто fⁿ([a₁],…,[a_n])) не залежить від вибору представників класів А₁,…,А_n. Це означає, що треба довести: a₁ÎA₁, …, a_nÎA_n, b₁ÎA₁,..,b_nÎA_n Þ [fⁿ(a₁,…,a_n)]=[fⁿ(b₁,…,b_n)]. Маємо: a₁ÎA₁, …, a_nÎA_n, b₁ÎA₁,..,b_nÎA_n Þ a₁Rb₁,…, a_nRb_n Þ fⁿ(a₁,…,a_n)Rfⁿ(b₁,…,b_n) (використано стабільність відношення R у алгебрі G) Þ [fⁿ(a₁,…,a_n)]=[fⁿ(b₁,…,b_n)].

Розглянемо приклад побудови фактор-алгебри за конгруенцією. Нехай на носієві алгебри G=(N,+,´) задано бінарне відношення R={<x,y>| (x-y) ділиться на 3}. Покажемо, що R – конгруенція. Відношення R рефлексивне. Дійсно: xÎN Þ (x-x)=0 Þ 0 ділиться на 3 Þ <x,x>ÎR. Відношення R симетричне. Дійсно: <x,y>ÎR Þ (x-y) ділиться на 3 Þ x-y=3k для деякого цілого k Þ y-x=3(-k), (-k) ціле Þ y-x ділиться на 3 Þ <y,x>ÎR. Відношення R транзитивне. Дійсно: <x,y>ÎR, <y,z>ÎR Þ (x-y) ділиться на 3, (y-z) ділиться на 3 Þ x-y=3k для деякого цілого k, y-z=3m для деякого цілого m Þ x-z=3(k+m), (k+m) ціле Þ (x-z) ділиться на 3 Þ <x,z>ÎR. Таким чином, R – відношення еквівалентності. Покажемо стабільність R відносно операцій сигнатури алгебри G. Запишемо умову стабільності R відносно бінарної операції +:

xRy, uRv Þ (x+u)R(y+v).

Доведемо, що дана умова виконується. Маємо: xRy, uRv Þ (x-y) ділиться на 3, (u-v) ділиться на 3 Þ x-y=3k для деякого цілого k, u-v=3m для деякого цілого m Þ x=y+3k, u=v+3m Þ x+u=(y+v)+3(k+m) Þ (x+u)-(y+v)=3(k+m) для цілого (k+m) Þ (x+u)-(y+v) ділиться на 3 Þ (x+u)R(y+v). Отже, R стабільне відносно операції +. Тепер запишемо умову стабільності R відносно бінарної операції ´:

xRy, uRv Þ (x´u)R(y´v).

Доведемо, що ця умова виконується. Маємо: xRy, uRv Þ (x-y) ділиться на 3, (u-v) ділиться на 3 Þ x-y=3k для деякого цілого k, u-v=3m для деякого цілого m Þ x=y+3k, u=v+3m Þ x´u=(y+3k)(v+3m)=(y´v)+3(kv+ym+3km) Þ (x´u)-(y´v)=3(kv+ym+km) Þ (x´u)-(y´v) ділиться на 3 Þ (x´u)R(y´v). Отже, R стабільне відносно операції ´. Оскільки R стабільне відносно кожної операції сигнатури алгебри G, R стабільне у G. Оскільки R є відношенням еквівалентності й стабільне у алгебрі G, то R є конгруенцією.

Зазначимо, що фактор-множину множини N за відношенням еквівалентності R можна побудувати ще й таким чином. Знайдемо клас числа 0: К(0)={n|nÎN, 0Rn}={n|nÎN, (0-n) ділиться на 3}={n|nÎN, 0-n=3k для деякого цілого k}={n|nÎN, n=3(-k), -k ціле}={n|nÎN, n ділиться на 3}={n|nÎN, остача від ділення n на 3 дорівнює 0}. К(0)¹N, отже, існують числа, що належать N\K(0); зокрема, 1ÎN\K(0). Побудуємо К(1): К(1)={n|nÎN, 1Rn}={n|nÎN, (1-n) ділиться на 3}={n|nÎN, 1-n=3k для деякого цілого k}={n|nÎN, n=3(-k)+1, -k ціле}={n|nÎN, остача від ділення n на 3 дорівнює 1}. Множина N містить числа, що не належать ні К(0), ні К(1), зокрема, 2ÏК(0), 2ÏК(1). Побудуємо К(2): К(2)={n|nÎN, 2Rn}={n|nÎN, (2-n) ділиться на 3}={n|nÎN, 2-n=3k для деякого цілого k}={n|nÎN, n=3(-k)+2, -k ціле}={n|nÎN, остача від ділення n на 3 дорівнює 2}. Сукупність множин K(0), К(1), К(2) утворює розбиття множини N. Таким чином, N/R={K(0),K(1),K(2)}={[0],[1],[2]}.

Визначимо на множині N/R дві бінарні операції (позначимо їх так само, як й операції алгебри G, тобто + та ´). Для визначення операцій використаємо правило: fⁿ([a₁],…,[a_n])=[fⁿ(a₁,…,a_n)]. Отже, для операції + маємо: [a₁]+[a₂]=[a₁+a₂], а для операції ´ маємо: [a₁]´[a₂]=[a₁´a₂]. Таким чином, щоб обчислити результат операції + (´) для елементів [a₁] та [a₂] множини N/R, додаємо (множимо) числа a₁ та a₂, а потім обчислюємо остачу від ділення на 3 числа a₁+a₂ (a₁´a₂); якщо остача дорівнює 0, то результат виконання оперції + (´) є [0], якщо остача 1, то результат є [1], якщо остача 2, то результат є [2]. Отже, для операції + маємо: [0]+[0]=[0+0]=[0], [0]+[1]=[0+1]=[1], [0]+[2]=[0+2]=[2], [1]+[0]=[1+0]=[1], [1]+[1]=[1+1]=[2], [1]+[2]=[1+2]=[3]=[0], [2+0]=[2+0]=[2], [2]+[1]=[2+1]=[3]=[0], [2]+[2]=[4]=[1]. Для операції ´ виконуємо аналогічні обчислення (за рівністю [a₁]´[a₂]=[a₁´a₂]). Подамо + та ´ у вигляді таблиць:

Алгебра G/R побудована. Кінець прикладу.

Означення 10. Нехай G=(A,W) – алгебра, G/R фактор-алгебра алгебри G за конгруенцією R. Відображення h_nat:A®A/R, що визначається таким чином: h_nat(a)=[a], називається натуральним гомоморфізмом алгебри G у фактор-алгебру G/R.

Покажемо, що відображення h_nat дійсно є гомоморфним відображенням алгебри G у фактор-алгебру G/R. Нехай fⁿ – операція із сигнатури алгебри G, a₁,…,a_nÎA; покажемо, що h_nat(fⁿ(a₁,…,a_n))=fⁿ(h_nat(a₁),…,h_nat(a_n)). Маємо: h_nat(fⁿ(a₁,…,a_n))=[fⁿ(a₁,…,a_n)]; fⁿ(h_nat(a₁),…,h_nat(a_n))= =fⁿ([a₁],…,[a_n]); оскільки [fⁿ(a₁,…,a_n)]=fⁿ([a₁],…,[a_n]), то h_nat(fⁿ(a₁,…,a_n))=fⁿ(h_nat(a₁),…,h_nat(a_n)).

Розглянемо приклад. Побудуємо натуральний гомоморфізм алгебри G=(N,+,´) у фактор-алгебру G/R=(N/R,+,´) за конгруенцією R={<x,y>| (x-y) ділиться на 3}. Як було показано у попередньому прикладі, N/R={[0],[1],[2]}. З означення натурального гомоморфізму випливає, що для невід’ємного цілого числа х маємо: h_nat(х)=[0], якщо хÎ[0] (тобто якщо х ділиться на 3), h_nat(х)=[1], якщо хÎ[1] (тобто якщо остача від ділення х на 3 дорівнює 1), h_nat(х)=[2], якщо хÎ[2] (тобто якщо остача від ділення х на 3 дорівнює 2).

Теорема про гомоморфізми. Нехай h – гомоморфне відображення алгебри G=(A,W) на алгебру H=(B,W). Тоді в алгебрі G існує конгруенція R, така що алгебри G/R та Н ізоморфні й, коли g – ізоморфізм G/R та Н, то h=h_nat*g, де h_nat – натуральний гомоморфізм алгебр G та G/R.

План доведення. Побудуємо на множині А бінарне відношення R таким чином: xRy Û h(x)=h(y). Доводимо, що R конгруенція у алгебрі G. Побудуємо відображення g:A/R®B таким чином: нехай [a]ÎA/R, тоді g([a])=h(a). Доводимо, що g – ізоморфізм алгебр G/R та Н. Доводимо, що h=h_nat*g.

Контрольні питання

1. Що таке фактор-алгебра алгебри за конгруенцією?

2. Що таке натуральний гомоморфізм?