冪集合とは

冪集合 (英：power set) とは、与えられた集合の部分集合を元とし、それをすべて集めた集合族のこと。

$\mathfrak{P}(S) = \{A_i\mid A_i\sube S\}$

空集合の冪集合

空集合 $\empty$ の部分集合は $\empty$ ただ一つであるため、冪集合 $\mathfrak{P}(\empty)$ は、$\empty$ のみから成る集合となる。なお $\mathfrak{P}(\empty)$ は空集合ではない。

$\begin{aligned} \mathfrak{P}(\empty) &= \lbrace\empty\rbrace \cr \mathfrak{P}(\empty) &\ne \empty \end{aligned}$

有限集合の冪集合の濃度

$\vert\mathfrak{P}(S)\vert = 2^n \quad (\vert S\vert=n)$

有限集合の冪集合の濃度の導出：

$n$ 個の元から成る有限集合 $S$ が与えられたとき、$S$ の冪集合 $\mathfrak{P}(S)$ の濃度は二項定理から、

$\begin{aligned} \vert S\vert &= n \cr \cr \vert\mathfrak{P}(S)\vert &= \sum_{k=1}^n\binom n k + \vert\lbrace\empty\rbrace\vert \cr &= \sum_{k=0}^n\binom n k \cr &= \sum_{k=0}^n\binom n k 1^n 1^{n-k} \cr &= (1+1)^n \cr &= 2^n \cr \cr \therefore \vert\mathfrak{P}(S)\vert &= 2^n \quad (\vert S\vert = n) \end{aligned}$

関連記事

• 部分集合
• 族
• 二項定理

参考文献

集合・位相入門

posted with amazlet at 19.10.30

松坂 和夫
岩波書店
売り上げランキング: 33,460

Amazon.co.jpで詳細を見る