1 準備

1.1 自然数の演算

℘0 … \(\wp 0 = 1\) \(\blacktriangleleft\) \(\mathbb{W}.\)
word(ss,s) … \(\cdot\)
*𝕄 … \(\begin{cases} m \in \mathbb{M} \Longrightarrow m \cdot 0 = 0 \\ m , n \in \mathbb{M} \Longrightarrow m \cdot ( n \textit{+1} ) = ( m \cdot n ) + m \end{cases}\)
⋅∈𝕄 … \(m , n \in \mathbb{M} \Longrightarrow m \cdot n \in \mathbb{M}\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，ax_s ，+𝕄 ，*𝕄

word(ss,s) … ↑
↑𝕄 … \(\begin{cases} m \in \mathbb{M} \Longrightarrow m ^ 0 = 1 \\ m , n \in \mathbb{M} \Longrightarrow m ^ { n \textit{+1} } = ( m ^ n ) \cdot m \end{cases}\)
↑∈𝕄 … \(m , n \in \mathbb{M} \Longrightarrow m ^ n \in \mathbb{M}\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，ax_s ，+𝕄 ，*𝕄 ，↑𝕄

2 主定理

「\(n\) 元集合の部分集合は \(2^n\) 個」であることを \(n\) についての帰納法で示す。
\(n \cup \{n\}\) の部分集合は、\(n\) を含まないもの（\(\wp n\) の元）と、\(A \cup \{n\}\)（\(A \subset n\)）の形のものに分かれる。
2つは交わらず、\(A \mapsto A \cup \{n\}\) で後者は \(\wp n\) と対等。よって \(\wp n\) が \(2^n\) 個なら \(\wp(n \cup \{n\})\) は \(2^n + 2^n = 2^{n+1}\) 個。
\(n \in \mathbb{M} \Longrightarrow \wp n \stackrel{\#}= 2 ^ n\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，ax_s ，+𝕄 ，*𝕄 ，↑𝕄