万能述語の存在の証明
参考
準備
任意の自然数$ kについて、以下の定理が成り立つ
①-1
以下の条件を満たす$ k+2変数原始帰納述語$ \mathrm{Sigma}_kが存在する $ k変数の任意の帰納的述語$ Aに対して自然数$ pが存在して, $ Aは $ A(\vec{x})\Leftrightarrow (\exist t\in\mathbb{N})\mathrm{Sigma}_k(p,\vec{x},t)と表せる
証明
以下のように取ればいい
$ \mathrm{Sigma}_k(p,\vec{x},t)\iff \left(\mathrm{Trace}_k(p,\vec{x},t)\land \mathrm{output}(t)=1\right)
①-2
以下の条件を満たす$ k+2変数 原始帰納述語$ \mathrm{Pi}_kが存在する $ k変数の任意の帰納的述語$ Aに対して自然数$ pが存在して, $ Aは $ A(\vec{x})\Leftrightarrow (\forall t\in\mathbb{N})\mathrm{Pi}_k(p,\vec{x},t)と表せる
証明
以下のように取ればいい
$ \mathrm{Pi}_k(p,\vec{x},t)\iff\left(\mathrm{Trace}_k(p,\vec{x},t)\Rightarrow \mathrm{output}(t)=1\right)
以下の定理を示す
$ nを1以上の任意の自然数、$ kを任意の自然数としたとき以下の2つが成り立つ
②-1
$ (k+1)変数の$ \Sigma_n述語$ E^{\Sigma_n}_{k}が存在して以下が成り立つ
$ k変数の任意の$ \Sigma_n述語$ Aに対して
自然数$ pが存在し、
$ Aは、$ A(\vec{x})\iff E^{\Sigma_n}_{k}(p,\vec{x})と表せる
この$ E^{\Sigma_n}_{k}のことを「$ k変数用の$ \Sigma_n万能述語」と言う
②-2
$ (k+1)変数の$ \Pi_n述語$ E^{\Pi_n}_{k}が存在して、以下が成り立つ
$ k変数の任意の$ \Pi_n述語$ Aに対して
自然数$ pが存在し、
$ Aは、$ A(\vec{x})\iff E^{\Pi_n}_{k}(p,\vec{x})と表せる
この$ E^{\Pi_n}_{k}のことを「$ k変数用の$ \Pi_n万能述語」と言う
②-1の$ nが偶数の場合の証明
まず、定理①-2を用いることで、
任意の計算可能述語$ Bを、以下のように表せるような$ \mathrm{Pi}が存在する
③$ B(\vec{x},\vec{y})\iff (\forall t)\mathrm{Pi}(p,\vec{x},\vec{y},t)
ちゃんと書くと、
任意の$ k+n変数の任意の計算可能述語$ Bに対して、
$ pが存在して、
上のように表せる
定理Aの①との対応を図で書くと
https://gyazo.com/cd926e13ac5cb9bbf02992e4c0ef382a
このような$ \mathrm{Pi}を使うことで、$ E^{\Sigma_n}_kを定義できる
④$ E^{\Sigma_n}_k:=\left(\exists y_{1}\right)\left(\forall y_{2}\right)\left(\exists y_{3}\right)\left(\forall y_{4}\right) \cdots\left(\exists y_{n-1}\right)(\forall z) \operatorname{Pi}\left(p, \vec{x}, \vec{y}^{\prime}, \operatorname{left}(z), \operatorname{right}(z)\right)
これが目的の万能述語ねmrsekut.icon
右辺の引数の個数の対応は下図の通り
https://gyazo.com/a12bb02b8564e1a92f318931f2742208
これは定義なので、
$ \mathrm{Pi}を使ってこんなふうに定義することで、
$ E^{\Sigma_n}_kができました
と言っているに過ぎない
では、なぜこの$ E^{\Sigma_n}_kが「万能述語の力を持っている」と言えるのか
それを確認する
$ k変数の任意の$ \Sigma_n述語$ A(\vec{x})が、
$ E^{\Sigma_n}_k(p,\vec{x})で書けること
を確認すればいい
そのために、上の③④を使う
$ k変数の任意の$ \Sigma_n述語$ A(\vec{x})は、Σn述語の定義より $ A(\vec{x}) \quad \Longleftrightarrow \quad\left(\exists y_{1}\right)\left(\forall y_{2}\right) \cdots\left(\exists y_{n-1}\right)\left(\forall y_{n}\right) \underline{B'(\vec{x}, \vec{y})}
となる$ k+n変数計算可能述語$ B'が存在する
この下線部に③を適用することで
$ A(\vec{x}) \Longleftrightarrow\left(\exists y_{1}\right)\left(\forall y_{2}\right) \cdots\left(\exists y_{n-1}\right)\left(\forall y_{n}\right)\underline{(\forall t) \operatorname{Pi}(p, \vec{x}, \vec{y}, t)}
となり、この右辺は④の右辺と同じなので
④の$ \forall zを$ \forall y_nに置き換えているmrsekut.icon
$ \forallの連続は、一つの$ \forallと見ることができるので、$ \Sigma_nであることに変わりはない
$ A(\vec{x})\Longleftrightarrow E^{\Sigma_n}_k(p,\vec{x})
よって、任意の$ \Sigma_n述語は、$ E^{\Sigma_n}_kで表現できることがわかった
その他の場合の証明
①-1を使う
$ nが奇数のときの②-1
$ nが偶数のときの②-2
①-2を使う
$ nが偶数のときの②-1
上で示したもの
$ nが奇数のときの②-2