# 定義 $X$を任意の集合とするとき、その部分集合全体の作る[[集合系]]、すなはち$X$のすべての部分集合の集合を「$X$の冪集合$\mathcal{P}(X)$」という # 例 $X = \{a, b, c\}$なら、$\mathcal{P}(X) = \phi, \{a\}, \{b\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}$ # 定理 1. $X$が$n$個の元からなる有限集合であれば、$\mathcal{P}(X)$の要素数は$2^n$ [[数学的帰納法]]による証明: $n=1$のとき: 冪集合は$\phi, X$ $n \geq 2$のとき: $X = \{1, 2, ..., n\}$, $X' = \{1, 2, ..., n-1\}$とする。冪集合のうち、$X$の部分集合で$n$を含まないものは$X'$の部分集合である。 帰納法の仮定より、$X'$の部分集合は$2^{n-1}$個存在する。 $X$の部分集合で$n$を含むものは、$X'$の部分集合に$n$をつけて得られるので、$2^{n-1}$個存在する。 これより、$X$の部分集合は$2^{n-1} + 2^{n-1} = 2^{n}$個存在する # 記法 - $\mathcal{P}(X)$ - $2^X$と書くこともある - $\mathfrak{P}(S)$とも