7.3: Класи еквівалентності

Якщо нас цікавлять імена (як у прикладі\(7.2.2(1)\)), то нас також може зацікавити набір всіх людей, які мають те ж ім'я, що і ви. Це називається вашим «класом еквівалентності».

Визначення\(7.3.1\).

Припустимо,\(\sim\) це відношення еквівалентності на множині\(A\). Для кожного\(a \in A\) класу еквівалентності\(a\) є наступна підмножина\(A\):\[[a]=\left\{a^{\prime} \in A \mid a^{\prime} \sim a\right\} .\]

Приклад\(7.3.2\).

Для співвідношення еквівалентності,\(N\) описаного в прикладі\(7.2.2(1)\), ми маємо\ [\ text {Джастін Тімберлейк}] =\ {x\ in\ text {Люди}\ mid\ text {firstName} (x) =\ text {firstName} (\ text {Джастін Тімберлейк})\}.\)

Іншими словами,\(\text { [Justin Timberlake] }\) це безліч всіх людей, чиє ім'я Джастін.

ПОПЕРЕДЖЕННЯ.

Позначення\([a]\) не говорить нам, яке відношення еквівалентності використовується. Це може збивати з пантелику, якщо розглядається більше одного співвідношення еквівалентності.

Приклад\(7.3.3\).

Припустимо,\(A=\{1,2,3,4,5\}\) і\ [R=\ left\ {\ begin {масив} {c}
(1,1), (1,3), (1,4), (2,2), (2,5), (3,1), (3,3),\\
(3,4), (4,1), (4,3), (4,4), (5,2), (5,5)
\ end {масив}\ справа\}.]

Можна перевірити, що\(R\) це відношення еквівалентності на\(A\). Класи еквівалентності:

Рішення

\ [\ почати {зібраний}
{[1] =\ {1,3,4\},\ квад [2] =\ {2,5\},\ квад [3] =\ {1,3,4\}}\\
{[4] =\ {1,3,4\},\ квадрад [5] =\ {2,5\}}.
\ end {зібраний}\]

Вправа\(7.3.4\).

Не потрібно показувати свої роботи.

1. Нехай\(B=\{1,2,3,4,5\}\) і\ [S=\ left\ {\ begin {масив} {c}
   (1,1), (1,4), (2,2), (2,3), (3,2)\\
   (3,3), (4,1), (4,4), (5,5)
   \ end {масив}\ right\}.\]
   Знайти клас еквівалентності кожного елемента\(B\). (Ви можете припустити без доказів, що\(S\) це відношення еквівалентності на\(B\).)
2. Дозвольте\(C = \{1,2,3,4,5\}\) і визначте\(T\) за допомогою\[x T y \text { iff } x+y \text { is even. }\]
   Знайти клас еквівалентності кожного елемента\(C\). (Ви можете припустити без доказів, що\(T\) це відношення еквівалентності на\(C\).)

Наступна теорема представляє деякі дуже важливі властивості класів еквівалентності:

Теорема\(\PageIndex{1}\)

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

1. Для всіх\(a \in A\) у нас є\(a \in [a]\).
2. Для всіх\(a \in A\) у нас є\([a] \neq \varnothing\).
3. Об'єднання класів еквівалентності - це все\(A\). Тобто ми маємо\(A=\bigcup_{a \in A}[a]\), де\[\bigcup_{a \in A}[a]=\{x \mid \exists a \in A,(x \in[a])\} .\]
4. Для будь-якого\(a_{1}, a_{2} \in A\), такого, що\(a_{1} \sim a_{2}\), у нас є\([a_{1}] = [a_{2}]\).
5. Для будь-якого\(a_{1}, a_{2} \in A\), такого, що\(a_{1} \nsim a_{2}\), у нас є\(\left[a_{1}\right] \cap\left[a_{2}\right]=\varnothing\).

Вправа\(7.3.6\).

Довести теорему\(7.3.5\).
[Підказка: Використовуйте той факт, що\(\sim\) є рефлексивним, симетричним і перехідним.]

Зауваження\(7.3.7\).

Припустимо,\(\sim\) це відношення еквівалентності на множині\(A\). Вищевказана теорема передбачає, що будь-які два класи еквівалентності або рівні, або неспільні; тобто або вони мають точно такі ж елементи, або вони не мають спільних елементів.

Доказ

З огляду на два класи еквівалентності\([a_{1}]\) і\([a_{2}]\) які не є неспільними, ми хочемо показати\([a_{1}] = [a_{2}]\). Оскільки класи еквівалентності не є нероз'ємними, їх перетин непорожній, таким чином, є деякі\(a \in\left[a_{1}\right] \cap\left[a_{2}\right]\). Значить,\(a \in [a_{1}]\) і\(a \in [a_{2}]\). За визначенням класів еквівалентності це означає\(a \sim a_{1}\) і\(a \sim a_{2}\). Отже, Теорема\(7.3.5(4)\) говорить нам, що\([a] = [a_{1}]\) і\([a] = [a_{2}]\). \([a_{1}] = [a] = [a_{2}]\)Тому за бажанням