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

単射性. 素因数分解の一意性から、$┌0┐=1$、$┌St┐$ は $2$ のべき（$\ge 2$）、$┌(s+t)┐$ は $3^a{5}^b$ $(a,b\ge 1)$ の形で、この 3 種類は互いに重ならない。さらに $2^{┌t┐}$ から $┌t┐$ が、$3^{┌s┐}{5}^{┌t┐}$ から $┌s┐,┌t┐$ が復元できるので、帰納法により異なる項は異なるゲーデル数をもつ。したがって、ゲーデル数が $1000$ 以下の項を漏れなく列挙すればよい。

また、どの項についても $┌t┐\ge 1$ である。

$S$ で始まる項. $┌St┐=2^{┌t┐}\le 1000$ となるのは $┌t┐\le 9$（$2^9=512,2^{10}=1024$）のとき。

$+$ の項. $┌(s+t)┐=3^a{5}^b\le 1000$（$a=┌s┐,b=┌t┐$）とすると、$b\ge 1$ より $3^a\le 200$ なので $a\le 4$、$a\ge 1$ より $5^b\le 333$ なので $b\le 3$。

よって、まずゲーデル数が $9$ 以下の項を求めれば十分である。$+$ の項のゲーデル数は $3\cdot 5=15$ 以上なので、$9$ 以下の項は $0$ と $S$ の繰り返しだけからなる：
$$┌0┐=1,┌S0┐=2,┌SS0┐=4,┌SSS0┐=16>9.$$
したがってゲーデル数が $9$ 以下の項は $0,S0,SS0$（ゲーデル数 $1,2,4$）の 3 個。

$1000$ 以下の項の列挙.

$(1)$ $0$：$1$。

$(2)$ $St$（$┌t┐\le 9$）：$t=0,S0,SS0$ に対し $2^1=2,2^2=4,2^4=16$。3 個。

$(3)$ $(s+t)$（$┌s┐\le 4,┌t┐\le 3$）：$┌s┐\in \{1,2,4\}$, $┌t┐\in \{1,2\}$ の組で
$$3^1{5}^1=15,3^1{5}^2=75,3^2{5}^1=45,3^2{5}^2=225,3^4{5}^1=405,3^4{5}^2=2025.$$
このうち $1000$ 以下は $15,75,45,225,405$ の 5 個（項は $(0+0),(0+S0),(S0+0),(S0+S0),(SS0+0)$）。

以上より、求める個数は
$$1+3+5=9$$
である。

ゲーデル数の集合を $G$ とする。$1\in G$、$n\in G\Rightarrow 2^n\in G$、$a,b\in G\Rightarrow 3^a{5}^b\in G$。素因数分解の一意性より、$1$、$2$ の冪、$3$ と $5$ の両方で割れる数は互いに排他的で、ゲーデル数から項が一意に復元できる。よって「ゲーデル数が $1000$ 以下の項の個数」は $G$ の $1000$ 以下の元の個数に等しい。

(i) $0$ の項: ゲーデル数 $1$。

(ii) $St$ の形: $2^n\le 1000$ より $n\le 9$。$G$ の $9$ 以下の元を求める。$n=1$ は $G$ の元。$3$ は $2$ の冪でも $1$ でも $3^a{5}^b$ ($a,b\ge 1$) でもないので $G$ に入らない。$3^a{5}^b$ の最小は $15$ なので、$9$ 以下の $G$ の元は $1,2,4$（$2=2^1,4=2^2$）。$5,6,7,8,9$ は $G$ の元でない（$8=2^3$ は $3\notin G$、他は形に合わない）。よって $2^1=2,2^2=4,2^4=16$ の 3 個。

(iii) $(s+t)$ の形: $3^a{5}^b\le 1000$ で $a,b\in G$。$3^a\cdot 5\le 1000$ より $a\le 4$、$3\cdot 5^b\le 1000$ より $b\le 4$。$G$ の $4$ 以下の元は $1,2,4$。組 $(a,b)$ について:
- $(1,1):15,(1,2):75,(1,4):3\cdot 625=1875>1000$
- $(2,1):45,(2,2):225,(2,4):9\cdot 625>1000$
- $(4,1):81\cdot 5=405,(4,2):81\cdot 25=2025>1000,(4,4)$ は大

$1000$ 以下は $15,75,45,225,405$ の 5 個。

合計 $1+3+5=9$。元は $1,2,4,16,15,45,75,225,405$。