Покрытия, разбиения, множество-степень, классы эквивалентности. Понятие фактор-множества.

Возьмём для примера множество .

Множество всех подмножеств данного множества называется степенью множества (множество-степень). Число этих подмножеств . (доказывается мат индукцией)

Например: .

Под покрытием множества понимают такие подмножества, которые при объединении совпадают с . Например: , , тогда . Т.е. – блоки покрытия .

Система множеств, в которой все попарные пересечения множеств пусты, называется разбиением множества . Каждый элемент входит в один и только один класс разбиения. Т.е из предыдущего примера не являются разбиением.

Разбиением будут (например): , , .

При разбиении множества на подмножества используют понятие эквивалентности элементов. Для этого определяют, что значит «элемент x эквивалентен элементу y», после чего объединяют эквивалентные элементы в одно подмножество. При разумном понятии эквивалентности данное множество разбивается на взаимно непересекающиеся подмножества, объединение которых есть все множество.

Бинарное отношение называется отношением эквивалентности на множестве X, если оно рефлексивно, симметрично и транзитивно.

Далее символом X обозначается множество, на котором задано отношение эквивалентности R.

Каждое подмножество A из X называется классом эквивалентности, если:

1) оно состоит из эквивалентных друг другу элементов и

2) если эквивалентен хотя бы одному элементу из , то .

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

Доказательство. Пусть A и B – два класса эквивалентности из X. Допустим, что они пересекаются и c – общий элемент, то есть . Если x – произвольный элемент из A, то x~c. Поскольку , то и . Таким образом, . Аналогично доказывается, что . Итак, A = B. Теорема доказана.