Конечные множества

Большинство задач комбинаторики можно сформулировать как задачи теории конечных множеств. Поэтому целесообразно напомнить некоторые положения «теории конечных множеств».

Всякая совокупность объектов произвольного рода образует множество. При этом сами объекты называют элементами данного множества. Множества обозначают большими латинскими буквами, их элементы – малыми латинскими буквами.

Запись обозначает, что a есть элемент A, или а принадлежит А, а запись – a не является элементом множества A, или а не принадлежит множеству А.

Множество считают определённым, если о любом объекте можно сказать, является он элементом данного множества или нет.

По количеству элементов множества делят на пустые, конечные и бесконечные.

Пустым называют множество, не содержащее ни одного элемента. Обозначают такое множество символом Æ.

Если каждый элемент множества В принадлежит множеству А, то В называют подмножеством множества А.

Обозначают: или .

Читают: множество В входит в множество А или множество содержит множество В.

Теорема 1. Если и , то .

ÿ Доказательство проведем методом «от противного». Пусть множества и не совпадают. Тогда без ограничения общности можно считать, что существует элемент из множества , который не принадлежит множеству В. Следовательно, множество не может быть подмножеством множества . Однако по условию множество А является подмножеством множества В. Получили противоречие. Полученное противоречие доказывает справедливость равенства. Значит, множества и равны.

Теорема доказана.

На основе теоремы 1основан метод доказательства равенства множеств, который называют«методом включения».

Непустое подмножество множества называют собственным подмножеством, если .

Несобственными подмножествами множества являются пустое множество и само множество .

Бесконечным называют множество равномощное некоторому собственному подмножеству.

Конечным называют множество, которое не равномощно ни какому собственному подмножеству.

Количество элементов множества обозначают n(A).