Булеан

Булеан (степень множества, показательное множество, множество частей) — множество всех подмножеств данного множества [math]\displaystyle{ A }[/math] (включая нулевое и само множество А), обозначается [math]\displaystyle{ \mathcal P(A) }[/math] или [math]\displaystyle{ 2^A }[/math] (так как оно соответствует множеству отображений из [math]\displaystyle{ A }[/math] в [math]\displaystyle{ \{ 0,1\} }[/math]).

Если два множества равномощны, то равномощны и их булеаны. Обратное утверждение (то есть инъективность операции [math]\displaystyle{ \kappa \mapsto 2^\kappa }[/math] для кардиналов) является независимым от ZFC.

В категории множеств можно снабдить функцию [math]\displaystyle{ \mathcal{P} }[/math] структурой ковариантного или контравариантного функтора следующим образом:

ковариантный функтор отображает функцию [math]\displaystyle{ f\colon A\to B }[/math] в функцию [math]\displaystyle{ \mathcal{P}f\colon \mathcal{P}A \to \mathcal{P}B }[/math] такую, что она отображает [math]\displaystyle{ X }[/math] в образ [math]\displaystyle{ X }[/math] относительно [math]\displaystyle{ f }[/math];
контравариантный функтор отображает функцию [math]\displaystyle{ f\colon A\to B }[/math] в [math]\displaystyle{ \mathcal{P}f\colon \mathcal{P}B \to \mathcal{P}A }[/math] такую, что она отображает [math]\displaystyle{ X }[/math] в полный прообраз [math]\displaystyle{ X }[/math] относительно [math]\displaystyle{ f }[/math].

Открытая математическая проблема: cуществуют ли такие бесконечные множества [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math], что мощность множества [math]\displaystyle{ A }[/math] меньше мощности множества [math]\displaystyle{ B }[/math] и мощность множества [math]\displaystyle{ B }[/math] меньше мощности множества всех подмножеств множества [math]\displaystyle{ A }[/math]: [math]\displaystyle{ | A | \lt | B | \lt | 2^{A} | }[/math] ?^[1]

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

Справедливо следующее утверждение: число подмножеств конечного множества, состоящего из [math]\displaystyle{ n }[/math] элементов, равно [math]\displaystyle{ 2^n }[/math]. Результат доказывается методом математической индукции. В базе, у пустого множества [math]\displaystyle{ \varnothing }[/math]([math]\displaystyle{ n=0 }[/math]) только одно подмножество — оно само, и [math]\displaystyle{ 2^0=1 }[/math]. На шаге индукции утверждение считается установленным для множеств мощности [math]\displaystyle{ n }[/math] и рассматривается произвольное множество [math]\displaystyle{ M }[/math] с кардинальным числом [math]\displaystyle{ n+1 }[/math]; зафиксировав некоторый элемент [math]\displaystyle{ a_0\in M }[/math], подмножества множества [math]\displaystyle{ M }[/math] разделяются на два семейства:

[math]\displaystyle{ M_1 }[/math], содержащие [math]\displaystyle{ a_0 }[/math],
[math]\displaystyle{ M_2 }[/math], не содержащие [math]\displaystyle{ a_0 }[/math], то есть являющиеся подмножествами множества [math]\displaystyle{ M \setminus \{ a_0 \} }[/math].

Подмножеств второго типа по предположению индукции [math]\displaystyle{ 2^n }[/math], подмножеств первого типа ровно столько же, так как подмножество такого типа получается из некоторого и притом единственного подмножества второго типа добавлением элемента [math]\displaystyle{ a_0 }[/math] и, следовательно:

[math]\displaystyle{ 2^M = M_1 \bigcup M_2 }[/math] и [math]\displaystyle{ M_1 \bigcap M_2 = \varnothing }[/math].

По индукционному предположению [math]\displaystyle{ \left| M_1 \right| = 2^n }[/math] и [math]\displaystyle{ \left| M_2 \right| = 2^n }[/math], то есть:

[math]\displaystyle{ \left| 2^M \right| = \left| M_1 \right| + \left| M_2 \right| = 2^n + 2^n = 2^{n+1} = 2^\left| M \right| }[/math].

См. также

Примечания

↑ Брудно, 1971, с. 34.

Литература

Брудно А. Л. Теория функций действительного переменного. — М.: Наука, 1971. — 119 с.

[_46c665f65fc6a745-1] Брудно, 1971, с. 34.

[1]