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

Відно́шення еквівале́нтності ($\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$».

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

Позначення

В літературі можуть застосовуватися різні символи для позначення двох елементів Шаблон:Math і Шаблон:Math із множини що є еквівалентними відповідно до відношення еквівалентності Шаблон:Math; найбільш загальними позначеннями є "Шаблон:Math" і "Шаблон:Math", які використовують коли Шаблон:Math є неявною, і варіації позначень "Шаблон:Math", "Шаблон:Math", або "Шаблон:Math", які вказують Шаблон:Math явним чином. Нееквівалентність може записуватися як "Шаблон:Math" або "$a\equiv ̸b$".

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

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

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

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

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

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

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

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

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

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

$p:x\mapsto C_x$

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

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

$x{R}_{f}y⟺f(x)=f(y),x,y\in X$

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

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

чи

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

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

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

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