Клас еквівалентності

Клас еквівалентності елемента множини за заданим на цій множині відношенням еквівалентності є підмножина множини , що складається з елементів еквівалентних :

Класи еквівалентності між елементами структур часто використовуються для отримання меншої структури, елементами якої є класи. Зв'язок кожного елемента класу поділяється принаймні з одним іншим елементом іншого класу. Клас можна вважати тотожністю одного з оригінальних елементів.

Властивості

  • Кожен елемент x з X є членом класу еквівалентності [x]. Кожні два класи еквівалентності [x] і [y] або дорівнюють, або не перетинаються. Таким чином, множина всіх класів еквівалентності X утворює розбиття множини X: кожен елемент X належить одному і тільки одному класу еквівалентності.
  • x ~ y, тоді і тільки тоді, коли x і y належать до одного і того ж самого розділу множини.

З властивостей відношення еквівалентності випливає, що

x ~ y, тоді і тільки тоді, коли [x] = [y].

Іншими словами, якщо ~ є відношення еквівалентності на множині X, то ці твердження еквівалентні:

  • .

Позначення і формальне визначення

Відношення еквівалентності є бінарним відношенням, яке має три властивості:

Клас еквівалентності елемента 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), відповідає рівність дробів .
  • Відношення рівності за модулем () на множині цілих чисел є відношенням еквівалентності. Класи еквівалентності
  • Нехай дане число де Тоді всяку групу цифр називають класом. Група цифр  — перший клас (клас одиниць),  — другий клас (клас тисяч) тощо.
  • Нехай є підгрупою групи У групі діє закон еквівалентності: якщо . Виникає клас суміжності групи по групі .

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

Відображення

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

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

або, що те ж саме,

.

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

Див. також

Джерела

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.