\(n\) 個の集合の部分集合は \(2^n\) 個。部分集合と特性関数（\(X \to 2\)）の1対1対応で示す（52a と別の証明）。

1 準備

1.1 特性関数

\(A \subset X\) に、\(A\) の上で \(0\)、\(X \setminus A\) の上で \(1\) をとる特性関数 \(\chi_A : X \to 2\) を対応させると、全単射になる。
逆に、写像 \(f : X \to 2\) には逆像 \(f^{-1}[\{0\}]\) を対応させる。
\(\wp X \stackrel{\#}= X \to 2\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，ax_s

1.2 写像の個数

個数の等しい集合どうしの直積は、個数が等しい。
定義域に1点を足した写像は、元の写像とその1点での値の組に対応する。すなわち \(((n+1) \to m) =\# ((n \to m) \times m)\)。
L→s … \(n \in \mathbb{M} \Longrightarrow ( n \to m ) \times m \stackrel{\#}= ( n + 1 ) \to m\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，ax_s ，Ax𝕄
\(m\) 個の元それぞれの値を \(n\) 通りから選ぶので、\(m \to n\) は \(n^m\) 個。定義域の個数についての帰納法で示す。
L0 … \(0 \to n = 1\) \(\blacktriangleleft\) \(\mathbb{W}.\)
→=# … \(m , n \in \mathbb{M} \Longrightarrow m \to n \stackrel{\#}= n ^ m\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，ax_s ，Ax𝕄 ，+𝕄 ，⋅𝕄 ，↑𝕄

2 主定理

特性関数の全単射と写像の個数を組み合わせると、\(\wp n =\# (n \to 2) =\# 2^n\) となる。
\(n \in \mathbb{M} \Longrightarrow \wp n \stackrel{\#}= 2 ^ n\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，Ax𝕄 ，ax_s ，+𝕄 ，⋅𝕄 ，↑𝕄