冪集合
Contents
冪集合とは
冪集合 (英:power set) とは、与えられた集合の部分集合を元とし、それをすべて集めた集合族のこと。
\[ \mathfrak{P}(S) = \{A_i\mid A_i\sube S\} \]
記号 | 意味 |
---|---|
$S$ | 与えられた集合 |
$A$ | 部分集合 |
$\mathfrak{P}(S)$ | $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} \]