Означення 4. Нехай G = (А,W) – алгебра, fnÎW, RÍA2. Відношення R називається стабільним відносно операції fn, якщо a1Rb1,…,anRbn Þ fn(a1,…,an)Rfn(b1,…,bn). Якщо відношення R стабільне відносно кожної операції сигнатури W, то воно називається стабільним в алгебрі G.
Розглянемо, наприклад, алгебру G = (N,{+,!}) й відношення рівності (=) на множині N. Перевіримо, чи є воно стабільним відносно бінарної операції додавання (+). Для цього нам треба розглянути умову a1=b1, a2=b2 Þ (а1+а2)=(b1+b2). Дана умова виконується, отже, відношення = стабільне відносно операції +. Перевіримо стабільність відношення = відносно унарної операції !. Для цього розглянемо умову a1=b1 Þ а1!=b1!. Дана умова також виконується, отже, відношення = стабільне відносно операції !. Оскільки відношення + виявилося стабільним відносно кожної операції алгебри G, воно є стабільним у даній алгебрі. Розглянемо відношення < на множині N. Перевіримо стабільність даного відношення відносно бінарної операції +. Для цього розглянемо умову: a1<b1, a2<b2 Þ (а1+а2)<(b1+b2). Оскільки дана умова виконується, відношення < стабільне відносно операції +. Перевіримо стабільність відношення < відносно унарної операції !. Для цього розглянемо умову a1<b1 Þ а1!<b1!. Для чисел 0 та 1 з множини N маємо: 0<1, але з цього не випливає, що 0!<1! (адже 0!=1!), отже, відношення < не є стабільним відносно операції !.
Розглянемо ще один приклад. Нехай задана алгебра G=({a,b,c,d}, {f1,f2}), де f1(a)=b, f1(b)=а, f1(c)=d, f1(d)=с, f2(a,a)=f2(b,b)=f2(b,c)=a, f2(a,b)=f2(a,c)=f2(b,a)=f2(d,a)=b, f2(a,d)= =f2(b,d)=f2(c,c)=f2(d,b)=f2(d,d)=c, f2(c,a)=f2(c,b)=f2(c,d)=f2(d,c)=d. Нехай на носієві цієї алгебри задано бінарне відношення R={<a,c>,<b,d>}. Перевіримо стабільність відношення R відносно унарної операції f1 із сигнатури даної алгебри. Для цього нам треба перевірити таку умову: xRy Þ f1(x)Rf1(y). Можемо здійснити перевірку даної умови, перебираючи упорядковані пари виду <x,y>, що належать R, обчислюючи f1(x) та f1(y) та перевіряючи, чи належить упорядкована пара виду <f1(х), f1(y)> відношенню R. Оскільки R містить два елементи, треба виконати дві перевірки. Розглянемо упорядковану пару <a,c> з R. Маємо: f1(а)=b, f1(с)=d; оскільки <b,d>ÎR, виконується умова аRс Þ f1(а)Rf1(с). Тепер розглянемо упорядковану пару <b,d> з R. Маємо: f1(b)=a, f1(d)=c; оскільки <a,c>ÎR, виконується умова bRd Þ f1(b)Rf1(d). Отже, відношення R стабільне відносно операції f1. Перевіримо стабільність відношення R відносно операції f2. Для цього ми маємо перевірити умову: хRy, uRv Þ f2(x,u)Rf2(y,v). Зробимо це таким чином. Спочатку знайдемо усі такі комплекти упорядкованих пар виду <x,y> та <u,v>, що належать відношенню R. Маємо: 1) <a,c>, <a,c>; 2) <a,c>, <b,d>; 3) <b,d>, <a,c>; 4) <b,d>, <b,d>. Розглянемо комплект 1 (тобто <a,c>, <a,c>). Обчислимо вирази f2(a,a) та f2(c,c). Маємо: f2(а,а)=а, f2(с,с)=с. Оскільки <a,c>ÎR, можна стверджувати, що f2(а,a)Rf2(c,c). Отже, aRc, aRc Þ f2(a,a)Rf2(c,c). Для комплекту 2 (тобто <a,c>, <b,d>). Маємо: f2(a,b)=b, f2(c,d)=d. Оскільки <b,d>ÎR, то виконується f2(a,b)Rf2(c,d), а тоді aRc, bRd Þ f2(a,b)Rf2(c,d). Розглянемо комплект 3 (тобто <b,d>, <a,c>). Маємо: f2(b,a)=b, f2(d,c)=d; оскільки <b,d>ÎR, то f2(b,a)Rf2(d,c), а значить, bRd, aRc Þ f2(b,a)Rf2(d,c). Розглянемо комплект 4 (тобто <b,d>, <b,d>). Маємо: f2(b,b)=a, f2(d,d)=c; оскільки <a,c>ÎR, то f2(b,b)Rf2(d,d), а тому, bRd, bRd Þ f2(b,b)Rf2(d,d). Таким чином, відношення R стабільне відносно бінарної операції f2. Ми показали, що відношення R стабільне відносно кожної операції із сигнатури заданої алгебри, отже, R стабільне у цій алгебрі.
Означення 5. Нехай G = (А,W) – алгебра, RÍA2. Відношення R називається конгруенцією (або конгруентністю, або відношенням конгруентності), якщо R є відношенням еквівалентності на множині А та є стабільним у алгебрі G.
Наприклад, відношення рівності на носієві алгебри (N,{+,!}) є конгруенцією, адже воно стабільне у цій алгебрі, а також є відношенням еквівалентності на множині N. Конгруенцією є також кожне з бінарних відношень Rm (mÎN+, m>1), що задане на носієві алгебри (N,{+,´}) таким чином: xRmy Û (x-y) ділиться на m.
в) R1*R2 є конгруенцією тоді й тільки тоді, коли R1*R2=R2*R1;
г) R1¢ не є конгруенцією.
Доведемо перше твердження. Нам треба показати, що відношення R1ÇR2 є відношенням еквівалентності на множині А, а також є стабільним у алгебрі G. Оскільки R1,R2 – конгруенції, то R1, та R2 є відношеннями еквівалентності на множині А, а тоді, як відомо, R1ÇR2 теж є відношенням еквівалентності на А. Покажемо, що відношення R1ÇR2 стабільне відносно кожної операції із сигнатури алгебри G. Нехай fnÎW. Доведемо, що:
Маємо: x1R1ÇR2y1,…,xnR1ÇR2yn Þ x1R1y1, x1R2y1,…,xnR1yn, xnR2yn (застосовано означення операції перерізу відношень) Þ fn(x1,…,xn)R1fn(y1,…,yn), fn(x1,…,xn)R2fn(y1,…,yn) (використано стабільність R1 та R2 у алгебрі G) Þ fn(x1,…,xn)R1ÇR2fn(y1,…,yn) (застосовано означення операції перерізу відношень). Отже, відношення R1ÇR2 стабільне відносно будь-якої операції із сигнатури алгебри G, а тому воно стабільне у алгебрі G. Таким чином, відношення R1ÇR2 є конгруенцією. Твердження а) доведено.
Контрольні питання
1. Що таке стабільність відношення відносно операції?
2. Що таке стабільність відношення в алгебрі?
3. Що таке конгруенція?
4. Які відношення конгруентності Ви знаєте?
5. Які властивості мають відношення конгруентності?
