Відношення еквівалентності
Означення.ВідношенняR на множині називається відношенням еквівалентності, якщо воно рефлексивне, симетричне і транзитивне.
Виконаємо таке завдання: побудуємо графи заданих відношень.
1) граф відношення «бути паралельним», за умови, що а || b || с, k || d || e, f || h.
Які властивості має дане відношення?
Властивості рефлективності, симетричності і транзитивності.
2) граф відношення «бути рівними» на множині відрізків, якщо a = b = c, d = e, відрізок h не дорівнює жодному з даних відрізків.
На множині дробів задане відношення рівності. Якими властивостями володіє дане відношення?
- Воно рефлексивне, так як будь-який дріб рівний самому собі.
- Воно симетричне, так як із того, що дріб х рівний дробу у, слідує, що дріб у рівний дробу х.
- Воно транзитивне, так як із того, що дріб х рівний дробу у та дріб у рівний дробу z, слідує, що дріб х рівний дробу z.
Таким чином, відношення рівності дробів рефлексивне, симетричне та транзитивне. Говорять, що воно являється відношенням еквівалентності.
Означення.Відношення R на множині Х називається відношенням еквівалентності, якщо воно рефлексивне, симетричне та транзитивне.
Відношеннями еквівалентності являються, наприклад, відношення паралельності прямих, відношення рівності фігур. На всіх цих графах видно, як множина розбивається на підмножини. Так на графі відношення рівності дробів виділяються три підмножини: . Ці підмножини не перетинаються, а їх об’єднання співпадає з множиною Х, тобто має розбиття множини Х на попарно неперетинаючі підмножини.
Приклади відношень еквівалентності: відношення рівності на довільній множині; відношення паралельності прямих на площині; відношення подібності на множині усіх трикутників; відношення рівносильності на множині рівнянь; відношення «навчатися в одній групі» на множині студентів коледжу.
Дане відношення розбило задані множини на підмножини:
1) {a, b, c}, {d, e}, {f, h} – підмножини паралельних між собою прямих;
2) {a, b, c}, {e, d}, {h}; - підмножини рівних між собою відрізків;
3) {1/2, 2/4, 3/6}, {1/3, 2/6}, {1/4} підмножини рівних між собою дробів.
Ці множини не перетинаються, а їх об’єднання співпадає з множиною X.
Отже, якщо у множині Х задано відношення еквівалентності, то воно розбиває цю множину на підмножини, які попарно не перетинаються (класи еквівалентності).
І навпаки: якщо дане відношення, задане на множині Х, визначило розбиття цієї множини на класи, то це відношення є відношенням еквівалентності.
Отже, за допомогою відношення еквівалентності виконується досить поширена операція – розбиття непорожньої множини на підмножини, які називають класами еквівалентності, при якому:
1) кожен елемент множини належить одному і тільки одному класу;
2) будь-які два елементи одного класу перебувають у даному відношенні еквівалентності;
3) будь-які два елементи, що належать різним класам, не перебувають у цьому відношенні.
Граф відношення еквівалентності є об’єднанням кількох повних графів. Навпаки, якщо граф деякого відношення на множині розпадається на кілька повних графів, то воно є відношенням еквівалентності. Відношення еквівалентності наочно зображується системою повних графів, побудованих на класах еквівалентності. Повним називається граф, в якого всі точки сполучено стрілками і всі вершини мають петлі.
Всі елементи одного класу еквівалентності мають однакові властивості, що дає можливість вивчати властивості одного елемента і поширювати їх на всі елементи класу.
Теорема:Якщо на множині Х задане відношення еквівалентності, то воно розбиває цю множину на попарно неперетинаючі підмножини (класи еквівалентності).