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

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

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

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

Наслідком властивостей рефлексивності, симетричності і транзитивності є те, що будь-яке відношення еквівалентності забезпечує розбиття будь-якої базової множини на непересічні класи еквівалентності. Два елементи даної множини еквівалентні між собою тоді і тільки тоді, коли вони належать одному класу еквівалентності.

Позначення

В літературі можуть застосовуватися різні символи для позначення двох елементів a і b із множини що є еквівалентними відповідно до відношення еквівалентності R; найбільш загальними позначеннями є "a ~ b" і "a ≡ b", які використовують коли R є неявною, і варіації позначень "a ~_R b", "a ≡_R b", або "aRb", які вказують R явним чином. Нееквівалентність може записуватися як "a ≁ b" або "${\displaystyle a\not \equiv b}$".

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

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

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

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

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

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

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

• Еквівалентність категорій

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

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

${\displaystyle p\colon x\mapsto C_{x}}$

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

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

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

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

${\displaystyle {\overline {f}}(C_{x})=f(x)}$

чи

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

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

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

Розклад уроків в школі — є типовий приклад факторизації. В даному випадку ${\displaystyle X}$ — множина всіх учнів школи, ${\displaystyle Y}$ — множина всіх предметів, упорядкованих по днях тижня та часом їх проведення. Класами еквівалентності є класи (групи учнів). Відображення ${\displaystyle f}$ — розклад уроків записаних у щоденники учнів. Відображення ${\displaystyle {\overline {f}}}$ — розклад уроків по класам, який вивішують у вестибюлі школи. Там же і вивішується відображення ${\displaystyle 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.

Див. також

• Асимптотична рівність
• Відношення порядку
• Відношення толерантності
• Вільний добуток

Джерела

• Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)

• Хаусдорф Ф. Теория множеств. — Москва ; Ленинград : ОНТИ(інші мови), 1937. — 304 с. — ISBN 978-5-382-00127-2.(рос.)

• Мальцев А. И. Алгебраические системы. — Москва : Наука, 1970. — 392 с.(рос.)
• А. И. Кострикин, Введение в алгебру. М.: Наука, 1977, 47—51.
• Weisstein, Eric W. Відношення еквівалентності(англ.) на сайті Wolfram MathWorld.
• Відношення еквівалентності на PlanetMath.(англ.)
• Hazewinkel, Michiel, ред. (2001), Відношення еквівалентності, Математична енциклопедія, Springer, ISBN 978-1-55608-010-4