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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

[a] = \{ x \in S | x \sim a \}.

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

Властивості[ред.ред. код]

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

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

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

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

  • x \sim y
  • [x] = [y]
  • [x] \cap [y] \ne \emptyset.

Позначення і формальне визначення[ред.ред. код]

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

Клас еквівалентності елемента a позначається [a] і може визначатися як множина.

[a] = \{ x \in X \mid a \sim x \}

Альтернативне позначення [a]R може бути використане для позначення класу еквівалентності елемента зокрема у відношенні R. Це називається R-класу еквівалентність. Множина всіх еквівалентних класів в X даного відношення еквівалентності позначається як X/~ і називається фактормножина X на ~. Кожне відношення еквівалентності має канонічну проекцію, сюр'ективну функцію π з X де X/~ задано π(x) = [x].

Приклади[ред.ред. код]

  • Якщо X є множиною всіх автомобілів, і ~ є відношенням еквівалентності «має той же колір», то кожен клас еквівалентності складається з автомобілів однакового кольору. Наприклад, всі зелені автомобілі належать одному класу. Кількість класів X/~ дорівнює числу всіх кольорів автомобілів.
  • Розглянемо відношення еквівалентності на множині \Z цілих чисел: 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), відповідає рівність дробів \frac 13=\frac 26=\frac 5{15}.
  • Відношення рівності за модулем (\ a\equiv b\pmod n,\ a,b\in \Z) на множині цілих чисел \Z є відношенням еквівалентності. Класи еквівалентності \overline{a}_n=\left\{a, a \pm n, a \pm 2n, a \pm 3n, \ldots \right\}.

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

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

p\colon x \mapsto C_x

називається природним відображенням (або канонічної проекцією) X на фактормножину X/{\sim}. Нехай X, Y — множини, f\colon X \to Y- відображення, тоді бінарне відношення x \, {R_f} \,y визначене правилом

x \mathop{R_f} y \iff f(x) = f(y), \quad x, y \in X

є відношенням еквівалентності на X. При цьому відображення f індукує відображення \overline{f}\colon X/R_f \to Y, яке визначається правилом

\overline{f}(C_x) = f(x)

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

(\overline{f}\circ p)(x) = f(x).

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

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

Література[ред.ред. код]