ゲーデル数とは
表現可能性にはゲーデル数が必要なので、ゲーデル数について考えてみる。
前原昭二の本はとても参考になる。
https://amzn.to/4dMR6Ru
式は記号の列で表せる。各記号にゲーデル数という数を割り当てると、式を自然数で表すことができる。
例えば、論理学の式に出てくる記号をゲーデル数で定義してみよう。
記号にゲーデル数を対応させる
| 0 |
' |
\in |
\neg |
\rightarrow |
\forall |
( |
) |
| 1 |
3 |
5 |
7 |
9 |
11 |
13 |
15 |
変数
変数は
\begin{array}{llll}
1\text{階の変数}&x_1,& y_1,& z_1,& \dots\\
2\text{階の変数}&x_2,& y_2,& z_2,& \dots\\
3\text{階の変数}&x_3,& y_3,& z_3,& \dots\\
\end{array}
は15より大きい素数をゲーデル数として対応させる。
\begin{array}{lll}
17,& 19,& 23& \dots\\
17^2,& 19^2,& 23^2& \dots\\
17^3,& 19^3,& 23^3& \dots\\
\end{array}
有限列のゲーデル数
記号X_1,X_2,\dots X_\nuからなる有限列
S:\quad X_1 X_2\cdots X_i \cdots X_\nu
を考える。各記号の
X_iのゲーデル数が
n_i であるとき、素因数分解を使って、
n=2^{n_1}\cdot 3^{n_2}\cdot 5^{n_3}\cdot\cdots\cdot p_i^{n_i}\cdot\cdots\cdot p_\nu^{n_\nu}
として定まる自然数
nを列
Sのゲーデル数とする。ここで
p_iは
i番目の素数を表す。
記号の有限列の有限列
記号の有限列の有限列も同様で、ゲーデル数n_iを持つ記号の有限列S_iからなる有限列
のゲーデル数は
n=2^{n_1}\cdot 3^{n_2}\cdot 5^{n_3}\cdot\cdots\cdot p_\nu^{n_\nu}
として定まる自然数
nであるとする。
ゲーデル数が再帰的に定義可能なのはとてもミステリアスですね。
例
式 2 を 0\ '\ ' と表すと、各記号のゲーデル数は 1,3,3となるので、
記号列 0\ '\ ' のゲーデル数
2^1\cdot 3^3\cdot 5^3=6750
式 0 のゲーデル数は
となる。
ゲーデル数を表す記号
記号列 S のゲーデル数を \sharp S と表す。
\sharp 2 = \sharp(0,',') = 2^1\cdot 3^3\cdot 5^3=6750, \quad \sharp 0=2^1=2
記号列の記号列 0,0'',0 はどうなるであろうか。各記号列のゲーデル数はそれぞれ 2,\ 6750,\ 2 なので、
\sharp(0,0'',0) = 2^2\cdot 3^{6750}\cdot 5^2
膨大な数になるので、掲載するのを省略する。
Discussion