1 組合せの数の準備

word(ss,s) … \(\mathrm{C}\)
choose𝕄 … \(\begin{cases} n \in \mathbb{M} \Longrightarrow n \mathrm{C} 0 = 1 \\ k \in \mathbb{M} \Longrightarrow 0 \mathrm{C} ( k + 1 ) = 0 \\ n , k \in \mathbb{M} \Longrightarrow ( n + 1 ) \mathrm{C} ( k + 1 ) = n \mathrm{C} k + n \mathrm{C} ( k + 1 ) \end{cases}\)
choose∈𝕄 … \(n , k \in \mathbb{M} \Longrightarrow n \mathrm{C} k \in \mathbb{M}\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，ax_s ，+𝕄 ，choose𝕄

1点を取り除くと個数は1つ減り（Lcan）、足すと1つ増える（Ladd）。
Lcan … \(Y \cup \{ a \} \stackrel{\#}= k + 1 , a \notin Y , k \in \mathbb{M} \Longrightarrow Y \stackrel{\#}= k\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，ax_s ，+𝕄

2 主定理

自然数 \(n\) は集合 \(\{0, \dots, n-1\}\) なので（0-sn）、\(A \subset n\) は \(n\) 個の元から選んだ部分集合。
\(n\) の \(k\) 元部分集合全体を \(S\) とすると \(S\) は \(n \mathrm{C} k\) 個（\(n \mathrm{C} k\) はパスカルの漸化式 choose𝕄 で与える。階乗の式 \(n!/(k!\,(n-k)!)\) との関係はこの本では示していない）。
主張は「そのような \(S\) がある」の形で書く（\(S\) は外延性で1つに決まる）。
\(k = 0\) なら空集合だけ。\(n = 0\) で \(k \ge 1\) なら1つも無い。
\(n+1\) の \(k+1\) 元部分集合は、\(n\) を含まないもの（\(n\) の \(k+1\) 元部分集合）と、\(B \cup \{n\}\)（\(B\) は \(n\) の \(k\) 元部分集合）に分かれる。
\(n \notin n\) なので \(B \mapsto B \cup \{n\}\) は単射で、2つの組は交わらない。
Lcomb … \(n , k \in \mathbb{M} \Longrightarrow \exists S \, \forall A \, ( A \in S \Longleftrightarrow A \subset n , A \stackrel{\#}= k ) , S \stackrel{\#}= n \mathrm{C} k\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，ax_s ，+𝕄 ，choose𝕄