7.2: Визначення та основні властивості співвідношень еквівалентності

Людям часто потрібно перебирати колекцію предметів, складаючи подібні предмети в групу.

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

Здійснюючи інвентаризацію тварин у зоопарку, ми можемо порахувати кількість антилоп, кількість бабуїнів, кількість гепардів тощо. У цьому випадку всі тварини одного виду можуть бути згруповані разом.

Рішення

Математично кажучи, ми б визначили бінарне відношення\(S\) на множині тварин в зоопарку шляхом\[x S y \quad \text { iff } \quad x \text { and } y \text { are in the same species. }\]

Коли\(x\) і\(y\) розміщуються в одній групі (тобто коли\(x S y\) в наведеному вище прикладі), ми можемо сказати, що\(x\) це «еквівалентно»\(y\). Це означає, що\(x\) і\(y\) однакові в усіх відношеннях, які нас цікавлять. (У наведеному вище прикладі нас цікавить тільки вид тварини, а не його вага, ні вік, ні що-небудь ще.) Відповідне двійкове відношення ми називаємо «співвідношенням еквівалентності». Таким чином, двійкове відношення\(S\) в наведеному вище прикладі є відношенням еквівалентності.

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

Ось додаткові приклади:

1. Якщо нас цікавлять тільки імена, ми могли б визначити співвідношення еквівалентності\(N\) на множині всіх людей по\[x N y \text { iff } x \text { has the same first name as } y \text {. }\]
2. Припустимо, в кондитерській є бункери для різних видів цукерок, які вони продають. Для працівника, що поповнює бункери, всі шматочки цукерок, які йдуть в один і той же смітник, так що він або вона має справу з співвідношення еквівалентності на наборі цукерок.
3. У геометрії часто цікавить лише форма трикутника, а не його розташування (або колір, або що-небудь інше). Тому математики визначають відношення еквівалентності\(\cong\) на множині всіх трикутників по\[T_{1} \cong T_{2} \text { iff } T_{1} \text { is congruent to } T_{2} .\]

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

Припустимо,\(\sim\) це відношення еквівалентності. (Тобто у нас є\(x \sim y\) iff\(x\) і\(y\) однакові за всіма параметрами, які нас цікавлять.) Тоді ми очікуємо:

1. \(\sim\)є\(x\) рефлексивним (такий же, як\(x\)),
2. \(\sim\)симетрична (якщо\(x\) така ж\(y\), як, то\(y\) така ж, як\(x\)), і
3. \(\sim\)є перехідним (якщо\(x\) такий же\(y\), як, і\(y\) такий же\(z\), як, то\(x\) такий же, як\(z\)).

Це мотивує наступне визначення:

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

Відношення еквівалентності на множині\(A\) - це двійкове відношення на A, яке є рефлексивним, симетричним та перехідним.

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

Замість того, щоб представляти відношення еквівалентності буквою, традиційно використовувати символ\(\sim\) (або іноді\(\equiv\) або\(\cong\)).

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

Для будь-якого\(n \in \mathbb{Z}\), ми знаємо, що конгруентність по модулю\(n\) є рефлексивним, симетричним і перехідним (див. Вправа\(5.1.18\)). Тому конгруентність по модулю\(n\) - це відношення еквівалентності.

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

Визначте\(\sim\) двійкове відношення\(\mathbb{R}\) по\(x \sim y\) iff\(x^{2} = y^{2}\). Тоді\(\sim\) - відношення еквівалентності.

Рішення

Ми хочемо показати, що\(\sim\) є рефлексивним, симетричним і перехідним.

(Рефлексивний) З огляду на\(x \in \mathbb{R}\), у нас\(x^{2} = x^{2}\), так\(x \sim x\).
(Симетричний) Дано\(x, y \in \mathbb{R}\), таке, що\(x \sim y\), у нас є\(x^{2} = y^{2}\). Оскільки рівність симетрична, це означає\(y^{2} = x^{2}\), що так\(y \sim x\).
(Перехідний) Дано\(x, y, z \in \mathbb{R}\), таке що\(x \sim y\) і\(y \sim z\), у нас\(x^{2} = y^{2}\) і\(y^{2} = z^{2}\). \(x^{2} = y^{2} = z^{2}\)Тому так\(x^{2} = z^{2}\). Звідси\(x \sim z\).

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

Визначте\(\sim\) двійкове відношення\(\mathbb{N} \times \mathbb{N}\) на\((a_{1}, b_{1}\))\ sim (a_ {2}, b_ {2})\) iff\(a_{1}+b_{2} = a_{2}+b_{1}\). Тоді\(\sim\) - відношення еквівалентності.

Рішення

Ми хочемо показати, що\(\sim\) є рефлексивним, симетричним і перехідним.

(Рефлексивний) З огляду на\((a, b) \in \mathbb{N} \times \mathbb{N}\), у нас\(a + b = a + b\), так\((a, b) \sim (a, b)\).
(симетричний) З огляду на\((a_{1}, b_{1}),(a_{2}, b_{2}) \in \mathbb{N} \times \mathbb{N}\), такий\((a_{1}, b_{1}) \sim (a_{2}, b_{2})\), що, визначення\(\sim\) говорить нам, що\(a_{1} + b_{2} = a_{2} + b_{1}\). Оскільки рівність симетрична, це означає\(a_{2} + b_{1} = a_{1} + b_{2}\), що так\((a_{2}, b_{2}) \sim (a_{1}, b_{1})\).
(Перехідний) Враховуючи\((a_{1}, b_{1}),(a_{2}, b_{2}),(a_{3}, b_{3}) \in \mathbb{N} \times \mathbb{N}\), такий, що\[(a_{1}, b_{1}) \sim (a_{2}, b_{2}) \text { and } (a_{2}, b_{2}) \sim (a_{3}, b_{3}) ,\]

\[a_{1}+b_{2}=a_{2}+b_{1} \text { and } a_{2}+b_{3}=a_{3}+b_{2} .\]
Тому\ [\ почати {вирівняний}
\ лівий (a_ {1} +b_ {3}\ праворуч) +\ лівий (a_ {2} +b_ {2}\ праворуч) &=\ лівий (a_ {1} +b_ {2}\ правий) +\ лівий (a_ {2} +b_ {3}\ праворуч)\\
&=\ лівий (a_ {2} +b_ {1}\ праворуч) +\ ліворуч (a_ {3} +b_ {2}\ праворуч)\\
&=\ ліворуч (a_ {3} +b_ {1}\ праворуч) +\ ліворуч (a _ {2} +b_ {2}\ right)
\ end {aligned}\]
Віднімаючи\(a_{2} + b_{2}\) з обох сторін рівняння, робимо висновок\(a_{1} + b_{3} = a_{3} + b_{1}\), що, так\((a_{1}, b_{1}) \sim (a_{3}, b_{3})\).

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

Показати, що кожне з цих двійкових відносин є співвідношенням еквівалентності.

1. \(\sim\)Двійкове відношення on\(\mathbb{R}\) визначається\(x \sim y \text { iff } x^{2}-3 x=y^{2}-3 y\)
2. Двійкове відношення\(\sim\) на\(\mathbb{R}\) визначається\(x \sim y \text { iff } x-y \in \mathbb{Z} \text {. }\)
   [Підказка: Ви можете припустити (без доказів), що від'ємне від будь-якого цілого числа є цілим числом, і що сума будь-яких двох цілих чисел є цілим числом. Для транзитивності зверніть увагу, що\(x-z=(x-y)+(y-z)\).]
3. Двійкове відношення\(\sim\) on\(\mathbb{N}^{+} \times \mathbb{N}^{+}\) визначається за допомогою\(\left(a_{1}, b_{1}\right) \sim\left(a_{2}, b_{2}\right) \text { iff } a_{1} b_{2}=a_{2} b_{1}\).
   [Підказка: Подібно до доказу у прикладі\(7.2.8\), але з множенням замість додавання.]

Будь-який раз, коли у нас є функція, ми можемо використовувати її для створення співвідношення еквівалентності в області функції:

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

1. Кожна тварина має тільки один вид, так\(\text { Species }\) це функція, яка визначається на безлічі всіх тварин. Співвідношення\(S\) еквівалентності Прикладу\(7.2.1\) можна охарактеризувати\[x S y \quad \text { iff } \quad \text { Species }(x)=\operatorname{Species}(y) .\]
2. Якщо припустити, що у кожної людини є ім'я, то\(\text { FirstName }\) є функція на безлічі всіх людей. Співвідношення\(N\) еквівалентності Прикладу\(7.2.2(1)\) можна охарактеризувати\[x N y \quad \text { iff } \quad \text { FirstName }(x)=\text { FirstName }(y) .\]

Наступний результат узагальнює цю ідею до всіх функцій.

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

Припустимо\(f : A \rightarrow B\). Якщо ми визначимо двійкове відношення\(\sim\)\(A\) по\[a_{1} \sim a_{2} \quad \text { iff } \quad f\left(a_{1}\right)=f\left(a_{2}\right) ,\]

\(\sim\)то відношення еквівалентності.

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

Показати, що якщо\(\sim\) є відношення еквівалентності на\(\mathbb{R}\), то існують\(a, b \in \mathbb{R}\), такі що\(a \sim b\) і\(a + b = 6\).