Приклади відносин еквівалентності

Відношення рівності на будь-якій безлічі є відношенням еквівалентності, причому відношення рівності є в деякому змісті мінімальним (граничним) случаємо відносини еквівалентності.

Геометричне відношення подоби трикутників на площині є відношенням еквівалентності.

Відносини порівнянності по модулі числа n у Z: x порівнянно з у по модулі числа n, якщо різниця x – у поділяється на n. Позначається: x º у (mod n). Наприклад: 3 º 6(mod 3), 7 º 13(mod 3).

Відношення паралелльности прямих в евклідовому просторі.

Твердження виду sin ² x + cos ² x = 1, (a + b)(a – b) = a ² – b ², що складаються їхніх формул, з'єднаних знайомий рівності, задають бінарне відношення на безлічі формул, що описують суперпозиції елементарних функцій. Це відношення равносильности також є відношенням еквівалентності: формули рівносильні, якщо вони задають ту саму функцію.

Відношення «студенти x і y учаться в одній групі», де x, y Î {«студенти першого курсу»}.

Відношення «жити в одному районі», визначене на безлічі людей, що живуть у м. Києві, є відношенням еквівалентності.

Безліч усіх жителів Києва розбивається останнім відношенням еквівалентності на ряд непересічних підмножин, у даному випадку на безлічі людей, що живуть у тому самому районі. Два жителі вважаються еквівалентними по даному відношенню, якщо вони живуть у тому самому районі, і в цьому змісті вони нерозрізнені, тобто вони володіють тим самим властивістю: «жити в районі «ХХХ». Ця властивість є визначальною властивістю (предикатом) безлічі всіх жителів району «ХХХ». З іншого боку, не можна жити в двох (і більш) районах відразу (у всякому разі, відповідно до прописки), тому безлічі жителів різних районів не перетинаються. Таким чином, відношення «жити в одному районі» розбиває всю безліч жителів міста на ряд непересічних підмножин, таких, що усередині кожної підмножини всі жителі еквівалентні по даному відношенню, і ніякі два жителі різних підмножин не знаходяться у відношенні еквівалентності один з одним. Такі підмножини називаються класами еквівалентності.

Дамо більш строге визначення.

Визначення. Нехай на безлічі X задане відношення еквівалентності r. Тоді підмножина A Í X називається класом еквівалентності по відношенню r, якщо для будь-яких елементів x, y Î A виконується відношення xry.

Можна побудувати класи еквівалентності в такий спосіб. Виберемо елемент a ₁, що належить X, і утворимо підмножину A ₁ Í X з a ₁ і всіх елементів, еквівалентних a ₁. Це буде клас еквівалентності A ₁. Далі виберемо елемент a ₂ Î X і утворимо клас A ₂, що складається з всіх елементів, еквівалентних a ₂, і т.д. Одержимо систему класів A ₁, A ₂,..., таку, що будь-який елемент a_i Î X входить тільки в один клас, об'єднання всіх безлічей A ₁ È A ₂ È... утворить безліч X, і для будь-яких i, j A_i Ç A_j = Æ, тобто безліч класів еквівалентності утворить розбивка безлічі X.

Отримана система класів еквівалентності має наступні властивості.

Нехай r є відношення еквівалентності на X. Тоді безліч класів еквівалентності по відношенню r є розбивка безлічі X. Назад, якщо є деяка розбивка Â безлічі X, а відношення r таке, що arb тоді і тільки тоді, коли a Î A, b Î A, A Í Â, те r є відношення еквівалентності на X.

На підставі цієї теореми можна дати конструктивне визначення відносини еквівалентності: відношення r на безлічі Х називається еквівалентністю, якщо існує розбивка Х на підмножини { A ₁, A ₂ ,..., A_n } таке, що відношення xr у виконується тоді і тільки тоді, якщо x і в належать тому самому підмножині. Будемо позначати клас еквівалентності, породжений елементом a Î X через [ a ], якщо a Î [ a ]. Тоді, якщо arb, те [ a ] = [ b ].

Визначення 2.18. Безліч класів еквівалентності безлічі X по відношенню r називається фактором-безліччю безлічі X по відношенню r і позначається [ X / r ].

Приклади. Усі класи еквівалентності по відношенню рівності складаються з одного елемента. Фактор-безліч по відношенню рівності складається з елементів самої безлічі.

Усі подібні один одному трикутники складають один клас еквівалентності. Наприклад, безліч рівносторонніх трикутників складає один клас еквівалентності, безліч прямокутних рівнобедрених трикутників — інший і т.д. Фактор-безліч — безліч усіх можливих трикутників — нескінченно.

Розглянемо відношення порівнянності по модулі 3 на безлічі Z: xry Û x º y (mod 3). Запис x º y (mod 3) означає, що різниця х - у поділяється на 3 без залишку. Будемо позначати це так: xry Û (х - у) /3.

З'ясуємо, якими властивостями володіє це відношення. Нехай х, у Î Z.

1. Рефлексивность: для всякого x xrx. Дійсно, (x – x)/3 = 0/3 = 0; 0 Î Z, отже, відношення рефлексивне.

2. Симетричність: якщо xry, те вrх.

Нехай (х – у) /3 = k Î Z. Тоді вrх Û (у – х) /3 = –(х – у) /3 = – k Î Z. Отже, умова симетричності виконується.

3. Транзитивність: з xry і вrz випливає xrz.

Нехай (х–у)/3 = k₁ Î Z, тобто х–у = 3 k₁, і (y–z)/3 = k₂ Î Z, тобто y–z = 3 k₂. Вирішимо цю систему рівнянь, склавши них: х–у+y–z = 3(k₁+k₂), тобто x–z = 3 (k₁+k₂)= k₃ Î Z. Умова транзитивності виконується.

Відношення х º у (mod 3) є відношенням еквівалентності. Знайдемо його фактор-безліч [ Z / r ].

Для відношення порівнянності по модулі 3 на безлічі Z фактор-безліч буде складатися з усіх чисел виду a +3 k, де k Î Z. Довільне число х можна записати у виді 3q + r, 0 £ r < 3. У той самий клас еквівалентності потраплять усі числа, що дають при розподілі на 3 однакове число r у залишку. Ми одержимо три класи еквівалентності: [0] = {0, 3, 6, 9, 12, …}; [1] = {1, 4, 7, 10, 13, …}; [2] = {2, 5, 8, 11, 14, …}... У клас [0] попадають усі числа, що поділяються на 3 без залишку, у клас [1] — усі числа, при розподілі на 3 дающие в залишку 1, і в клас [2] — усі числа, що дають у залишку 2.

Кожен клас можна охарактеризувати одним представником цього класу, і в даному випадку таким представником зручніше за усе вибрати залишок r. Отже, фактор- безліччю Z по відношенню відносини х º у (mod 3) буде [ Z / r ] = {[0], [1], [2]}.

Дата добавления: 2014-01-07