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 \textit{+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}.\) ，𝕄0s ，IND𝕄 ，suc𝕄 ，+𝕄 ，*𝕄 ，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 \textit{+1} )\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，𝕄0s ，IND𝕄 ，suc𝕄 ，+𝕄 ，*𝕄 ，fusc𝕄

2 有理数

2.1 順序対・写像

word(ss,s)F … \(\mathsf{pr}\)
abbr … \(\langle X , Y \rangle\) ≈ \(\mathsf{pr} ( X , Y )\)
word(s,s) … \(\triangleleft\)  \(\triangleright\)
◁. … \(\triangleleft \langle x , y \rangle = x\)
▷. … \(\triangleright \langle x , y \rangle = y\)
pr:0 … \(\langle x_{0} , y_{0} \rangle = \langle x_{1} , y_{1} \rangle \Longleftrightarrow x_{0} = x_{1} , y_{0} = y_{1}\) \(\blacktriangleleft\) \(\mathbb{W}.\)
word(ss,s) … \(\times\)
^^pr. … \(X \times Y = \{ \langle x , y \rangle \mid x \in X , y \in Y \}\)
\(X \to Y\) は \(X\) から \(Y\) への写像全体の集合、\(X \overset{S}{\to} Y\) は全射全体の集合。
word(ss,s) … \(\to\)  \(\stackrel{\rm S}\to\)
→. … \(X \to Y = \{ f \subset X \times Y \mid \forall x \in X . \exists! y \, \langle x , y \rangle \in f \}\)
→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 \}\)

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}\)

3 主定理

偶数 \(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_s ，𝕄0s ，IND𝕄 ，suc𝕄 ，+𝕄 ，*𝕄 ，fusc𝕄 ，÷K