7.2: Відносини еквівалентності

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

Визначення 7.35. \(\sim\)Дозволяти відношення на множині\(A\). Тоді\(\sim\) називається відношення еквівалентності на\(A\) якщо\(\sim\) є рефлексивним, симетричним і перехідним.

Символ «\(\sim\)" зазвичай вимовляється як «twiddle» або «tilde», а фраза «\(a\sim b\)" може бути прочитана як «\(a\)пов'язана з\(b\)" або «\(a\)twiddles\(b\)».

Проблема 7.36. Дозвольте\(A=\{1,2,3,4,5,6\}\) і визначте\[R=\{(1,1),(1,6),(2,2),(2,3),(2,4),(3,3),(3,2),(3,4),(4,4),(4,2),(4,3),(5,5),(6,6),(6,1)\}.\] Використання\(R\), виконайте кожне з наступних дій.

1. Намалюйте диграф для\(R\).
2. Визначте\(R\), чи є відношення еквівалентності на\(A\).
3. Знайти\(Rel(R)\), визначаючи\(rel(x)\) для кожного\(x\in A\).

Проблема 7.37. Нехай\(A=\{a,b,c,d,e\}\).

1. Складіть відношення еквівалентності\(\sim\) на,\(A\) намалювавши диграф\(a\) такий, який не\(c\) пов'язаний\(b\) і не пов'язаний з\(b\).
2. Використовуючи свій диграф, знайдіть,\(Rel(\sim)\) визначаючи\(rel(x)\) для кожного\(x\in A\).

Проблема 7.38. Враховуючи скінченну множину\(A\) та відношення еквівалентності\(\sim\) на\(A\), опишіть, як повинен виглядати відповідний диграф.

Проблема 7.39. Визначте, які відносини, наведені в задачі 7.34, є співвідношеннями еквівалентності.

Проблема 7.40. \(\mathcal{T}\)Дозволяти бути набір всіх трикутників і визначити\(\sim\) на\(\mathcal{T}\) через\(T_1\sim T_2\) якщо\(T_1\) схожий на\(T_2\). Визначте\(\sim\), чи є відношення еквівалентності на\(\mathcal{T}\).

Проблема 7.41. Якщо можливо, побудуйте відношення еквівалентності на порожній множині. Якщо це неможливо, поясніть, чому.

Теорема 7.42. Припустимо,\(\sim\) це відношення еквівалентності на множині\(A\) і нехай\(a,b\in A\). Тоді\(rel(a)=rel(b)\) якщо і тільки якщо\(a\sim b\).

Теорема 7.43. Припустимо,\(\sim\) це відношення еквівалентності на множині\(A\). Тоді

1. \(\displaystyle \bigcup_{a\in A}\ rel(a)=A\), і
2. [thm:equiv дає розділ b] Для всіх\(a,b\in A\), або\(rel(a)=rel(b)\) або\(rel(a)\cap rel(b)=\emptyset\).

У світлі теореми 7.43 ми маємо наступне визначення.

Визначення 7.44. Якщо\(\sim\) відношення еквівалентності на множині\(A\), то для кожного\(a\in A\), ми\(rel(a)\) називаємо клас еквівалентності\(a\).

Коли\(\sim\) відношення еквівалентності на множині\(A\), зазвичай записувати кожен клас еквівалентності\(rel(a)\) як\([a]\) (або іноді\(\overline{a}\)). Елемент\(a\) всередині квадратних дужок називається представником класу еквівалентності\([a]\). Теорема 7.42 передбачає, що клас еквівалентності може бути представлений будь-яким елементом класу еквівалентності. Наприклад, у задачі 7.36 ми маємо,\([1]=[6]\) оскільки 1 і 6 знаходяться в одному класі еквівалентності. Колекція\(Rel(\sim)\) класів еквівалентності часто позначається тим\(A/\mathord\sim\), що читається як «по\(A\) модулю\(\sim\)» або «\(A\)мод\(\sim\)». Колекцію іноді\(A/\mathord\sim\) називають часткою\(A\) по\(\sim\).

Приклад 7.45. Нехай\(P\) позначають жителів конкретного міста і визначають\(\sim\) на\(P\) через,\(a\sim b\) якщо\(a\) і\(b\) мають однакове прізвище. Легко помітити, що це відношення є рефлексивним, симетричним та перехідним, а отже,\(\sim\) є співвідношенням еквівалентності на\(P\). Класи еквівалентності відповідають колекціям осіб з однаковим прізвищем. Наприклад, Марія Гарсія, Ентоні Гарсія та Аріана Гарсія належать до одного класу еквівалентності. Будь-який Гарсія може використовуватися як представник для відповідного класу еквівалентності, тому ми можемо позначити його як\([\text{Maria Garcia}]\), наприклад. Колекція\(P/\mathord\sim\) складається з різних наборів людей з однаковим прізвищем. Зокрема,\([\text{Maria Garcia}]\in P/\mathord\sim\).

Приклад 7.46. П'ять різних наборів родичів, які ви визначили в задачі 7.22, є класами еквівалентності для\(\equiv_5\) on\(\mathbb{Z}\). Ці класи еквівалентності часто називають класами конгруентності по модулю 5.

Підсумок теореми 7.43 полягає в тому, що, враховуючи співвідношення еквівалентності, кожен елемент живе точно в одному класі еквівалентності. У наступному розділі ми побачимо, що ми можемо запустити це в зворотному напрямку. Тобто, якщо ми відокремлюємо елементи множини так, що кожен елемент є елементом рівно однієї підмножини, то це визначає відношення еквівалентності.

Проблема 7.47. Якщо\(\sim\) відношення еквівалентності на скінченній множині\(A\), опишіть з\(A/\mathord\sim\) точки зору диграфа, відповідного\(\sim\).

Проблема 7.48. Для кожного з співвідношень еквівалентності, які ви визначили в Задачі 7.39, коротко опишіть відповідні класи еквівалентності.

Проблема 7.49. Припустимо\(S\),\(R\) і є обидва співвідношення еквівалентності на множині\(A\). Чи\(R\cap S\) є відношення еквівалентності на\(A\)? Якщо так, доведіть це. В іншому випадку наведіть контрприклад.

Проблема 7.50. Припустимо\(S\),\(R\) і є обидва співвідношення еквівалентності на множині\(A\). Чи\(R\cup S\) є відношення еквівалентності на\(A\)? Якщо так, доведіть це. В іншому випадку наведіть контрприклад.