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

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

自然数は $0$ を含むものとし、 $N = {0, 1, 2, \dots}$ とする。 $p_{i}$ で $i$ 番目の素数を表す（ $p_{0} = 2, p_{1} = 3, p_{2} = 5, \dots$ ）。 $n \geq 1$ と $i \in N$ に対し、 $(n)_{i}$ を「 $p_{i}^{e} ∣ n$ となる最大の $e \in N$ 」と定め、 $(0)_{i} = 0$ とする。

長さ $k \geq 0$ の有限列 $(a_{0}, a_{1}, \dots, a_{k - 1}) \in N^{k}$ のゲーデル数を
$┌ a_{0}, \dots, a_{k - 1} ┐ = i < k \prod p_{i}^{a_{i} + 1}$
と定める（空列のゲーデル数は $1$ ）。関数 $F : N \to N$ を、 $n$ がある有限列 $(a_{0}, \dots, a_{k - 1})$ のゲーデル数であるとき $F (n) = \sum_{i < k} a_{i}$ 、そうでないとき $F (n) = 0$ と定める。

$F$ が原始再帰関数であることを証明せよ。

ただし、次の事実は用いてよい。
- $x + y$ , $x \cdot y$ , $x - ˙ y$ （ $x \geq y$ なら $x - y$ 、そうでなければ $0$ ）、 $x \mapsto p_{x}$ 、 $(n, i) \mapsto (n)_{i}$ は原始再帰関数であり、述語 $x ∣ y$ と $x < y$ は原始再帰的である。
- 原始再帰関数・原始再帰的述語の全体は、合成、原始再帰、論理結合子 $\neg, \land, \lor, \to$ 、有界量化 $\forall i < m$ , $\exists i < m$ （ $m$ は原始再帰関数の値）で閉じている。また、述語 $P$ が原始再帰的であることは、その特性関数 $χ_{P}$ （ $P$ が成り立てば $1$ 、そうでなければ $0$ ）が原始再帰関数であることと定義する。
- 素因数分解の一意性。

この問題で使うもの

原始再帰的定義と関数の値（説明と入口の問題）
素因数分解による列のゲーデル数（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

「 $n$ がゲーデル数である」という述語を原始再帰的に書き、その特性関数と、指数 $(n)_{i}$ から作った有界和の積として $F$ を表すことを目指しましょう。

ヒント 2

$n$ がゲーデル数であることは「 $n \geq 1$ かつ、 $n$ を割る素数の添字の集合が ${0, 1, \dots, k - 1}$ の形」と言い換えられます。量化の範囲を有界にするには $i < p_{i}$ を使います。和は $\sum_{i < n} ((n)_{i} - ˙ 1)$ を考えます。

ヒント 3

$p_{i} \geq i + 2$ を帰納法で示すと、 $p_{i} ∣ n$ なら $i < n$ になります。そこで $Seq (n) :\Leftrightarrow 1 \leq n \land \forall i < n \forall j < i (p_{i} ∣ n \to p_{j} ∣ n)$ とおき、これがゲーデル数であることと同値であることを両方向から確かめます。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

素因数分解の一意性から、ゲーデル数 $n$ に対して列の長さと各項が一意に決まり（ $a_{i} = (n)_{i} - 1$ ）、 $F$ が矛盾なく定義されていることを述べている（1 点）
$p_{i} \geq i + 2$ （したがって $p_{i} ∣ n, n \geq 1$ なら $i < n$ ）を帰納法などで示し、量化や和の範囲を $n$ で抑えられる根拠にしている（2 点）
「 $n$ がゲーデル数である」を有界量化だけを使う述語（例: $1 \leq n \land \forall i < n \forall j < i (p_{i} ∣ n \to p_{j} ∣ n)$ ）で表し、それが原始再帰的であることを閉包性から説明している（2 点）
その述語がゲーデル数であることと同値であることを両方向とも示している（特に、添字の集合が下に閉じた有限集合なので ${0, \dots, k - 1}$ になることを使っている）（2 点）
$\sum_{i < m} ((n)_{i} - ˙ 1)$ が原始再帰で定義できることを示し、 $F (n) = χ_{Seq} (n) \cdot \sum_{i < n} ((n)_{i} - ˙ 1)$ が全ての $n$ で成り立つことを、 $k \leq n$ と $i \geq k$ の項が $0$ になることから確かめている（2 点）
以上を合成で閉じていることにまとめ、 $F$ が原始再帰関数であると結論している（1 点）

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

模範解答を読む

方針. $n$ がゲーデル数であるという述語 $Seq (n)$ を原始再帰的に書き、 $F (n) = χ_{Seq} (n) \cdot \sum_{i < n} ((n)_{i} - ˙ 1)$ と表せることを示す。

補題 1（ $F$ が定義としてきちんと決まること）. $n = \prod_{i < k} p_{i}^{a_{i} + 1}$ のとき、素因数分解の一意性から、 $i < k$ なら $(n)_{i} = a_{i} + 1 \geq 1$ 、 $i \geq k$ なら $(n)_{i} = 0$ である。よって $k$ は「 $p_{i} ∣ n$ となる $i$ の個数」として、各 $a_{i}$ は $(n)_{i} - 1$ として $n$ から一意に決まる。したがって $F$ は矛盾なく定義されている。

補題 2. すべての $i \in N$ について $p_{i} \geq i + 2$ 、特に $i < p_{i}$ である。

$i$ についての帰納法で示す。 $i = 0$ のとき $p_{0} = 2 \geq 2$ 。 $p_{i} \geq i + 2$ を仮定すると、素数の列は狭義単調増加なので $p_{i + 1} \geq p_{i} + 1 \geq i + 3$ 。

この結果、 $n \geq 1$ で $p_{i} ∣ n$ ならば $i < p_{i} \leq n$ 、つまり $i < n$ である。

補題 3（ $Seq$ は原始再帰的）. 述語
$Seq (n) :⟺ 1 \leq n \land \forall i < n \forall j < i (p_{i} ∣ n \to p_{j} ∣ n)$
を考える。 $1 \leq n$ は $0 < n$ と同じで原始再帰的である。 $p_{i} ∣ n$ と $p_{j} ∣ n$ は原始再帰関数 $i \mapsto p_{i}$ を原始再帰的述語 $x ∣ y$ に合成したものなので原始再帰的である。これらに $\to, \land$ と有界量化 $\forall j < i$ , $\forall i < n$ を施したものも原始再帰的である。 $Seq (n)$ が「 $n$ がある有限列のゲーデル数である」と同値であることを示す。

( $\Rightarrow$ の向き：ゲーデル数なら $Seq$ が成り立つ) $n = \prod_{i < k} p_{i}^{a_{i} + 1}$ とする。 $n \geq 1$ である。 $p_{i} ∣ n$ なら補題 1 より $i < k$ なので、 $j < i$ なら $j < k$ となり $p_{j} ∣ n$ 。よって $Seq (n)$ が成り立つ。

( $\Leftarrow$ の向き： $Seq$ が成り立てばゲーデル数) $Seq (n)$ を仮定し、 $D = {i \in N : p_{i} ∣ n}$ とおく。補題 2 より $D \subset {0, 1, \dots, n - 1}$ なので $D$ は有限である。また $i \in D$ , $j < i$ なら $i < n$ なので、仮定から $p_{j} ∣ n$ 、すなわち $j \in D$ となる。よって $D$ は下に閉じた有限集合なので、 $k = ∣ D ∣$ とすると $D = {0, 1, \dots, k - 1}$ である。 $n \geq 1$ の素因数は $p_{i}$ ( $i \in D$ ) だけなので、素因数分解により
$n = i < k \prod p_{i}^{(n)_{i}}, (n)_{i} \geq 1 (i < k)$
となる。 $a_{i} = (n)_{i} - 1 \in N$ とおけば $n = ┌ a_{0}, \dots, a_{k - 1} ┐$ となり、 $n$ はゲーデル数である。

補題 4（有界和）. $h (n, i) = (n)_{i} - ˙ 1$ は原始再帰関数の合成なので原始再帰関数である。 $G (n, m) = \sum_{i < m} h (n, i)$ は
$G (n, 0) = 0, G (n, m + 1) = G (n, m) + h (n, m)$
という原始再帰で定義されるので原始再帰関数である。

$F$ の表示. すべての $n$ について
$F (n) = χ_{Seq} (n) \cdot G (n, n) (*)$
が成り立つことを示す。

・ $n$ がゲーデル数でないとき：補題 3 より $χ_{Seq} (n) = 0$ なので右辺は $0$ で、定義から $F (n) = 0$ に等しい。

・ $n = ┌ a_{0}, \dots, a_{k - 1} ┐$ のとき： $χ_{Seq} (n) = 1$ である。まず $k \leq n$ を確かめる。 $k = 0$ なら明らかで、 $k \geq 1$ なら $p_{k - 1} ∣ n$ だから補題 2 より $k - 1 < p_{k - 1} \leq n$ 、つまり $k \leq n$ 。次に補題 1 より、 $i < k$ では $h (n, i) = (a_{i} + 1) - ˙ 1 = a_{i}$ 、 $k \leq i < n$ では $(n)_{i} = 0$ なので $h (n, i) = 0 - ˙ 1 = 0$ 。したがって
$G (n, n) = i < k \sum a_{i} + k \leq i < n \sum 0 = i < k \sum a_{i} = F (n) .$

これで $(*)$ が示された。 $χ_{Seq}$ （補題 3）と $n \mapsto G (n, n)$ （補題 4 の $G$ に恒等関数を合成したもの）はともに原始再帰関数であり、積 $x \cdot y$ も原始再帰関数なので、合成で閉じていることから $F$ は原始再帰関数である。

以上により、 $F$ は原始再帰関数である。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる