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

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

Следовательно, в силу доказанных теорем 1.4 и 1.5 существует связь между тремя понятиями — отображением множества, отношением эквивалентности на множестве и разбиением множества. Но неверно, что существует взаимно однозначное соответствие между отображениями и отношениями эквивалентности (заметим, что теорема 1.5 этого и не утверждает). Два разных отображения могут определять одно и то же разбиение отображаемого множества, тем самым задавая на нем одно и то же отношение эквивалентности. Так, например, любое биективное отображение задает на одно и то же разбиение — тривиальное разбиение на одноэлементные множества.