Відношення еквівалентності

Відношення еквівалентності — це бінарне відношення на множині, яке є рефлексивним, симетричним і транзитивним.

Мотивація

Відношення еквівалентності — це свого роду «тонша» версія відношення рівності. Ми завжди можемо вирішити, чи однакові два елементи множини, тобто чи a = b. Але іноді нам потрібно з'ясувати, чи вони лише подібні, не обов'язково однакові. Інакше кажучи — чи мають вони однакову якусь істотну властивість. Наприклад, дві книжки можна вважати подібними, якщо вони одного жанру — або мовою еквівалентності: дві книжки еквівалентні, якщо вони мають однаковий жанр.

Чого б ми чекали від такої еквівалентності? Візьмімо інший приклад. Два слова подібні/еквівалентні, якщо вони однакової довжини.

Напевно, ми б чекали, що коли виміряємо подібність двох однакових слів, то вийде, що вони подібні. Тобто для всіх слів має виконуватися, що вони подібні/еквівалентні самі собі. Мовою відношень: відношення еквівалентності має бути рефлексивним.

Далі, якщо слово «потік» подібне/еквівалентне слову «Агата», то, звісно, ми очікуємо, що й слово «Агата» буде еквівалентне слову «потік». Іншими словами, порядок не має значення. Мовою відношень: відношення еквівалентності має бути симетричним.

І нарешті, якщо слово «мить» подібне/еквівалентне слову «птах», а слово «птах» еквівалентне слову «нога», то ми очікуємо, що й пара слів «мить» і «нога» буде еквівалентною. Тобто відношення еквівалентності має бути ще й транзитивним.

Нічого більше від еквівалентності ми не очікуємо.

Приклади

Інші приклади еквівалентностей:

• Жити в одному місті. Юрко, безумовно, живе в тому самому місті, що й Юрко (рефлексивність). Якщо Юрко живе в тому самому місті, що й Андрій, то й Андрій живе в тому самому місті, що й Юрко (симетричність). А якщо Андрій живе в тому самому місті, що й Мартин, то й Юрко живе в тому самому місті, що й Мартин (транзитивність).
• Пісні одного автора. Пісня «Балада про сірий чайник» напевно має того самого автора, що й пісня «Балада про сірий чайник» (рефлексивність). Якщо пісні «Балада про сірий чайник» і «Вальс для старої шафи» мають одного автора, то й «Вальс для старої шафи» та «Балада про сірий чайник» мають одного автора (симетричність). А якщо «Вальс для старої шафи» і «Марш дощових черв’яків» мають одного автора, то й «Балада про сірий чайник» та «Марш дощових черв’яків» мають одного автора (транзитивність).
• (a; b) ∈ R тоді й лише тоді, коли a − b — парне число; a, b — цілі числа. Рефлексивність: a − a = 0, нуль — парне число. Симетричність: позначмо c = a − b. Тоді b − a = −(a − b) = −c. Якщо c парне, то й −c має бути парним. Транзитивність: позначмо p = a − b, а також q = b − c. Нам відомо, що і p, і q — парні числа. Тепер маємо довести, що a − c — парне число. У цю рівність замість c підставимо c = b − q: a−(b − q), що дорівнює a − b + q. З припущень нам відомо, що a − b — парне число. Якщо до парного числа додати ще одне парне число q, отримаємо знову парне число.
• Рівність. Рівність є еквівалентністю, і водночас це найменша еквівалентність на довільній множині M.

Тривіальні еквівалентності

Маємо непорожню множину M. Яка найменша можлива еквівалентність R на множині M? Найменша можлива підмножина декартового добутку M × M — це порожня множина $\varnothing$. Чи задовольняє порожня множина умови еквівалентності?

Вона, безумовно, симетрична: оскільки відношення R не має жодного елемента, умова симетричності виконується автоматично і тривіально. Так само й транзитивність. Проблема з рефлексивністю. Означення каже, що для всіх елементів x множини M виконується (x; x) ∈ R. Чи виконується це? Множина M непорожня, тож містить якийсь елемент, наприклад q. Чи належить пара (q; q) відношенню R? Ні. Отже, відношення R не є рефлексивним.

Яке найменше відношення, що задовольняє рефлексивність? Відношення рівності. Відношення R має містити щонайменше пари (x; x) для всіх елементів M. А це якраз тотожне відношення. Чи є таке відношення симетричним? Легко побачити, що так. Так само легко побачити, що воно й транзитивне. Найменше відношення еквівалентності на множині M — це тотожне відношення, яке позначаємо id_M і яке містить пари (x; x) для всіх x ∈ M.

Яка найбільша можлива еквівалентність на множині M? Найбільша підмножина — це вся множина M × M. Чи задовольняє вона умови еквівалентності? Напевно, тривіально видно, що так.

Клас еквівалентності

Кожна еквівалентність розбиває множину M на систему неперетинних множин, які ми називаємо класами еквівалентності.

Нехай M — множина всіх слів, а R — еквівалентність «слова однакової довжини». Тобто (a; b) ∈ R тоді й лише тоді, коли слова a і b мають однакову довжину. Ця еквівалентність розіб'є множину слів на кілька менших множин, у кожній з яких будуть слова однакової довжини. Окремі класи еквівалентності можна розрізняти за допомогою нижнього індексу, який водночас показуватиме довжину слів у цій множині:

• M₁ = {а, і, у, я, …}
• M₂ = {на, до, чи, ми, ви, …}
• M₃ = {але, без, той, там, …}
• M₄ = {мить, парк, гора, нива, …}
• …

Зверни увагу на дві речі: 1) окремі множини попарно неперетинні, не мають жодного спільного елемента. 2) усі елементи кожної окремої множини еквівалентні між собою. Усі слова в множині M₃ еквівалентні між собою, бо всі вони мають довжину три, тобто однакову довжину, а це і є умова еквівалентності.

При цьому кожен елемент однозначно задає свій клас еквівалентності. Це зазвичай записуємо за допомогою позначення M[x], де x ∈ M. Якби ми написали M[але], то тим самим однозначно задали б клас еквівалентності, який ми вже позначили як M₃.

Як, власне, знайти клас еквівалентності, якщо ми знаємо якийсь x ∈ M? Проходимо всі елементи множини M і з'ясовуємо, які з них еквівалентні елементу x. Усі такі елементи й будуть складати клас еквівалентності M[x].

Для M[але] ми б пройшли всі слова в M і залишили в M₃ ті, що мають довжину три.

Означення та властивості класу еквівалентності

Клас еквівалентності можна означити так. Нехай M — множина, а R — задана на ній еквівалентність. Тоді класом розбиття, який містить елемент x ∈ M, називаємо:

$$M[x] = {y \in M; (x; y) \in R}$$

Означення каже, що це всі y, еквівалентні заданому елементу x. Оскільки відношення еквівалентності рефлексивне, то таким способом сюди потрапляє й сам елемент x — адже x еквівалентний сам собі.

Розбиттям за еквівалентністю називаємо множину всіх класів еквівалентності. Тож розбиттям множини всіх слів була б множина {M₁, M₂, M₃, …}.

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

• (a; b) ∈ R тоді й лише тоді, коли M[a] = M[b]. Якщо маємо два елементи a, b, які еквівалентні, то їхні класи еквівалентності мають бути рівними.
• Навпаки, якщо (a; b) ∈ R не виконується, то також M[a] ≠ M[b], точніше $M[a] \cap M[b] = \varnothing$. Якщо маємо два елементи, які не еквівалентні, то їхні класи розбиття не перетинаються.
• Об'єднання всіх класів еквівалентності має дати вихідну множину M: M₁ ∪ M₂ ∪ … ∪ M_n = M. (Попередній запис — лише для скінченної кількості класів еквівалентності, але загалом їх може бути нескінченно багато.)

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

Перший приклад, непарні та парні числа:

Нехай маємо просту еквівалентність R, задану на натуральних числах N. (a; b) ∈ R тоді й лише тоді, коли і a, і b непарні або і a, і b парні. Приклади елементів: (1; 7), (13; 9), (4; 6), (8; 136). Визначимо тепер розбиття цієї еквівалентності на класи еквівалентності.

Почнемо послідовно. Чому дорівнюватиме клас N[1]? Треба знайти всі числа, еквівалентні числу один. За умовою еквівалентності це всі непарні числа, тож N[1] = {1, 3, 5, 7, 9, …}.

Чому дорівнюватиме клас N[2]? Знайдемо всі числа, еквівалентні двійці. Це всі парні числа: N[2] = {2, 4, 6, 8, 10, …}.

Тепер N[3]. Які числа еквівалентні трійці? Усі непарні числа. Але так ми отримаємо множину N[1], яку вже обчислили два абзаци тому. Так само для N[4] — там знову множина парних чисел.

Бачимо, що далі вже весь час повторювалися б ті самі множини. Це видно і з того, що яке б інше натуральне число n ми не взяли, виконуватиметься n ∈ N[1] або n ∈ N[2]. Інших натуральних чисел, крім непарних і парних, немає, тому ці дві множини утворюють розбиття за еквівалентністю.

Це схоже на те, ніби ми уявили еквівалентність на множині людей: і a, і b — чоловіки або і a, і b — жінки. Тоді розбиттям була б множина жінок і множина чоловіків.

Другий приклад, модуль числа:

Нехай R — еквівалентність на множині цілих чисел Z, задана так: (a; b) ∈ R тоді й лише тоді, коли |a| = |b|. (Ці вертикальні риски означають модуль числа.) Знову йдемо послідовно:

• Z[0] = {0}. Нуль перебуває у відношенні лише з нулем.
• Z[1] = {−1, 1}. Одиниця перебуває у відношенні з одиницею та з мінус одиницею, бо |1| = |−1|.
• Z[2] = {−2, 2}. Двійка перебуває у відношенні з двійкою та з мінус двійкою.
• Z[3] = {−3, 3}.
• …

Напевно, зрозуміло, як це триватиме далі. Усім розбиттям тоді була б множина класів:

$${{a, -a}; a \in \mathbb{Z}_0^+}$$

(Тобто всі пари a, −a, де a — невід'ємне ціле число.) Бачиш, що класів нескінченно багато.