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

Відно́шення еквівале́нтності ($\sim$) на множині $X$ — це бінарне відношення для якого виконуються наступні умови:

1. Рефлексивність: $\,a \sim a$ для будь-якого $a$ в $X$,
2. Симетричність: якщо $\,a \sim b$, то $\,b \sim a$,
3. Транзитивність: якщо $\,a \sim b$ та $\,b \sim c$, то $\,a \sim c$.

Запис вигляду «$\,a \sim b$» читається як «$a$ еквівалентно $b$».

Пов'язані визначення

• Класом еквівалентності $C(a)$ елемента $a$ називається підмножина елементів, еквівалентних $a$. З зазначеного визначення випливає що, якщо $b \in C(a)$, то $C(a) = C(b)$.

Множина всіх класів еквівалентності позначається $X/{\sim}$.

• Для класу еквівалентності елемента $a$ використовується наступне позначення: $[a]$, $a / {\sim}$, $\overline{a}$.
• Множина класів еквівалентності по відношенню $\sim$ є розбиттям множини.

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

• Найбільш наочний і всім знайомий приклад відношення еквівалентності — поділ учнів школи на класи.
• Відношення рівності («$\;=$») тривіальне відношення еквівалентності на довільній множині, зокрема на множині дійсних чисел.
• Порівняння по модулю, («а ≡ b (mod n)»).
• В Евклідовій геометрії
  • Відношення конгруентності («$\cong$»).
  • Відношення подібності («$\ \sim$»).
  • Відношення паралельності прямих («$\|$»).
• Відношення рівнопотужності множин є еквівалентністю.
• Еквівалентність функцій в Математичному аналізі:

  кажуть що функція $\, f(x)$ еквівалентна функції $\, g(x)$ при $\, x \rightarrow x_0$, якщо вона може бути представлена у вигляді: $\, f(x) = \alpha(x) g(x)$, де $\, \alpha(x) \rightarrow 1$ при $\, x \rightarrow x_0$. В даному випадку пишуть $\, f(x) \sim g(x)$, при $\, x \rightarrow x_0$. Якщо $\, g(x) \ne 0$ при $\, x \ne x_0$, еквівалентність функції $\, f(x)$ та $\, g(x)$ при $\, x \rightarrow x_0$, очевидно, рівносильна відношенню $\lim_{x \rightarrow x_0}{\frac{f(x)}{g(x)}} = 1$.

Ще один важливий, життєвий випадок: Коли лікар виписує ліки, в рецепті він записує класи еквівалентних ліків. Він не може вказати конкретний приклад абсолютно конкретний екземпляр упаковки таблеток або ампул. Таким чином, всі ліки розбиті на класи відношенням еквівалентності.

Факторизація відображень

Множина класів еквівалентності, яка відповідає відношенню еквівалентності $\sim$, позначається символом $X/{\sim}$ і називається фактормножиною відносно $\sim$. При цьому сюр'єктивне відображення

$p\colon x \mapsto C_x$

називається дійсним відображенням (чи канонічною проекцією) $X$ на фактормножену $X/{\sim}$.

Нехай $X$, $Y$ — множини, $f\colon X \to Y$ — відображення, тоді бінарне відношення $x \, {R_f} \,y$ визначене правилом

$x \mathop{R_f} y \iff f(x) = f(y), \quad x, y \in X$

є відношенням еквівалентності на $X$. При цьому відображення утворює відображення $\overline{f}\colon X/R_f \to Y$, яке визначається правилом

$\overline{f}(C_x) = f(x)$

чи

$(\overline{f}\circ p)(x) = f(x)$.

При цьому отримується факторизація відображення $f$ на сюр'єктивне відображення $p$ та ін'ективне відображення $\overline{f}$.

Факторизація відображень широко використовується в гуманітарних науках та в тих галузях техніки де немає можливостей використовувати числові значення. Вона дозволяє уникати формул там, де їх неможливо використати. Наведемо загально відомий всім приклад:

Розклад уроків в школі — є типовий приклад факторизації. В даному випадку $X$ — множина всіх учнів школи, $Y$ — множина всіх предметів, упорядкованих по днях тижня та часом їх проведення. Класами еквівалентності є класи (групи учнів). Відображення $f$ — розклад уроків записаних у щоденники учнів. Відображення $\overline{f}$ — розклад уроків по класам, який вивішують у вестибюлі школи. Там же і вивішується відображення $p$ — списки класів. Цей простий приклад наочно демонструє практичні вигоди факторизації: неможливо собі уявити розклад занять як таблицю в якій занесені всі учні школи в особистому порядку. Факторизація дозволила зобразити потрібну учням інформацію у зручному для використання вигляді в ситуації коли формули застосовувати неможливо.

На цьому переваги факторизації не закінчується. Вона дала можливість розділити роботу між людьми: завуч складає розклад, а учні записують його у щоденники. Аналогічно факторизація дозволила розділити роботу медика, який ставить діагноз та виписує рецепт, і фармацевта який еквівалентно рецепту підбирає ліки. Апофеозом факторизації є конвеєр, де реалізоване максимальне розбиття праці за рахунок стандартизації деталей.

Факторизація дозволила забезпечити модульність сучасної техніки. Наприклад, можна замінити телефон але залишити сім-карту і карту пам'яті зі старого телефону, або поміняти оперативну пам'ять в комп'ютері більше нічого не чіпаючи. Все це гнучкість і модульність в основі яких лежить факторизація.

Фактормножина та класи еквівалентності

Сукупність множин {B_i|i∈I} називається розбиттям множини A, якщо B_i=A і B_i∩B_j = ∅ для i≠j. Множини B_i, i∈I є підмножинами множини A і називаються класами, суміжними класами, блоками або елементами розбиття. Очевидно, що кожний елемент a∈A належить одній і тільки одній множині B_i, i∈I.

Нехай тепер на множині M задано відношення еквівалентності R. Виконаємо таку побудову. Виберемо деякий елемент a∈M і утворимо підмножину S_a^R = {x| x∈M і aRx}, яка складається з усіх елементів множини M, еквівалентних елементу a. Візьмемо другий елемент b∈M такий, що b∉S_a^R і утворимо множину S_b^R = {x | x∈M і bRx } з елементів еквівалентних b і т. д. Таким чином одержимо сукупність множин (можливо, нескінченну) {S_a^R, S_b^R,…}.

Побудована сукупність множин { S_i^R | i∈I} є фактормножиною множини M за еквівалентністю R і позначається M/R.

Очевидно, що будь-які два елементи з одного класу S_i^R еквівалентні між собою, в той час як будь-які два елементи з різних класів фактормножини M/R нееквівалентні.

Класи S_i^R називають класами еквівалентності за відношенням R. Клас еквівалентності, який містить елемент a∈M часто позначають через [a]_R.

Див. також

• Відношення толерантності
• Відношення порядку

Джерела

• А. И. Кострикин, Введение в алгебру. М.: Наука, 1977, 47—51.
• А. И. Мальцев, Алгебраические системы, М.: Наука, 1970, 23—30.
• В. В. Иванов, Математический анализ. НГУ, 2009.