Булеан

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

Мощность конечного булеана[править | править вики-текст]

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

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

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

2^M = M_1 \bigcup M_2 и M_1 \bigcap M_2 = \varnothing.

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

\left| 2^M \right| = \left| M_1 \right| + \left| M_2 \right| = 2^n + 2^n = 2^{n+1} = 2^\left| M \right|.

См. также[править | править вики-текст]