Каждое множество порождает новое множество несколько необычным образом.
ОПРЕДЕЛЕНИЕ 1. Булеаном множестваA называется совокупность всех подмножеств множества A. Обозначение:
Примеры. (единственный элемент булеана – пустое множество). (у одноэлементного множества два подмножества: пустое и само множество).
Упражнение. Запишите булеаны множеств {a,b}, {a,b,c}. Подсчитайте число элементов каждого из булеанов.
Из предыдущего упражнения следует гипотеза, подтверждение которой это следующий факт.
Теорема 1. для конечного множества A. Здесь и далее |A| - число элементов конечного множества. Для множеств бесконечных смысл этому символу будет придан ниже.
Доказательство. Пусть A={a1,a2,…,an}. Каждому подмножеству A можно сопоставить вектор длины n, элементами которого являются числа 0 и 1, где единицы соответствуют тем элементам, которые входят в подмножество. Например, подмножеству {a1,a3}Ì{a1,a2,a3,a4} соответствует вектор (1,0,1,0). Справедливо и обратное: каждому вектору длины n из 0 и 1 соответствует подмножество A. Таким образом, число элементов булеана равно числу таких векторов. Но это просто число размещений с повторениями из 2 по n, т.е. (см. п. 1.2), что и требовалось.