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

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

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

自然数全体を $\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とし、$p_i$ を $i$ 番目の素数とする（$p_0=2,p_1=3,p_2=5,\dots$）。有限列 $(a_0,a_1,\dots ,a_{k-1})\in {\mathbb{N}}^k$ のゲーデル数を
$$⟨a_0,a_1,\dots ,a_{k-1}⟩=\prod _{i=0}^{k-1}{p}_i^{a_i+1}$$
で定める（空列のゲーデル数は $1$ とする）。

関数 $F:\mathbb{N}\to \mathbb{N}$ を
$$F(0)=1,F(1)=1,F(n+2)=F(n+1)+2F(n)(n\in \mathbb{N})$$
で定め、その累積値関数（course-of-values function）$\overline{F}:\mathbb{N}\to \mathbb{N}$ を
$$\overline{F}(n)=⟨F(0),F(1),\dots ,F(n-1)⟩$$
で定める。自然数 $\overline{F}(5)$ の正の約数の個数を求めよ。

自然数全体を $\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とする。$\mathrm{rm}(x,y)$ を「$x$ を $y$ で割った余り」（$y\ge 1$）とし、ゲーデルの $\beta$ 関数を $$\beta (c,d,i)=\mathrm{rm}(c,1+(i+1)d)(c,d,i\in \mathbb{N})$$ で定める（$\beta$ は原始再帰関数である）。有限列 $(a_0,a_1,a_2)=(2,0,3)$ を、$s=\max \{3,a_0,a_1,a_2\}$ として $d=s!$ を用いて符号化する。すなわち $$\beta (c,d,0)=2,\beta (c,d,1)=0,\beta (c,d,2)=3$$ を満たす $c\in \mathbb{N}$ を考える。このような $c$ のうち最小のものを求めよ。

1 項関数記号 $f$ と 1 項関係記号 $P$ からなる一階の言語（等号を含む）を考える。台集合を $A=\{1,2,3,4,5,6\}$ に固定し、関数 $f^{\mathcal{M}}:A\to A$ と部分集合 $P^{\mathcal{M}}\subseteq A$ の組を 1 つ定めるごとに構造 $\mathcal{M}=(A,f^{\mathcal{M}},P^{\mathcal{M}})$ が 1 つ定まるとする。次の 2 つの文
$${\phi }_1:\forall x(f(f(x))=x),{\phi }_2:\forall x(P(x)\to \neg P(f(x)))$$
をともにみたす構造 $\mathcal{M}$（すなわち $\mathcal{M}\models {\phi }_1\wedge {\phi }_2$ となる組 $(f^{\mathcal{M}},P^{\mathcal{M}})$）の個数を求めよ。ただし、同型な構造であっても $(f^{\mathcal{M}},P^{\mathcal{M}})$ が異なれば別のものとして数える。

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

長さ $k\ge 0$ の有限列 $(a_0,a_1,\dots ,a_{k-1})\in {\mathbb{N}}^k$ のゲーデル数を
$$┌a_0,\dots ,a_{k-1}┐=\prod _{i<k}{p}_i^{a_i+1}$$
と定める（空列のゲーデル数は $1$）。関数 $F:\mathbb{N}\to \mathbb{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\dot{-}y$（$x\ge y$ なら $x-y$、そうでなければ $0$）、$x\mapsto p_x$、$(n,i)\mapsto (n{)}_i$ は原始再帰関数であり、述語 $x\mid y$ と $x<y$ は原始再帰的である。
- 原始再帰関数・原始再帰的述語の全体は、合成、原始再帰、論理結合子 $\neg ,\wedge ,\vee ,\to$、有界量化 $\forall i<m$, $\exists i<m$（$m$ は原始再帰関数の値）で閉じている。また、述語 $P$ が原始再帰的であることは、その特性関数 ${\chi }_P$（$P$ が成り立てば $1$、そうでなければ $0$）が原始再帰関数であることと定義する。
- 素因数分解の一意性。