Отношение эквивалентности. Бинарное отношение r, заданное на множестве М, называется отношением эквивалентности или просто эквивалентностью

Бинарное отношение r, заданное на множестве М, называется отношением эквивалентности или просто эквивалентностью, если оно рефлексивно, транзитивно и симметрично. Для обозначения этого отношения чаще используется запись a ~ b без указания r.

Значение этого отношения заключается в том, что с помощью него множество разбивается в объединение попарно непересекающихся подмножеств (классов эквивалентности).

Пусть «~» – эквивалентность на множестве М. Подмножество К_а Í М, состоящее из всех элементов М, эквивалентных элементу а Î М, называется классом эквивалентности элемента а по отношению «~», т.е. К_а ={ х: х ~ а, где а, х Î М }.

Утверждения:

1) Два класса эквивалентности множества М либо совпадают, либо не пересекаются.

Действительно, если два класса эквивалентности К_а Í М и К_b Í М имеют общий элемент с Î М, то для любого элемента х Î К_а следует: х ~ а и а ~ с и с ~ b и по транзитивности x ~ b. Значит, x Î К_b и наоборот. Следовательно, К_а = К_b. Теперь предположим, что классы К_а и К_b пересекаются, тогда они имеют общий элемент с Î М, такой что с Î К_а и с Î К_b. Но тогда, как было доказано, К_а = К_b.

2) Любой элемент множества М попадает в один и только один класс эквивалентности. Поэтому множество М разбивается на попарно непересекающиеся классы эквивалентных между собой элементов.

Множество всех классов эквивалентности для М по отношению «~» называется фактор–множеством и обозначается М /~. А процесс разбиения М на классы эквивалентности называется факторизацией.

Примеры:

1) Отношение равенства на любом множестве является эквивалентностью. Соответствующее ему разбиение на классы есть объединение всех одноэлементных подмножеств данного множества.

2) На множестве всех целых чисел рассмотрим отношение r, согласно которому (x, y)Î r, если х и у имеют одинаковые знаки. Ясно, что это отношение рефлексивно, транзитивно и симметрично, следовательно, r – эквивалентность. Тогда соответствующая факторизация множества ℤ /~=ℤ^‑∪ℤ⁺∪{0}, т.к. число 0 эквивалентно только себе.

3) На множестве всех натуральных чисел рассмотрим отношение r, согласно которому (x, y)Î r, если они имеют одинаковый остаток при делении на одно и то же фиксированное натуральное число m, или как говорят, сравнимы по модулю m: (x mod m) = (y mod m). Заданное отношение – эквивалентность. По этому отношению множество ℕ разбивается на классы чисел, сравнимых по модулю m. Это следующие классы:
K₀ – числа, делящиеся на m без остатка, т.е. К₀={ x Îℕ: x mod m =0};
K₁ – числа, дающие при делении на m остаток 1, т.е. К₁={ x Îℕ: x mod m =1};
K₂ – числа, дающие при делении на m остаток 2, т.е. К₂={ x Îℕ: x mod m =2};
………
K _m _–1 – числа, дающие остаток m –1, т.е. К _m _–1={ x Îℕ: x mod m = m –1}.