有理数は可算：Calkin–Wilf 木（Stern の数列 fusc）を使って、自然数から有理数への全射を作る。

1 準備

どの自然数も偶数 \(2k\) か奇数 \(2k+1\) のどちらか（Lpar）。

2 自然数から有理数への全射の作成

2.1 Stern の数列

\({\rm fusc}\) は次の漸化式を満たす関数として仮定します（存在は示しません）。\(0, 1, 1, 2, 1, 3, 2, 3, 1, 4, \ldots\) と続く数列です。
word(s,s)F … \(\mathrm{fusc}\)
fusc𝕄 … \(\begin{cases} \mathrm{fusc} ( 0 ) = 0 \\ \mathrm{fusc} ( 1 ) = 1 \\ n \in \mathbb{M} \Longrightarrow \mathrm{fusc} ( 2 \cdot n ) = \mathrm{fusc} ( n ) \\ n \in \mathbb{M} \Longrightarrow \mathrm{fusc} ( 2 \cdot n + 1 ) = \mathrm{fusc} ( n ) + \mathrm{fusc} ( n + 1 ) \end{cases}\)
Lfusc … \(n \in \mathbb{M} \Longrightarrow \mathrm{fusc} ( n ) \in \mathbb{M} , ( n \neq 0 \Longrightarrow \mathrm{fusc} ( n ) \neq 0 )\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，Ax𝕄 ，ax_s ，+𝕄 ，⋅𝕄 ，fusc𝕄

Calkin–Wilf：どの \(a, b\)（\(b \neq 0\)）も、ある \(n\) と \(g\) で \(a = g\,{\rm fusc}(n)\)、\(b = g\,{\rm fusc}(n+1)\) と書ける。
\(a+b\) についての強い帰納法：\(a = 0\) なら \(n = 0\)。\(b \le a\) なら \((a-b, b)\) から \(2n+1\) へ、\(a < b\) なら \((a, b-a)\) から \(2n\) へ（互除法を逆にたどる）。
LCW … \(a , b \in \mathbb{M} , b \neq 0 \Longrightarrow \exists n \in \mathbb{M} . \exists g \in \mathbb{M} . a = g \cdot \mathrm{fusc} ( n ) , b = g \cdot \mathrm{fusc} ( n + 1 )\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，Ax𝕄 ，ax_s ，+𝕄 ，⋅𝕄 ，fusc𝕄

2.2 整数と有理数

整数は自然数 \(n\) と \(-n\)、有理数は分数 \(a \div b\)（\(a\) は整数、\(b\) は 0 でない自然数）。
\(-\) と \(\div\) については約分（÷K）だけを仮定します。
word(s,s) … \(-\)
word(ss,s) … \(/\)
word(,s) … \(\mathbb{Z}\)  \(\mathbb{Q}\)
ℤ. … \(\mathbb{Z} = \{ a \mid a \in \mathbb{M} \mathbin{\rm o\!r} \exists n \in \mathbb{M} . a = - n \}\)
ℚ. … \(\mathbb{Q} = \{ a / b \mid a \in \mathbb{Z} , b \in \mathbb{M} , b \neq 0 \}\)
÷K … \(\begin{cases} c , a , b \in \mathbb{M} , c \neq 0 \Longrightarrow ( c \cdot a ) / ( c \cdot b ) = a / b \\ c , a , b \in \mathbb{M} , c \neq 0 \Longrightarrow ( - ( c \cdot a ) ) / ( c \cdot b ) = ( - a ) / b \end{cases}\)

2.3 主定理

word(ss,s) … \(\stackrel{\rm S}\to\)
→S. … \(X \stackrel{\rm S}\to Y = \{ f \in X \to Y \mid \forall y \in Y . \exists x \, \langle x , y \rangle \in f \}\)
偶数 \(2n\) に \({\rm fusc}(n) \div {\rm fusc}(n+1)\)、奇数 \(2n+1\) に \(-{\rm fusc}(n) \div {\rm fusc}(n+1)\) を対応させる（Calkin–Wilf の数え上げに符号を付けたもの）。
有理数 \(\pm a \div b\) は、LCW で \(a = g\,{\rm fusc}(n)\)、\(b = g\,{\rm fusc}(n+1)\) と書いて約分すれば値に現れるので、この対応は全射。
\(\exists f \, f \in \mathbb{M} \stackrel{\rm S}\to \mathbb{Q}\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，Ax𝕄 ，ax_s ，+𝕄 ，⋅𝕄 ，fusc𝕄 ，÷K