Пусть R — бинарное отношение на множестве А, т.е. R⊂А².

Отношение R называется отношением эквивалентности (эквивалентностью) если оно рефлексивно, симметрично и транзитивно. Эквивалентность часто обозначают символом ∼ (тильда), т.е. вместо записи xRy пишут x∼y и говорят «x (икс) эквивалентен y (игрек)». Важность отношения эквивалентности объясняется наличием следующего утверждения.

Теорема. Если на множестве A задано отношение эквивалентности R, то множество A разбивается на непересекающиеся множества A₁, A₂, …, эквивалентных друг другу элементов. Множества A₁, A₂, … называются классами эквивалентности.

Множество, состоящее из классов эквивалентности, называется фактор-множеством и обозначается 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}}.