Булеан

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

Пусть A — множество. Множество всех подмножеств множества A называется булеаном A (также степенью множества (англ. power set), показательным множеством или множеством частей) и обозначается \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.


Доказательство проведем методом математической индукции.

База. Если 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-\left\{a_0\right\}.

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

Следовательно имеем 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|.

См. также[править | править исходный текст]