Отношения эквивалентности, фактор - множества.

Рефлексивное, симметричное и транзитивное отношение называется эквивалентностью.

Пусть ~ есть эквивалентность на множестве M, а xÎM. Тогда множество [x]={y|y~x} называется классом эквивалентности, порожденным элементом x.

Фактор-множество множества относительно эквивалентности ~ – это семейство всех классов эквивалентности: M/~={[x]|xÎM}.

Теорема. Пусть на множестве M задана эквивалентность ~. Тогда семейство всех классов эквивалентности [x], xÎM, есть разбиение M на классы.

Доказательство. Проверим выполнение всех трех условий определения разбиения множества на попарно непересекающиеся классы:

1) для всех xÎM класс [x]¹Æ, [x]ÍM;

2) для всех x,yÎM классы [x] и [y] не пересекаются: [x]Ç[y]=Æ, где x¹y;

3) объединение всех классов [x], xÎM совпадает с множеством M.

Условие 1) следует из рефлексивности отношения ~.

Условие 2) из транзитивности и симметричности отношения ~. Действительно, если zÎ[x], zÎ[y], x,y,zÎM, то z~x, z~y, x~z, x~y, [x]=[y].

Условие 3) также следует из рефлексивности отношения ~.

Пример. Эквивалентность "ученики x и y учатся в одном классе" на множестве M всех учеников школы определяет разделение M на классы.