Глава 3. Упорядоченные множества

Множество всех подмножеств множества М называется булеаном и обозначает­ся 2^М:

2^М = {А| АМ}

Теорема.Для конечного множества М |2^М| = 2^|M|

Доказательство:

Индукция по |M|. База: если |M| = 0, то М= Ø и 2^Ø = {Ø}. Следовательно,

|2^Ø | = |{Ø}| = 1 = 2⁰=2^|Ø|.

Индукционный переход: пусть M |М| <k→|2^М| = 2^|M|. Рассмотрим М = {а₁,... ,a_k},

|М| = k. Положим

M₁ = {X 2^M |a_kϵX} иМ₂ = {X2^м | a_kX}.

Имеем 2^M = M₁UМ₂ и Mi∩М₂ = Ø. По индукционному предположению |M₁| = 2^k-1,

|M₂| = 2^k-1. Следовательно, |2^М| = |M₁| + |M₂| =2^k-1 + 2^k-1=2×2^k-1 =2^k=2^М.

Пример. Пусть X = {1,2,3}. Тогда множество всех подмножеств X будет

2^X = {0, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, X}.