Булеан

Булеан (также степень множества, показательное множество, множество всех подмножеств) — это множество, элементами которого являются все возможные подмножества данного множества, включая пустое множество и само исходное множество. Для множества \(A\) булеан обычно обозначается как \(\mathcal{P}(A)\), \(2^{A}\) или \(P(A)\). Термин введён в честь английского математика и логика Джорджа Буля, основоположника математической логики и булевой алгебры.

Определение и обозначения

Пусть \(A\) — произвольное множество. Булеаном множества \(A\) называется множество \(\mathcal{P}(A)\), состоящее из всех подмножеств множества \(A\):

\[ \mathcal{P}(A) = \{ X \mid X \subseteq A \}. \]

Например, для множества \(A = \{a, b, c\}\) булеан состоит из восьми элементов:

\[ \mathcal{P}(A) = \{ \varnothing, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\} \}. \]

Обозначение \(2^{A}\) связано с тем, что для конечного множества из \(n\) элементов мощность булеана равна \(2^{n}\). В теоретико-множественной интерпретации \(2^{A}\) рассматривается как множество всех функций из \(A\) в двухэлементное множество \(\{0, 1\}\), что изоморфно множеству всех подмножеств.

Мощность булеана

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

Для конечного множества \(A\), содержащего \(n\) элементов, мощность булеана равна \(2^{n}\). Это следует из комбинаторного принципа: каждый элемент множества может либо входить, либо не входить в подмножество, что даёт \(2^{n}\) различных комбинаций. Например:

• Если \(|A| = 0\) (пустое множество), то \(\mathcal{P}(A) = \{\varnothing\}\), его мощность равна \(1 = 2^{0}\).
• Если \(|A| = 1\), то \(\mathcal{P}(A) = \{\varnothing, A\}\), мощность равна \(2 = 2^{1}\).
• Если \(|A| = 2\), то \(\mathcal{P}(A)\) содержит 4 элемента: \(\varnothing\), \(\{a\}\), \(\{b\}\), \(\{a, b\}\).

Бесконечные множества

Для бесконечных множеств мощность булеана строго больше мощности исходного множества. Этот результат известен как теорема Кантора: для любого множества \(A\) (как конечного, так и бесконечного) мощность \(\mathcal{P}(A)\) строго больше мощности \(A\). В частности, для счётного множества (например, множества натуральных чисел \(\mathbb{N}\)) мощность булеана равна мощности континуума (обозначается \(\mathfrak{c}\) или \(2^{\aleph_0}\)), которая несчётна. Теорема Кантора доказывается методом диагонализации и показывает, что не существует наибольшего кардинального числа.

Свойства булеана

Алгебраические свойства

Булеан любого множества образует булеву алгебру относительно операций объединения (\(\cup\)), пересечения (\(\cap\)) и дополнения (\(\setminus\)). Эта алгебра является полной и атомистической: атомами служат одноэлементные подмножества. В булевой алгебре \(\mathcal{P}(A)\) выполняются все аксиомы булевой алгебры:

• Коммутативность, ассоциативность и дистрибутивность операций.
• Существование нейтральных элементов: пустое множество (\(\varnothing\)) для объединения и само множество \(A\) для пересечения.
• Существование дополнения: для каждого подмножества \(X \subseteq A\) его дополнение \(A \setminus X\) также является подмножеством \(A\).

Теоретико-множественные свойства

• Булеан содержит пустое множество и само исходное множество.
• Для любых двух множеств \(A\) и \(B\) выполняется: \(\mathcal{P}(A \cap B) = \mathcal{P}(A) \cap \mathcal{P}(B)\).
• \(\mathcal{P}(A \cup B) \supseteq \mathcal{P}(A) \cup \mathcal{P}(B)\), причём равенство достигается только в случае, когда одно из множеств является подмножеством другого.
• Булеан декартова произведения множеств не равен декартову произведению булеанов: \(\mathcal{P}(A \times B) \neq \mathcal{P}(A) \times \mathcal{P}(B)\).

Связь с характеристическими функциями

Каждому подмножеству \(X \subseteq A\) можно поставить в соответствие характеристическую функцию \(\chi_X : A \to \{0, 1\}\), где \(\chi_X(a) = 1\) если \(a \in X\) и \(0\) в противном случае. Множество всех таких функций изоморфно булеану, что оправдывает обозначение \(2^{A}\).

Примеры

Пример 1: Конечное множество

Для множества \(A = \{1, 2\}\): \[ \mathcal{P}(A) = \{\varnothing, \{1\}, \{2\}, \{1, 2\}\}. \] Мощность: \(4 = 2^{2}\).

Пример 2: Пустое множество

Для \(A = \varnothing\): \[ \mathcal{P}(\varnothing) = \{\varnothing\}. \] Мощность: \(1 = 2^{0}\).

Пример 3: Бесконечное множество

Для множества натуральных чисел \(\mathbb{N}\) булеан \(\mathcal{P}(\mathbb{N})\) несчётен. Его мощность равна мощности континуума, то есть мощности множества всех действительных чисел \(\mathbb{R}\). Это означает, что между \(\mathbb{N}\) и \(\mathcal{P}(\mathbb{N})\) не существует биекции.

Применение

Математика

Булеан широко используется в теории множеств, топологии, теории меры и функциональном анализе. В топологии булеан множества служит основой для построения дискретной топологии (где все подмножества считаются открытыми). В теории меры булеан используется для определения сигма-алгебр и измеримых множеств.

Информатика и дискретная математика

В информатике булеан применяется для представления всех возможных комбинаций битовых строк, при анализе алгоритмов перебора и в теории графов (например, для построения булеана вершин графа при решении задачи о независимом множестве). В комбинаторике булеан используется для подсчёта числа подмножеств и в задачах, связанных с бинарными отношениями.

Логика и теория типов

В математической логике булеан множества пропозициональных переменных соответствует множеству всех возможных интерпретаций (истинностных значений). В теории типов булеан интерпретируется как тип всех подмножеств (или предикатов) над заданным типом.

Интересные факты

• Теорема Кантора о строгом возрастании мощности булеана является одним из фундаментальных результатов теории множеств. Она показывает, что не существует «множества всех множеств» — такое понятие приводит к парадоксам (например, парадоксу Рассела).
• Булеан множества мощности \(n\) содержит ровно \(2^{n}\) элементов, что делает его удобным инструментом для демонстрации экспоненциального роста комбинаторных пространств.
• В контексте аксиоматической теории множеств (например, ZFC) существование булеана для любого множества гарантируется аксиомой степени (или аксиомой булеана).

Источники

• Куратовский К., Мостовский А. Теория множеств. — М.: Мир, 1970.
• Хаусдорф Ф. Теория множеств. — М.: КомКнига, 2006.
• Ершов Ю. Л., Палютин Е. А. Математическая логика. — М.: Наука, 1987.
• Халмош П. Теория множеств. — М.: Иностранная литература, 1960.