Теорема. Всякое отношение эквивалентности на множестве А определяет некоторое разбиение множества А на подмножества

Всякое отношение эквивалентности на множестве А определяет некоторое разбиение множества А на подмножества, и обратно, всякое разбиение множества, определяет отношение эквивалентности на множестве А.

Доказательство

1) Пусть Е – отношение эквивалентности на множестве А, тогда А/Е фактор множество множества А по отношению Е.

Так как в силу рефлексивности Е , то каждое из множеств А/Е не пусто и .

Чтобы установить, что А/Е – разбиение множества А остается установить, что если .

Пусть и , то есть .

Так как отношение Е – симметрично, то

в силу транзитивности, если

и , то

еще раз используем свойство транзитивности, если

и , то и .

То есть . Включение доказывается аналогично.

2) Предположим, что Е отношение на множестве А, соответствующее разбиению R={A_i}. Покажем рефлексивность, симметричность и транзитивность отношения Е, задав его следующим образом:

- рефлексивность

, следовательно существует i, такое что , отсюда и . Значит .

- симметричность

значит существует i, такое что и , следовательно существует i, такое что и . Отсюда .

- транзитивность

, значит существует i, такое что и и существует j, такое что и , то есть и , но система классов не пересекается, следовательно i=j. Отсюда .