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

(Перенаправлено з Класи еквівалентності)

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

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

Властивості

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

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

ред.

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

 

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

 

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

 

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

 .

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

Див. також

ред.

Джерела

ред.