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

$0$ 以上の整数全体を $\mathbb{N}=\{0,1,2,\dots \}$ とする。関数 $f:\mathbb{N}\to \mathbb{N}$ を、累積再帰
$$f(0)=1,f(n+1)=f(n)+f\left(\lfloor \frac{n}{2}\rfloor \right)(n\in \mathbb{N})$$
で定める。ここで $\lfloor t\rfloor$ は $t$ 以下の最大の整数である。$f(n)\ge 20$ となる最小の $n\in \mathbb{N}$ を求めよ。

自然数全体を $\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)$ の値を求めよ。

$p_0=2,p_1=3,p_2=5,p_3=7,\dots$ を小さい順に並べた素数とする。$0$ 以上の整数からなる長さ $k+1$ の有限列 $(a_0,a_1,\dots ,a_k)$（$k\geqq 0$）を
$$┌(a_0,a_1,\dots ,a_k)┐=\prod _{i=0}^k{p}_i^{a_i+1}$$
で正の整数に符号化する。符号が $1440600$ である列を求め、成分を順に並べた組で答えよ。

$\omega$ を最小の無限順序数とし、$+$ と $\cdot$ は順序数の和と積とする。順序数
$$\alpha =(\omega \cdot 2+3)\cdot (\omega +2)$$
のカントール標準形を
$$\alpha ={\omega }^2\cdot a+\omega \cdot b+c(a,b,c\text{ は }0\text{ 以上の整数})$$
と表すとき、組 $(a,b,c)$ をこの順に求めよ。

2 項関係記号 $E$ だけからなる言語の構造 $\mathcal{G}=(V,E^{\mathcal{G}})$ を、台集合 $V=\{1,2,3,4,5,6\}$、
$$E^{\mathcal{G}}=\{(a,b)\mid \{a,b\}\in \{\{1,2\},\{1,3\},\{1,4\},\{1,5\},\{5,6\}\}\}$$
で定める（$E^{\mathcal{G}}$ は対称で、5 本の辺をもつ無向グラフを表す）。$\mathcal{G}$ の自己同型、すなわち全単射 $\sigma :V\to V$ であって、すべての $a,b\in V$ について $E(a,b)⟺E(\sigma (a),\sigma (b))$ を満たすものの個数を求めよ。