Отношение эквивалентности

Определение

Определение:

Бинарное отношение [math]R[/math] на множестве [math]X[/math] называется отношением эквивалентности, если оно обладает следующими свойствами: Рефлексивность: [math]\forall x \in X: xRx[/math]. Симметричность: [math]\forall x, y \in X:[/math] если [math]xRy[/math], то [math]yRx[/math]. Транзитивность: [math]\forall x, y, z \in X:[/math] если [math]xRy[/math] и [math]yRz[/math], то [math]xRz[/math].

Отношение эквивалентности обозначают символом [math]\thicksim[/math]. Запись вида [math]a \thicksim b[/math] читают как "[math]a[/math] эквивалентно [math]b[/math]"

Примеры отношений эквивалентности

• Отношение равенства([math]=[/math]) является тривиальным примером отношения эквивалентности на любом множестве.
• Отношение равенства по модулю [math]k[/math]: [math]a \equiv b (mod~k)[/math] на множестве целых чисел.
• Отношение параллельности прямых на плоскости.
• Отношение подобия фигур на плоскости.
• Отношение равносильности на множестве уравнений.
• Отношение связности вершин в графе.
• Отношение быть одного роста на множестве людей.

Следующие отношения не являются отношениями эквивалентности:

• Отношения порядка, так как они не являются симметричными.
• Отношение быть знакомым на множестве людей, так как оно не транзитивное.

Классы эквивалентности

Определение:

Система непустых подмножеств [math]\{M_1, M_2, ..., M_n, ...\}[/math] множества [math]M[/math] называется разбиением данного множества, если: [math]M = M_1 \cup M_2 \cup ... \cup M_n \cup ...[/math] [math]M_i \cap M_j = \varnothing[/math] при [math]i \neq j[/math]. Множества [math]M_1, M_2, ..., M_n, ...[/math] называются классами данного разбиения.

Примерами разбиений являются:

• Разбиение многоугольников на группы по числу вершин.
• Разбиение треугольников по свойствам углов (остроугольные, прямоугольные, тупоугольные).
• Разбиение учащихся школы по классам.

Теорема:

Если на множестве M задано отношение эквивалентности [math]\thicksim[/math], то оно порождает разбиение этого множества на классы эквивалентности такое, что: любые два элемента одного класса находятся в отношении [math]\thicksim[/math] любые два элементы разных классов не находятся в отношении [math]\thicksim[/math]

Семейство всех классов эквивалентности множества образует множество, называемое фактор-множеством, или факторизацией множества [math]M[/math] по отношению [math]\thicksim[/math], и обозначаемое [math]M/^{\thicksim}[/math].

Ссылки

• Wikipedia | Отношение эквивалентности
• Бинарные отношения. Отношение эквивалентности