Размеўения и перестановки с повторениями и без повторений. Сочетания без повторений и их свойства

Теорема 1.4. Для любого отношения эквивалентности на множестве множество классов эквивалентности образует разбиение множества . Обратно, любое разбиение множества задает на нем отношение эквивалентности, для которого классы эквивалентности совпадают с элементами разбиения.
Покажем, что отношение эквивалентности на множестве определяет некоторое разбиение этого множества. Убедимся вначале, что любые два класса эквивалентности по отношению либо не пересекаются, либо совпадают.
Пусть два класса эквивалентности и имеют общий элемент . Тогда и . В силу симметричности отношения имеем , и тогда и . В силу транзитивности отношения получим . Пусть , тогда . Так как , то и, следовательно, .
Обратно, если , то в силу симметричности получим и в силу транзитивности — , то есть . Таким образом, .
Итак, любые два не совпадающих класса эквивалентности не пересекаются. Так как для любого справедливо (поскольку ), т.е. каждый элемент множества принадлежит некоторому классу эквивалентности по отношению , то множество всех классов эквивалентности по отношению образует разбиение исходного множества . Таким образом, любое отношение эквивалентности однозначно определяет некоторое разбиение.
Теперь пусть — некоторое разбиение множества . Рассмотрим отношение , такое, что имеет место тогда и только тогда, когда и принадлежат одному и тому же элементу данного разбиения:
Очевидно, что введенное отношение рефлексивно и симметрично. Если для любых и имеет место и , то и в силу определения отношения принадлежат одному и тому же элементу разбиения. Следовательно, и отношение транзитивно. Таким образом, — эквивалентность на .

Фактор-множество

Теорема 1.4 позволяет отождествлять отношения эквивалентности и разбиения: любая эквивалентность определяет единственное разбиение и наоборот.
Множество всех классов эквивалентности по данному отношению эквивалентности на множестве называют фактор-множеством множества по отношению и обозначают .