Пусть R — бинарное отношение на множестве А, т.е. R⊂А2.
Отношение R называется отношением эквивалентности (эквивалентностью) если оно рефлексивно, симметрично и транзитивно. Эквивалентность часто обозначают символом ∼ (тильда), т.е. вместо записи xRy пишут x∼y и говорят «x (икс) эквивалентен y (игрек)». Важность отношения эквивалентности объясняется наличием следующего утверждения.
Теорема. Если на множестве A задано отношение эквивалентности R, то множество A разбивается на непересекающиеся множества A1, A2, …, эквивалентных друг другу элементов. Множества A1, A2, … называются классами эквивалентности.
Множество, состоящее из классов эквивалентности, называется фактор-множеством и обозначается A/R (или A/∼).
Теорема. Обозначим M[x] = {y|x∼y, y∈A} − множество элементов эквивалентных x.
1. Если x∼y, то M[x] = M[y]. Т.е., класс эквивалентности однозначно определяется любым своим элементом.
2. Если x не эквивалентен y, то M[x]∩M[y] = ∅.
Примеры.
1. Разбиение студентов на группы является отношением эквивалентности. Здесь два студента считаются эквивалентными, если они учатся в одной группе. Фактор-множество — множество групп ВУЗа.
2. Отношение равенства x = y является эквивалентностью на любом множестве A.
3. Отношение подобия на множестве треугольников.
4. Отношение R, заданное на множестве A = {1, 2, 3, 4, 5} графически (см. рис.), является отношением эквивалентности, т.к. оно рефлекcивно, симметрично и транзитивно. Фактор множество A/R = {{1, 4}, {2, 3, 5}}.