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

自然数全体を $\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$ のうち最小のものを求めよ。

自然数全体を $\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$ を含む）とする。カントールの対関数 $\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)$ の値を求めよ。

$\omega$ を最小の無限順序数とし、順序数の和・積・べきは通常の（超限帰納法による）順序数演算とする。積 $\alpha \cdot \beta$ は「$\alpha$ を $\beta$ 回並べたもの」を表す流儀（たとえば $\omega \cdot 2=\omega +\omega$, $2\cdot \omega =\omega$）とする。順序数
$$\delta =(\omega \cdot 2+1{)}^3+({\omega }^2\cdot 3+\omega \cdot 5+2)\cdot (\omega \cdot 2+4)$$
をカントール標準形で
$$\delta ={\omega }^3\cdot c_3+{\omega }^2\cdot c_2+\omega \cdot c_1+c_0(c_0,c_1,c_2,c_3\text{は自然数})$$
と表したとき、組 $(c_3,c_2,c_1,c_0)$ をこの順に求めよ。

命題変数 $x_1,x_2,\dots ,x_6$ だけを用いた命題論理の論理式を考える（結合子は $\neg ,\wedge ,\vee ,\to$ を用いる）。2 つの論理式は、$x_1,\dots ,x_6$ へのすべての真理値割り当てで同じ真理値をとるとき同値であるという。次の 2 つの論理式を定める。
$$\phi =\underset{i=1}{\overset{5}{\bigwedge }}\left(x_i\vee x_{i+1}\right),\chi =\underset{i=1}{\overset{4}{\bigwedge }}\left(x_i\vee x_{i+1}\vee x_{i+2}\right).$$
$x_1,\dots ,x_6$ だけを用いた論理式 $\psi$ であって、$\phi \to \psi$ と $\psi \to \chi$ がともにトートロジー（恒真式）であるものを考える。このような $\psi$ の、同値関係による同値類の個数を求めよ。