Пусть R – бинарное отношение на множестве X. Отношение R называется рефлексивным, если (x, x) Î R для всех x Î X; симметричным – если из (x, y) Î R следует (y, x) Î R; транзитивным числу 23 соответствует вариант 24 если (x, y) Î R и (y, z) Î R влекут (x, z) Î R.
Пример 1
Будем говорить, что x Î X имеет общее с элементом y Î X, если множество x Ç y не пусто. Отношение иметь общее будет рефлексивным и симметричным, но не транзитивным.
Отношением эквивалентности на X называется рефлексивное, транзитивное и симметричное отношение. Легко видеть, что R Í X ´ X будет отношением эквивалентности тогда и только тогда, когда имеют место включения:
IdX Í R (рефлексивность),
R-1 Í R (симметричность),
R ° R Í R (транзитивность).
В действительности эти три условия равносильны следующим:
IdX Í R, R-1 = R, R ° R = R.
Разбиением множества X называется множество А попарно непересекающихся подмножеств a Í X таких, что UA = X. С каждым разбиением А можно связать отношение эквивалентности ~ на X, полагая x ~ y, если x и y являются элементами некоторого a Î A.
Каждому отношению эквивалентности ~ на X соответствует разбиение А, элементами которого являются подмножества, каждое из которых состоит из находящихся в отношении ~. Эти подмножества называются классами эквивалентности. Это разбиение А называется фактор-множеством множества X по отношению ~ и обозначается: X/~.
Пример 2
Определим отношение ~ на множестве w натуральных чисел, полагая x ~ y, если остатки от деления x и y на 3 равны между собой. Тогда w/~ состоит из трёх классов эквивалентности, соответствующих остаткам 0, 1 и 2.