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

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

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

Запис вигляду «» читається як « еквівалентно ».

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

Позначення ред.

В літературі можуть застосовуватися різні символи для позначення двох елементів a і b із множини що є еквівалентними відповідно до відношення еквівалентності R; найбільш загальними позначеннями є "a ~ b" і "ab", які використовують коли R є неявною, і варіації позначень "a ~R b", "aR b", або "aRb", які вказують R явним чином. Нееквівалентність може записуватися як "ab" або " ".

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

  • Класом еквівалентності   елемента   називається підмножина елементів, еквівалентних  . З зазначеного визначення випливає що, якщо  , то  .

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

  • Для класу еквівалентності елемента   використовується наступне позначення:  ,  ,  .
  • Множина класів еквівалентності по відношенню   є розбиттям множини.

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

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

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

Див. також: Факторизація

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

 

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

Нехай  ,   — множини,   — відображення, тоді бінарне відношення   визначене правилом

 

є відношенням еквівалентності на  . При цьому відображення утворює відображення  , яке визначається правилом

 

чи

 .

При цьому отримується факторизація відображення   на сюр'єктивне відображення   та ін'ективне відображення  .

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

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

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

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

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

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

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

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

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

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

Див. також ред.

Джерела ред.