カントールの対関数とその逆

カントールの対関数 $J (x, y) = \frac{( x + y ) ( x + y + 1 )}{2} + y$ の値を計算でき、 $n$ から $\frac{s ( s + 1 )}{2} \leq n$ となる最大の $s$ を求めて逆写像 $K (n), L (n)$ （ $J (K (n), L (n)) = n$ ）を求められる（例: $J (2, 3) = 18$ , $K (18) = 2$ , $L (18) = 3$ ）

前提

可算集合（大学数学集合と位相）

この技能までの道筋（7 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
写像・単射の個数と集合の濃度（大学数学集合と位相）
可算集合（大学数学集合と位相）

説明

0 以上の整数の組 $(x, y)$ に 0 以上の整数 1 つを重なりなく、もれなく割り当てる具体的な全単射が、カントールの対関数 $J (x, y) = \frac{( x + y ) ( x + y + 1 )}{2} + y$ です。ここでは $N = {0, 1, 2, \dots}$ （0 を含む）とします。 $J$ の値を計算することと、逆に番号 $n$ からもとの組 $(K (n), L (n))$ を取り出すことができるようになります。 $N \times N$ が可算であることを具体的な式で示したり、計算理論で 2 つの数を 1 つの数にまとめたりする場面で使います。

なぜそうしてよいのか

格子点 $(x, y)$ （ $x, y \in N$ ）を、 $x + y = s$ の斜めの線（第 $s$ 対角線）ごとにまとめます。第 $s$ 対角線には $(s, 0), (s - 1, 1), \dots, (0, s)$ の $s + 1$ 個の点があります。対角線を $s = 0, 1, 2, \dots$ の順に、各対角線の中では $y = 0, 1, \dots, s$ の順にたどって $0, 1, 2, \dots$ と番号を振ります。どの点もいつかちょうど 1 回たどられるので、これは $N \times N$ から $N$ への全単射です。

点 $(x, y)$ の番号を数えましょう。それより前の対角線（第 $0$ 〜第 $s - 1$ ）にある点は $1 + 2 + \dots + s = \frac{s ( s + 1 )}{2}$ 個、同じ対角線の中で前にある点は $y$ 個です。よって番号は $\frac{s ( s + 1 )}{2} + y$ （ $s = x + y$ ）で、これが $J (x, y)$ です。 $T (s) = \frac{s ( s + 1 )}{2}$ （三角数）と書くと、第 $s$ 対角線の番号は $T (s), T (s) + 1, \dots, T (s) + s$ で、次の対角線は $T (s) + s + 1 = T (s + 1)$ から始まります。

このことから逆写像が得られます。番号 $n$ が第 $s$ 対角線にあるのは $T (s) \leq n < T (s + 1)$ のとき、つまり $s$ が「 $T (s) \leq n$ をみたす最大の $s$ 」のときです。 $s$ がわかれば $y = n - T (s)$ （このとき $0 \leq y \leq s$ ）、 $x = s - y$ と決まり、これを $K (n) = x$ 、 $L (n) = y$ と書きます。

手順

順方向： $s = x + y$ を計算し、 $J (x, y) = \frac{s ( s + 1 )}{2} + y$ に代入する
逆方向：三角数 $T (s) = \frac{s ( s + 1 )}{2}$ を $s = 0, 1, 2, \dots$ と並べ（ $0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, \dots$ ）、 $T (s) \leq n$ をみたす最大の $s$ を見つける（ $T (s) \leq n < T (s + 1)$ ）
$L (n) = y = n - T (s)$ を求める（ $0 \leq y \leq s$ になっていることを確かめる）
$K (n) = x = s - y$ を求め、 $J (x, y) = n$ となることを代入して検算する

例題

$N = {0, 1, 2, \dots}$ とし、 $J : N \times N \to N$ を $J (x, y) = \frac{( x + y ) ( x + y + 1 )}{2} + y$ で定める。 $J (x, y) = 50$ となる $(x, y)$ を求めよ。

例題の解答

手順 2：三角数を並べると $T (9) = \frac{9 \cdot 10}{2} = 45$ 、 $T (10) = \frac{10 \cdot 11}{2} = 55$ で、 $45 \leq 50 < 55$ 。よって $T (s) \leq 50$ をみたす最大の $s$ は $s = 9$ 。

手順 3： $y = 50 - T (9) = 50 - 45 = 5$ 。 $0 \leq 5 \leq 9$ をみたす。

手順 4： $x = s - y = 9 - 5 = 4$ 。検算すると $J (4, 5) = \frac{9 \cdot 10}{2} + 5 = 45 + 5 = 50$ で正しい。

よって $(x, y) = (4, 5)$ 。

答え: $(4, 5)$

よくある誤り

$s$ を $T (s) \geq n$ となる最小の $s$ としてしまう誤り（ $n = 50$ で $T (10) = 55$ から $s = 10$ とし、 $y = 50 - 55 = - 5$ と負になるなど）。正しくは $T (s) \leq n$ となる最大の $s$ で、 $s = 9$ 、 $y = 5$
$x$ と $y$ の役割を取り違え、 $x = n - T (s)$ 、 $y = s - x$ としてしまう誤り（ $n = 18$ で $(3, 2)$ とするなど）。正しくは $J$ の式で足しているのは $y$ なので $L (n) = y = n - T (s)$ 、 $K (18) = 2$ 、 $L (18) = 3$
三角数を $\frac{s ( s - 1 )}{2}$ や $\frac{( x + y ) ^{2}}{2}$ で計算してしまう誤り（ $J (2, 3) = \frac{5 \cdot 4}{2} + 3 = 13$ など）。正しくは $J (2, 3) = \frac{5 \cdot 6}{2} + 3 = 18$
$N$ が 1 から始まるとして番号を 1 ずらしてしまう誤り（ $J (0, 0) = 1$ とするなど）。この定義では $N$ は 0 を含み $J (0, 0) = 0$

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
$0$ 以上の整数全体を $N = {0, 1, 2, \dots}$ とし、カントールの対関数 $J : N \times N \to N$ を
$J (x, y) = \frac{( x + y ) ( x + y + 1 )}{2} + y$
で定める。 $J$ は全単射である。 $J (x, y) = 33$ を満たす $(x, y) \in N \times N$ を求め、組 $(x, y)$ で答えよ。

この技能を使う問題

この技能の次に学べること

累積再帰（大学院数学数理論理学・集合論）