冪集合

どんな集合にも、隠れた相棒がいる。それはその集合のすべての部分集合からなる集合で、冪集合（べきしゅうごう、power set）と呼ばれる。冪集合は元の集合よりも必ず真に大きくなる — 無限集合であっても例外ではない。冪集合は組合せ論、論理学、位相幾何学、計算機科学など幅広い分野に登場するので、早めに理解しておくと後々とても役に立つ。

定義

$A$ を集合とする。$A$ の冪集合 $\mathcal{P}(A)$ は、$A$ の部分集合をすべて元として持つ集合として定義される：

$$\mathcal{P}(A) \;\coloneqq\; \{S \mid S \subseteq A\}.$$

$\mathcal{P}(A)$ の元はそれ自体が集合であるという点が、最初はちょっと不思議に感じるかもしれない。どんな $A$ に対しても、必ず $\mathcal{P}(A)$ に含まれると保証される部分集合が2つある：

• $\emptyset \in \mathcal{P}(A)$：空集合はすべての集合の部分集合だから。
• $A \in \mathcal{P}(A)$：$A$ は常に自分自身の部分集合だから。

冪集合を順番に構成する

$A = \{1, 2, 3\}$ としよう。すべての部分集合を大きさごとにまとめると次のようになる：

大きさ	部分集合
0	$\emptyset$
1	$\{1\}$, $\{2\}$, $\{3\}$
2	$\{1,2\}$, $\{1,3\}$, $\{2,3\}$
3	$\{1,2,3\}$

したがって：

$$\mathcal{P}(\{1,2,3\}) = \bigl\{ \emptyset,\; \{1\},\; \{2\},\; \{3\},\; \{1,2\},\; \{1,3\},\; \{2,3\},\; \{1,2,3\} \bigr\}.$$

元の数を数えると $8$ 個ある。

冪集合の濃度

元の個数が $|A| = n$ の有限集合 $A$ に対して、

$$|\mathcal{P}(A)| = 2^n. \tag{1}$$

なぜ $2^n$ なのか？ $A$ の $n$ 個の元それぞれについて、「部分集合に含める」か「含めない」かの2択がある。$n$ 個すべての選択の組み合わせの総数は

$$\underbrace{2 \times 2 \times \cdots \times 2}_{n \text{ 個}} = 2^n$$

となる。これが $\mathcal{P}(A)$ を $2^A$ とも書く理由だ。

例で確認。 $|\{1,2,3\}| = 3$ なので、$|\mathcal{P}(\{1,2,3\})| = 2^3 = 8$。上で列挙した8つの部分集合と一致する。

小さいケースをいくつか覚えておくと便利だ：

| $|A|$ | $|\mathcal{P}(A)|$ | 例 | |-------|--------------------|----| | $0$ | $1$ | $\mathcal{P}(\emptyset) = \{\emptyset\}$ | | $1$ | $2$ | $\mathcal{P}(\{a\}) = \{\emptyset, \{a\}\}$ | | $2$ | $4$ | $\mathcal{P}(\{a,b\}) = \{\emptyset, \{a\}, \{b\}, \{a,b\}\}$ | | $3$ | $8$ | （上の例のとおり） | | $10$ | $1024$ | — |

$\mathcal{P}(\emptyset) = \{\emptyset\}$ は元を1個（空集合そのもの）持つことに注意 — 0個ではない。

二進文字列との対応

各部分集合 $S \subseteq A$ には、$A$ のどの元が $S$ に含まれるかを示す特性関数（とくせいかんすう、characteristic function）が対応する：

$$\mathbf{1}_S \colon A \to \{0, 1\}, \quad a \mapsto \begin{cases} 1 & a \in S \\ 0 & a \notin S \end{cases}$$

$A = \{1, 2, 3\}$ で元の順序を $(a_1, a_2, a_3) = (1, 2, 3)$ とすると、$\mathcal{P}(A)$ と長さ3の二進文字列の間に全単射（ぜんたんしゃ、bijection）が得られる：

部分集合	二進文字列 $(a_1, a_2, a_3)$
$\emptyset$	$(0,\;0,\;0)$
$\{1\}$	$(1,\;0,\;0)$
$\{2\}$	$(0,\;1,\;0)$
$\{3\}$	$(0,\;0,\;1)$
$\{1,2\}$	$(1,\;1,\;0)$
$\{1,3\}$	$(1,\;0,\;1)$
$\{2,3\}$	$(0,\;1,\;1)$
$\{1,2,3\}$	$(1,\;1,\;1)$

長さ3の二進文字列はちょうど $2^3 = 8$ 個あり、これは式 $(1)$ を独立に裏付けている。

この全単射 $\mathcal{P}(A) \cong \{0,1\}^A$ が、表記 $2^A$ の深い意味だ：$2$ は集合 $\{0, 1\}$ を表し、$\{0,1\}^A$ は $A$ から $\{0,1\}$ へのすべての写像の集合を意味する。

無限集合の冪集合

無限集合に対しては式 $(1)$ はそのまま使えないが、本質的な考え方は生き続ける。カントールの定理は、任意の集合 $A$ に対して $A$ から $\mathcal{P}(A)$ への全射（ぜんしゃ、surjection）は存在しないと述べている。すなわち：

$$|A| < |\mathcal{P}(A)|$$

これは、$A$ から $\mathcal{P}(A)$ への単射（$a \mapsto \{a\}$ という写像）は存在するが全単射は存在しないという意味だ。冪集合は、たとえ両方が無限であっても、元の集合よりも必ず真に大きい。

まとめ

• 冪集合 $\mathcal{P}(A)$ は $A$ のすべての部分集合からなる集合で、その元は集合である。
• $\mathcal{P}(A)$ には必ず $\emptyset$ と $A$ 自身が含まれる。
• 有限集合に対しては $|\mathcal{P}(A)| = 2^{|A|}$ — 元を含めるかどうかの二択の組み合わせ分だけ部分集合がある。
• 各部分集合は長さ $|A|$ の二進文字列に対応し、全単射 $\mathcal{P}(A) \cong \{0,1\}^A$ が得られる。これが別表記 $2^A$ の由来だ。
• カントールの定理：任意の集合 $A$ に対して $\mathcal{P}(A)$ は $A$ より真に大きく、$A$ から $\mathcal{P}(A)$ への全射 $A \twoheadrightarrow \mathcal{P}(A)$ は存在しない。