算術的階層の各領域に万能述語が存在することの証明

万能述語#5fafd4ae19827000008c0471の定理の証明

参考

『C言語による計算の理論』 p.122

部分帰納的関数に関する以下の定理を用いる

任意の自然数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)

ref 万能述語#5fafd4ae19827000008c0473

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が存在して、

上のように表せる

\mathrm{Pi}はk+n+2変数原始帰納述語

定理Aの①との対応を図で書くと

このような\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)

これが目的の万能述語ね

右辺の引数の個数の対応は下図の通り

これは定義なので、

\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に置き換えている

\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