この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

数理論理学・集合論の問題

難易度 2大学院の講義の演習問題レベル大学院数学数理論理学・集合論

自然数全体を $N = {0, 1, 2, \dots}$ （ $0$ を含む）とする。カントールの対関数 $π : N \times N \to N$ を
$π (x, y) = \frac{( x + y ) ( x + y + 1 )}{2} + y$
で定める。 $π$ は全単射であるから、各 $n \in N$ に対して $π (x, y) = n$ をみたす $(x, y)$ がただ 1 つ存在する。これを $x = π_{1} (n)$ , $y = π_{2} (n)$ と書く（ $π_{1}, π_{2}$ は原始再帰関数である）。

関数 $g : N \to N$ を、累積再帰（course-of-values recursion）により
$g (0) = 0, g (n + 1) = π (g (π_{2} (n)), g (π_{1} (n))) + 1 (n \in N)$
で定める（ $π_{1} (n), π_{2} (n) \leq n$ なので well-defined であり、 $g$ は原始再帰関数である）。 $g (2024)$ の値を求めよ。

この問題で使うもの

累積再帰（説明と入口の問題）
カントールの対関数とその逆（説明と入口の問題）

この問題を解けるようになるまで（26 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

$g (n + 1)$ を求めるには、まず $n$ を $π_{1} (n), π_{2} (n)$ に分解し、それらの $g$ の値を再帰的に求める。 $0$ に達するまで分解を繰り返し、得られた値を下から組み立てる。

ヒント 2

$π (x, y) = n$ の逆算は、 $\frac{w ( w + 1 )}{2} \leq n$ をみたす最大の $w$ を取り、 $y = n - \frac{w ( w + 1 )}{2}$ , $x = w - y$ とする。番号を二分木と見なすと $g$ は左右を入れ替えた木の番号を与える。

ヒント 3

$2023 = π (56, 7)$ , $55 = π (10, 0)$ , $9 = π (0, 3)$ , $6 = π (3, 0)$ , $2 = π (0, 1)$ , $0 = π (0, 0)$ となる。これから $g (1) = 1$ , $g (3) = 2$ , $g (7) = 6$ , $g (10) = 4$ , $g (56) = 15$ が得られる。

答えと解説

答えを見る

247

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

考え方. 二分木（各内部節点がちょうど 2 つの子をもつ順序木）に次のゲーデル数をつける：葉 $∙$ の番号を $0$ 、左部分木 $L$ ・右部分木 $R$ をもつ木 $⟨ L, R ⟩$ の番号を $π (# L, # R) + 1$ とする。 $π$ が全単射なので、これは二分木全体と $N$ の全単射になる。番号 $m$ の木を $T_{m}$ と書くと、 $n + 1$ の木は $T_{n + 1} = ⟨ T_{π_{1} (n)}, T_{π_{2} (n)} ⟩$ である。 $g$ の定義は「左右を入れ替えたものを再帰的に作る」ことにあたり、 $g (m)$ は $T_{m}$ の鏡像の番号である。以下、実際に計算する。

逆関数の計算. $n$ に対し $\frac{w ( w + 1 )}{2} \leq n$ をみたす最大の $w$ をとり、 $y = n - \frac{w ( w + 1 )}{2}$ , $x = w - y$ とすれば $π_{1} (n) = x$ , $π_{2} (n) = y$ 。

$2024$ の分解（木 $T_{2024}$ の復元）.
- $2024 = 2023 + 1$ ： $\frac{63 \cdot 64}{2} = 2016 \leq 2023 < 2080 = \frac{64 \cdot 65}{2}$ より $w = 63$ , $y = 7$ , $x = 56$ 。よって $T_{2024} = ⟨ T_{56}, T_{7} ⟩$ 。
- $56 = 55 + 1$ ： $\frac{10 \cdot 11}{2} = 55$ より $w = 10$ , $y = 0$ , $x = 10$ 。 $T_{56} = ⟨ T_{10}, T_{0} ⟩$ 。
- $10 = 9 + 1$ ： $6 \leq 9 < 10$ より $w = 3$ , $y = 3$ , $x = 0$ 。 $T_{10} = ⟨ T_{0}, T_{3} ⟩$ 。
- $7 = 6 + 1$ ： $w = 3$ , $y = 0$ , $x = 3$ 。 $T_{7} = ⟨ T_{3}, T_{0} ⟩$ 。
- $3 = 2 + 1$ ： $1 \leq 2 < 3$ より $w = 1$ , $y = 1$ , $x = 0$ 。 $T_{3} = ⟨ T_{0}, T_{1} ⟩$ 。
- $1 = 0 + 1$ ： $π_{1} (0) = π_{2} (0) = 0$ 。 $T_{1} = ⟨ T_{0}, T_{0} ⟩$ 。

$g$ の計算（下から順に）.
- $g (0) = 0$ 。
- $g (1) = π (g (0), g (0)) + 1 = π (0, 0) + 1 = 1$ 。
- $g (3) = π (g (1), g (0)) + 1 = π (1, 0) + 1 = \frac{1 \cdot 2}{2} + 0 + 1 = 2$ 。
- $g (7) = π (g (0), g (3)) + 1 = π (0, 2) + 1 = \frac{2 \cdot 3}{2} + 2 + 1 = 6$ 。
- $g (10) = π (g (3), g (0)) + 1 = π (2, 0) + 1 = 3 + 0 + 1 = 4$ 。
- $g (56) = π (g (0), g (10)) + 1 = π (0, 4) + 1 = \frac{4 \cdot 5}{2} + 4 + 1 = 15$ 。
- $g (2024) = π (g (7), g (56)) + 1 = π (6, 15) + 1 = \frac{21 \cdot 22}{2} + 15 + 1 = 231 + 16 = 247$ 。

（検算： $247 = 246 + 1$ , $\frac{21 \cdot 22}{2} = 231 \leq 246 < 253$ より $π_{1} (246) = 6$ , $π_{2} (246) = 15$ となり、 $T_{247} = ⟨ T_{6}, T_{15} ⟩$ が $T_{2024} = ⟨ T_{56}, T_{7} ⟩$ の鏡像であることと整合する。）

よって $g (2024) = 247$ 。

別解

$π (x, y) = T (x + y) + y$ （ $T (s) = s (s + 1) /2$ ）。 $g (2024)$ は $n = 2023$ を用いて計算する。

$T (63) = 2016 \leq 2023 < T (64) = 2080$ より $s = 63$ , $y = 2023 - 2016 = 7$ , $x = 56$ 。よって $π_{1} (2023) = 56, π_{2} (2023) = 7$ で、
$g (2024) = π (g (7), g (56)) + 1$ 。

小さい値の計算（ $n$ と $(π_{1} (n), π_{2} (n))$ ）:
- $g (1) = π (g (0), g (0)) + 1 = π (0, 0) + 1 = 1$
- $g (2)$ : $n = 1$ , $(1, 0)$ より $π (g (0), g (1)) + 1 = π (0, 1) + 1 = 2 + 1 = 3$
- $g (3)$ : $n = 2$ , $(0, 1)$ より $π (g (1), g (0)) + 1 = π (1, 0) + 1 = 2$
- $g (4)$ : $n = 3$ , $(2, 0)$ より $π (g (0), g (2)) + 1 = π (0, 3) + 1 = 9 + 1 = 10$
- $g (7)$ : $n = 6$ , $(3, 0)$ より $π (g (0), g (3)) + 1 = π (0, 2) + 1 = 5 + 1 = 6$
- $g (10)$ : $n = 9$ , $(0, 3)$ より $π (g (3), g (0)) + 1 = π (2, 0) + 1 = 3 + 1 = 4$
- $g (56)$ : $n = 55 = T (10)$ , $(10, 0)$ より $π (g (0), g (10)) + 1 = π (0, 4) + 1 = (10 + 4) + 1 = 15$

したがって $g (2024) = π (6, 15) + 1 = T (21) + 15 + 1 = 231 + 16 = 247$ 。

検算: $π (6, 15) = 231 + 15 = 246$ 、 $+ 1 = 247$ 。

数理論理学・集合論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題