算術的階層が潰れないことの証明
参考
$ 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
この$ E^{\Sigma_n}_kは、$ k変数$ \Sigma_nの万能述語 これが本当に、$ \Sigma_n述語であることを示せばいい
どういうことか
①の右辺の万能述語部分$ E^{\Sigma_n}_kだけを見ると、下の算術的階層の図の紫の部分のどこかに入る しかし、$ E^{\Sigma_n}_k(x_k,\vec{x})では、赤の部分に入りますよ、という主張
https://gyazo.com/a4c6a670e1d177f3445dac3b21e944ea
青の部分に入るということは、$ \Sigma_nでも$ \Pi_nでもあるということ
赤の部分に入るということは、$ \Sigma_nであり、$ \Pi_nではないということ
ということで、「青の部分に入る」、つまり「$ \Pi_nである」と仮定して矛盾を導けばいい
この$ Uが$ \Pi_nであると仮定する
すると$ \lnot Uは、$ \Sigma_n述語になる
$ \lnot Uが$ \Sigma_n述語であるということは、それを表現する$ \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が目的の関数になっているmrsekut.icon
この$ Wは、$ \Sigma_{n+1}かつ$ \Pi_{n+1}である
この時点では下図の紫の中のどこかmrsekut.icon
かつ$ \Sigma_nでも$ \Pi_nでもない
つまり、下図の赤の箇所に位置する
https://gyazo.com/1a822cb3422bb1ee72b2dc09b94ac5f4
なぜなら
$ 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ではない
つまり水色の部分に入らない