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

Клас еквівалентності елемента $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]\neq \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 {1}{3}}={\frac {2}{6}}={\frac {5}{15}}$ .

Відношення рівності за модулем ( $\ a\equiv b{\pmod {n}},\ a,b\in \mathbb {Z}$ ) на множині цілих чисел $\mathbb {Z}$ є відношенням еквівалентності. Класи еквівалентності ${\overline {a}}_{n}=\left\{a,a\pm n,a\pm 2n,a\pm 3n,\ldots \right\}.$
Нехай дане число $a_{n}a_{n-1}\cdot \cdot \cdot a_{3}a_{2}a_{1},$ де $a_{i}=0,1,2,...,9.$ Тоді всяку групу цифр $a_{i+2}a_{i+1}a_{i},i\equiv 1{\pmod {3}}$ називають класом. Група цифр $a_{3}a_{2}a_{1}$ — перший клас (клас одиниць), $a_{6}a_{5}a_{4}$ — другий клас (клас тисяч) тощо.
Нехай $H$ є підгрупою групи $G.$ У групі $G$ діє закон еквівалентності: $x\sim y,$ якщо $xy^{-1}\in H$ . Виникає клас суміжності групи $G$ по групі $H$ .

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

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

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$ , яке визначається правилом