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

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

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

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

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

Множина всіх класів еквівалентності множини $\ S$ називається фактормножиною і є розбиттям множини $\ S.$

Кожен елемент $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$ із $X$ , $a ~ a$ (рефлексивність),
Для кожних двох елементів $a$ і $b$ з $X$ , якщо $a ~ b$ , то і $b ~ a$ (симетрія)
Для кожних трьох елементів $a$ , $b$ і $c$ з $X$ , якщо $a ~ b$ і $b ~ c$ , то $a ~ c$ (транзитивність).

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

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

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

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

Якщо $X$ є множиною всіх автомобілів, і $~$ є відношенням еквівалентності «має той же колір», то кожен клас еквівалентності складається з автомобілів однакового кольору. Наприклад, всі зелені автомобілі належать одному класу. Кількість класів $X /~$ дорівнює числу всіх кольорів автомобілів.

Розглянемо відношення еквівалентності на множині $\mathbb{Z}$ цілих чисел: $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)$ , відповідає рівність дробів $\frac 13=\frac 26=\frac 5{15}$ .

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

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

$p\colon x \mapsto C_x$

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