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

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

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

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

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

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

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

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