Клас еквівалентності
Клас еквівалентності елемента множини за заданим на цій множині відношенням еквівалентності є підмножина множини , що складається з елементів еквівалентних :
Класи еквівалентності між елементами структур часто використовуються для отримання меншої структури, елементами якої є класи. Зв'язок кожного елемента класу поділяється принаймні з одним іншим елементом іншого класу. Клас можна вважати тотожністю одного з оригінальних елементів.
Властивості
ред.- Множина всіх класів еквівалентності множини називається фактор-множиною і є розбиттям множини
- Кожен елемент x з X є членом класу еквівалентності [x]. Кожні два класи еквівалентності [x] і [y] або дорівнюють, або не перетинаються. Таким чином, множина всіх класів еквівалентності X утворює розбиття множини X: кожен елемент X належить одному і тільки одному класу еквівалентності.
- x ~ y, тоді і тільки тоді, коли x і y належать до одного і того ж самого розділу множини.
З властивостей відношення еквівалентності випливає, що
- x ~ y, тоді і тільки тоді, коли [x] = [y].
Іншими словами, якщо ~ є відношення еквівалентності на множині X, то ці твердження еквівалентні:
- .
Позначення і формальне визначення
ред.Відношення еквівалентності є бінарним відношенням, яке має три властивості:
- Для кожного елемента a із X, a ~ a (рефлексивність),
- Для кожних двох елементів a і b з X, якщо a ~ b, то і b ~ a (симетрія)
- Для кожних трьох елементів a, b і c з X, якщо a ~ b і b ~ c, то a ~ c (транзитивність).
Клас еквівалентності елемента a позначається [a] і може визначатися як множина.
Альтернативне позначення [a]R може бути використане для позначення класу еквівалентності елемента зокрема у відношенні R. Це називається R-класу еквівалентність. Множина всіх еквівалентних класів в X даного відношення еквівалентності позначається як X/~ і називається фактор-множина X на ~. Кожне відношення еквівалентності має канонічну проєкцію, сюр'єктивну функцію π з X де X/~ задано π(x) = [x].
Приклади
ред.- Якщо X є множиною всіх автомобілів, і ~ є відношенням еквівалентності «має той же колір», то кожен клас еквівалентності складається з автомобілів однакового кольору. Наприклад, всі зелені автомобілі належать одному класу. Кількість класів X/~ дорівнює числу всіх кольорів автомобілів.
- Розглянемо відношення еквівалентності на множині цілих чисел: x ~ y, тоді і тільки тоді, коли їх різниця x − y парне число. Це співвідношення призводить до двох класів еквівалентності: один клас, що складається з усіх парних чисел, та другий, який складається з усіх непарних чисел. Клас парних чисел позначається, як [0], непарних як [1]. Згідно з цим співвідношенням [7], [9], та [117] належать одному класу — [1].
- Нехай X множина впорядкованих пар цілих чисел (a,b), де b не дорівнює нулю, і характеризує відношення еквівалентності ~ на X. Відповідно до якого (a,b) ~ (c,d), тоді і тільки тоді, коли ad = bc. Класу еквівалентності пари (a,b) можна поставити у відповідність раціональне число a/b, таким чином, це відношення еквівалентності і його класи еквівалентності можуть бути використані як формальне визначення множини раціональних чисел. Наприклад, еквівалентним парам (1,3), (2,6), (5,15), відповідає рівність дробів .
- Відношення рівності за модулем ( ) на множині цілих чисел є відношенням еквівалентності. Класи еквівалентності
- Нехай дане число де Тоді всяку групу цифр називають класом. Група цифр — перший клас (клас одиниць), — другий клас (клас тисяч) тощо.
- Нехай є підгрупою групи У групі діє закон еквівалентності: якщо . Виникає клас суміжності групи по групі .
Факторизація відображень
ред.Відображення
називається природним відображенням (або канонічної проєкцією) на фактор-множину . Нехай , — множини, - відображення, тоді бінарне відношення визначене правилом
є відношенням еквівалентності на . При цьому відображення індукує відображення , яке визначається правилом
або, що те ж саме,
- .
При цьому виходить факторизація відображення на сюр'єктивне відображення і ін'єктивне відображення .
Див. також
ред.Джерела
ред.- Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)
- Хаусдорф Ф. Теория множеств. — Москва ; Ленинград : ОНТИ , 1937. — 304 с. — ISBN 978-5-382-00127-2.(рос.)
- Курош А. Г. Общая алгебра. — М. : Мир, 1970. — 162 с.(рос.)
- Кон П. Универсальная алгебра. — Москва : Мир, 1968. — 351 с.(рос.)