Булеан множества

Каждое множество порождает новое множество несколько необычным образом.

ОПРЕДЕЛЕНИЕ 1. Булеаном множестваA называется совокупность всех подмножеств множества A. Обозначение:

Примеры. (единственный элемент булеана – пустое множество). (у одноэлементного множества два подмножества: пустое и само множество).

Упражнение. Запишите булеаны множеств { a,b }, { a,b,c }. Подсчитайте число элементов каждого из булеанов.

Из предыдущего упражнения следует гипотеза, подтверждение которой это следующий факт.

Теорема 1. для конечного множества A. Здесь и далее | A | - число элементов конечного множества. Для множеств бесконечных смысл этому символу будет придан ниже.

Доказательство. Пусть A= { a ₁, a ₂,…, a_n }. Каждому подмножеству A можно сопоставить вектор длины n, элементами которого являются числа 0 и 1, где единицы соответствуют тем элементам, которые входят в подмножество. Например, подмножеству { a ₁, a ₃}Ì{ a ₁, a ₂, a ₃, a ₄} соответствует вектор (1,0,1,0). Справедливо и обратное: каждому вектору длины n из 0 и 1 соответствует подмножество A. Таким образом, число элементов булеана равно числу таких векторов. Но это просто число размещений с повторениями из 2 по n, т.е. (см. п. 1.2), что и требовалось.