算術的階層が潰れないことの証明
参考
『C言語による計算の理論』 pp.123-124
算術的階層は全て埋まるという定理を再掲
n,kを1以上の任意の自然数としたとき以下が成り立つ
(1)\Sigma_{n}であって\Pi_{n}ではないk変数述語が存在する
(2)\Pi_{n}であって、\Sigma_{n}ではないk変数述語が存在する
(3)\Sigma_{n+1}かつ\Pi_{n+1}であるが、\Sigma_{n}でも\Pi_{n}でもないk変数述語が存在する
(1)の証明
\Sigma_{n}述語であって\Pi_{n}述語ではないような、k変数述語の例を一つ挙げればいい
①U(\vec{x})\iff E^{\Sigma_n}_k(x_k, \vec{x})
これがその例の一つになる
\vec{x}は、x_1,\cdots,x_k
これが本当に、\Sigma_n述語であることを示せばいい
どういうことか
①の右辺の万能述語部分 E^{\Sigma_n}_kだけを見ると、下の算術的階層の図の紫の部分のどこかに入る
しかし、 E^{\Sigma_n}_k(x_k,\vec{x})では、赤の部分に入りますよ、という主張
青の部分に入るということは、\Sigma_nでも\Pi_nでもあるということ
赤の部分に入るということは、\Sigma_nであり、\Pi_nではないということ
ということで、「青の部分に入る」、つまり「\Pi_nである」と仮定して矛盾を導けばいい
このUが\Pi_nであると仮定する
すると\lnot Uは、\Sigma_n述語になる
②つまり、\lnot U(\vec{x})\iff E^{\Sigma_n}_k(p,\vec{x})となるような自然数pが存在する
よって、
U(x_1,x_2,\cdots,x_{k-1},p)\iff E^{\Sigma_n}_k(p, x_1,\cdots,x_{k-1}, p)
∵①にx_1,x_2,\cdots,x_{k-1},pを代入
\iff \lnot U(x_1,x_2,\cdots,x_{k-1},p) ∵②
故にU=\lnot Uとなり、矛盾
よって、Uは\Sigma_n万能述語であって、\Pi_n述語ではないような、k変数述語である
赤に入る
(2)の証明
V(\vec{x})\iff E^{\Pi_n}_kとすれば、(1)と同じやり方で示せる
このVが、\Pi_nであり\Sigma_nではないk変数述語になっている
(3)の証明
(1)のUと、(2)のVを使ってWを以下のように定義する
W(\vec{x})\iff \left((x_kは偶数)\land U(\vec{x'},\frac{x_k}{2})\right)\lor \left((x_kは奇数)\land V(\vec{x'},\frac{x_k-1}{2})\right)
\vec{x'}は、x_1,\cdots,x_{k-1}
Uは\Sigma_n述語
Vは\Pi_n述語
このWが目的の関数になっている
このWは、\Sigma_{n+1}かつ\Pi_{n+1}である
この時点では下図の紫の中のどこか
かつ\Sigma_nでも\Pi_nでもない
つまり、下図の赤の箇所に位置する
なぜなら
Wの定義より以下の2式が成り立つ
U(\vec{x})\iff W(\vec{x'}, 2x_k)
V(\vec{x})\iff W(\vec{x'}, 2x_k+1)
もし、Wが\Sigma_nだとすると、
つまり上図の緑の部分
Vも\Sigma_nになって(2)に反する
なのでWは\Sigma_nではない
つまり緑の部分に入らない
もし、Wが\Pi_nだとすると、
つまり上図の水色の部分
Wも\Pi_nとなって(1)に反する
なのでWは\Pi_nではない
つまり水色の部分に入らない