有理数の付番 - 簡潔なQ

概要

有理数の付番の計算しやすい定義を与えた。

はじめに

有理数 ( $\mathbb{Q}$ ) は自然数 ( $\mathbb{N}$ ) と同じくらいの個数しかない(可算)というのはよく知られています。これは通常、以下のような理屈で納得されます。

$0, 1, -1, 2, -2, 3, -3, \ldots$ のように付番することで、 $\mathbb{Z}$ は $\mathbb{N}$ と同じくらいしかないことがわかる。
$(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), \ldots$ のように付番することで、 $\mathbb{N} \times \mathbb{N}$ は $\mathbb{N}$ と同じくらいしかないことがわかる。
$\mathbb{Q}$ は分子と分母の組で表せるので、 $\mathbb{N}$ と同じかそれより少ないとわかる。
一方、自然数はそのまま有理数なので、 $\mathbb{N}$ は $\mathbb{Q}$ と同じかそれより少ないとわかる。
したがって、 $\mathbb{N}$ と $\mathbb{Q}$ は同じくらいしかない (この推論をCantor-Bernstein-Schröderの定理という)

しかし以下のようにすると、具体的な付番を与えることができます:

了解1.1 $\mathbb{N}$ は0以上の整数全てからなる集合を指すこととする。自然数という言葉も同様の意味で用いる。また、 $\mathbb{N}^+$ を1以上の整数全てからなる集合とする。

定義1.2 $f\colon \mathbb{Q} \to \mathbb{N}$ を以下のように定義する。

$f(q) = 2f(1 / (q - 1)) + 2$ 　　　 ( $1 \lt q$ の場合)
$f(q) = 2f(1 / q - 1) + 1$ 　　　 ( $0 \lt q \le 1$ の場合)
$f(q) = 0$ 　　　　　　　　　　　　 ( $q = 0$ の場合)
$f(q) = 2f(1 / q + 1) + 2$ 　　　 ( $-1 \le q \lt 0$ の場合)
$f(q) = 2f(1 / (q + 1)) + 1$ 　　　 ( $q \lt -1$ の場合)

証明

では、これが実際に付番として機能することを証明していきます。証明とかよくわからない人は飛ばしてもOKです。

定理1.3 $f$ は矛盾なく定義される。

(証明) 方程式中の除算は以下のように正当化される。

1番目の方程式では $1 \lt q$ より $0 \lt q - 1$ となるため、除算可能。
2番目の方程式では $0 \lt q$ より除算可能。
4番目の方程式では $q \lt 0$ より除算可能。
5番目の方程式では $q \lt -1$ より $q + 1 \lt 0$ となるため、除算可能。

また $f$ の結果に対しては2をかける操作と1または2を足す操作しかしていないから、 $\mathbb{N}$ の範疇に収まる。

あとは、この方程式の解がちょうど1つあることを示せばよい。そのためには $f(q)$ の値が $q$ の何らかの順序にしたがって順番に決定されることを示せばよい。そのような指標としてここでは以下のようなものを考える。 $a \in \mathbb{Z}$ , $b \in \mathbb{N}^+$ , $\mathrm{gcd}(a, b) = 1$ に対し、 $|-|_f \colon \mathbb{Q} \to \mathbb{N}$ を

$\displaystyle |a/b|_f = |a| + |b|$

と定める。(有理数はこのような $a, b$ の組で一意に表せるので、ちゃんと定義される)

$f(q)$ の値が $|q|_f$ の小さいほうから順に定まるということを示したい。上記の方程式は $q$ に関する漏れや重複のない場合分けになっているので、各方程式をそれぞれ見ていけばよい。

1番目の方程式では $b \lt a$ として $f(a/b)$ を $f(b / (a - b))$ で表している。ここで $b$ と $a - b$ は互いに素のため、 $|b / (a - b)|_f = |b| + |a - b| \lt |b| + |a| = |a / b|_f$ となる。したがって既に定まっている値を使って $f(a/b)$ を表している。
2番目の方程式では $0 \lt a \le b$ として $f(a/b)$ を $f( (b - a) / a)$ で表している。ここで $b - a$ と $a$ は互いに素のため、 $|(b - a) / a|_f = |b - a| + |a| \lt |b| + |a| = |a / b|_f$ となる。したがって既に定まっている値を使って $f(a/b)$ を表している。
3番目の方程式はダイレクトに $f(a/b)$ を表しているので問題ない。
4番目の方程式では $-b \le a \lt 0$ として $f(a/b)$ を $f(-(b + a) / -a)$ で表している。ここで $-(b + a)$ と $-a$ は互いに素のため、 $|-(b + a) / -a|_f = |-(b + a)| + |-a| = |b + a| + |a| \lt |b| + |a| = |a / b|_f$ となる。したがって既に定まっている値を使って $f(a/b)$ を表している。
5番目の方程式では $a \lt -b$ として $f(a/b)$ を $f(-b / -(a + b))$ で表している。ここで $-b$ と $-(a + b)$ は互いに素のため、 $|-b / -(a + b)|_f = |-b| + |-(a + b)| = |b| + |a + b| \lt |b| + |a| = |a / b|_f$ となる。したがって既に定まっている値を使って $f(a/b)$ を表している。

■

定理1.4 $f$ は全単射である。

まずは前者(全射)を示す。全射を示すためには、 $n \in \mathbb{N}$ とおいて、 $f(q) = n$ となる $q \in \mathbb{Q}$ の存在を示せばよい。これを $n$ に関する数学的帰納法 (累積帰納法) によって示す。

$n = 0$ のとき、 $q = 0$ とおけばよい。

$n > 0$ のときはさらに $n$ の偶奇で場合分けする。 $n$ が奇数のとき、 $m \in \mathbb{N}$ を用いて $n = 2m + 1$ と表記できる。 $m \lt n$ なので数学的帰納法の仮定より $f(r) = m$ となる $r \in \mathbb{Q}$ が存在する。

さらに $r$ の符号で場合分けする。 $r \ge 0$ のとき、 $q = 1 / (r + 1)$ とおく。すると $0 \lt q \le 1$ より $f(q) = 2f(1 / q - 1) + 1 = 2f(r) + 1 = 2m + 1 = n$ となる。 $r \lt 0$ のときは、 $q = 1 / r - 1$ とおく。すると $q \lt -1$ より $f(q) = 2f(1 / (q + 1)) + 1 = 2f(r) + 1 = 2m + 1 = n$ となる。

$n$ が(正の)偶数のとき、 $m \in \in \mathbb{N}$ を用いて $n = 2m + 2$ と表記できる。 $m \lt n$ なので数学的帰納法の仮定より $f(r) = m$ となる $r \in \mathbb{Q}$ が存在する。

こちらも $r$ の符号で場合分けする。 $r > 0$ のとき、 $q = 1 / r + 1$ とおく。すると $1 \lt q$ より $f(q) = 2f(1 / (q - 1)) + 2 = 2f(r) + 2 = 2m + 2 = n$ となる。 $r \le 0$ のときは、 $q = 1 / (r - 1)$ とおく。すると $-1 \le q \lt 0$ より $f(q) = 2f(1 / q + 1) + 2 = 2f(r) + 2 = 2m + 2 = n$ となる。

以上により $f$ は全射であることが示された。

続いて単射を示す。単射を示すためには、 $q, q' \in \mathbb{Q}$ とおいて $f(q) = f(q')$ なら $q = q'$ を示せばよい。これを $f(q)$ に関する数学的帰納法(累積帰納法)によって示す。

$f(q) = f(q') = 0$ のとき $q = q' = 0$ である。これは1番目、2番目、4番目、5番目の方程式が当てはまらないことからわかる。

$f(q) = f(q') > 0$ の場合、さらに偶奇で場合分けする。 $f(q) = f(q')$ が奇数のとき、1,3,4番目の方程式は当てはまらないので、 $q \lt -1$ または $0 \lt q \le 1$ である。 $q'$ についても同様に $q' \lt -1$ または $0 \lt q' \le 1$ である。ここで $q \lt -1$ なら $r = 1 / (q + 1)$ 、 $0 \lt q \le 1$ なら $r = 1 / q - 1$ と定義する。また同様に $r'$ も定義する。すると $f(q) = 2f(r) + 1$ , $f(q') = 2f(r') + 1$ となる。特に $f(r) = f(r') \lt f(q)$ なので、数学的帰納法の仮定より $r = r'$ がわかる。ここで、 $r = r' \ge 0$ なら $q = 1 / (r + 1) = 1 / (r' + 1) = q'$ となり、 $r = r' \lt 0$ なら $q = 1 / r - 1 = 1 / r' - 1 = q'$ となる。

同様に、 $f(q) = f(q')$ が(正の)偶数のとき、2,3,5番目の方程式は当てはまらないので、 $-1 \le q \lt 0$ または $1 \lt q$ である。 $q'$ についても同様に $-1 \le q' \lt 0$ または $1 \lt q'$ である。ここで $-1 \le q \lt 0$ なら $r = 1 / q + 1$ 、 $1 \lt q$ なら $r = 1 / (q - 1)$ と定義する。また同様に $r'$ も定義する。すると $f(q) = 2f(r) + 2$ , $f(q') = 2f(r') + 2$ となる。特に $f(r) = f(r') \lt f(q)$ なので、数学的帰納法の仮定より $r = r'$ がわかる。ここで、 $r = r' > 0$ なら $q = 1 / r + 1 = 1 / r' + 1 = q'$ となり、 $r = r' \le 0$ なら $q = 1 / (r - 1) = 1 / (r' - 1) = q'$ となる。

以上により $f$ が単射であることが示された。

■

原理

有理数に付番する場合、約分できる分数に番号を与えないようなトリックが必要です。これは通常、約分できる分数を見つけるたびにスキップするような方法で対処しますが、この定義ではユークリッドの互除法の手順をそのままエンコードすることで、はじめから互いに素なペアだけを発見するような仕組みになっています。

まずは正の整数2つのユークリッドの互除法をエンコードすることを考えます。たとえば33と57の互除法は以下のようになります。