Итак, ликбез по элементарной теории множеств.
Класс - это некоторая штука, которой могут принадлежать или не принадлежать другие штуки. Множество - это частный случай класса, но разница между этими понятиями нас сейчас волновать не должна. Также нас не будет волновать конкретная аксиоматика.
То есть, если у нас есть множество
, то для любого объекта
либо верно, что
, либо неверно, что
. Во втором случае будем писать
.
читается как "
принадлежит
", "
является элементом
", "
входит в
".
Множества определяются только своими элементами, то есть, если есть два множества
и
, и любой
либо одновременно входит в них, либо одновременно не входит, то эти множества равны. И наоборот - если найдется элемент
, который эти два множества различает (в одно входит, а в другое нет), то множества различны. Это определение равенства множеств. Формально:
. (В аксиоматических теориях импликацию влево называют аксиомой экстенсиональности)
Если в множестве только конечное число элементов, то его можно задать перечислением этих элементов. Запись
означает, что
тогда и только тогда, когда
есть одно из
. То есть
,
...
, а все остальные объекты не принадлежат
. Формально:
. Мы будем считать, что конечные множества существуют. В аксиоматических теориях это, как правило, доказывается.
Частный случай конечного множества - множество пустое
. Пустое множество, по определению - это множество, не содержащее элементов. То есть для любого
верно
. Нетрудно доказать (пользуясь определением равенства), что пустое множество единственно.
Элементами множеств могут быть множества. Например, если
- множество, то существует конечное множество
, для которого справедливо
, но
, если
. Например, имея пустое множество, можно сформировать множество
.
Утверждение.
.
Доказательство. Существует элемент
, а именно,
, который не принадлежит левому множеству, но принадлежит правому.
Теперь у нас есть уже по крайней мере два различных множества,
и
. Мы можем сформировать новые множества
и
.
Задача. Докажите, что все множества
,
,
и
различны.
Теперь о подмножествах. Множество
является подмножеством множества
, если любой элемент
множества
является также и элементом
. Формально:
. Например, множество
является подмножеством множества
, так как в первом множестве ровно один элемент
, и он является также и элементом второго множества. Формально, это следет из определения конечного множества:
,
.
Пустое множество является подмножеством любого множества, так как в нем нет элементов, а определение подмножества накладывает ограничения только на элементы. Формально это утверждение следует из принципа ex falso quodlibet (из лжи следует все, что угодно).
Никакое непустое множество подмножеством пустого быть не может, так как в непустом множестве элементы есть, а в пустом нет. То есть
является единственным подмножеством
.
Множество всех подмножеств (булеан) множества
обозначается
. Формально:
. В предыдущем пункте мы доказали, что
.
Подмножества множества
долны содержать только элементы множества
. Простейшими такими множествами (кроме пустого), являются одноэлементые. Нетрудно доказать, что
.
Теперь давайте рассмотрим множество
и внимательно выпишем все его элементы и подмножества.
- это конечное множество с двумя элементами
и
.
Подмножества множества
формируются из этих элементов. Во-первых, это пустое множество, во-вторых, это одноэлементые подмножества
и
, и в-третьих, это само множество
. Таким образом,
.
Упражнение. Докажите, что конечное множество с
элементами имеет ровно
подмножеств.