算術的階層
Arithmetical hierarchy
Kleene hierarchy
前提
$ n: 1以上の自然数
$ k: 自然数
$ \vec{x},\vec{y}: 長さ$ kの数の列
それぞれ$ (x_1,\cdots,x_k)
定理: 述語$ Aに関する以下の2条件は同値
$ Aは、$ \Sigma_1でもあり、$ \Pi_1でもある
ちなみに、$ \Sigma_1のみを満たす場合は、半決定可能であるmrsekut.icon 証明
$ Aが1変数述語のときを考える
$ A=\Sigma_1であり、この補集合は$ \bar{A}=\bar{\Sigma_1}=\Pi_1である
$ \Sigma_1も$ \Pi_1も半決定可能なので、$ A,\bar{A}もまた半決定可能である
$ Aが2変数以上の述語のときも同様
算術的階層の図的理解 ref 『C言語による計算の理論』.iconp.120
https://gyazo.com/39281f1ebfeb95c6b129f9129648c820
$ \Sigma_1述語全体: ①$ \cup②
$ \Pi_1述語全体: ①$ \cup③
$ \Sigma_2述語全体: ①$ \cup②$ \cup③$ \cup④$ \cup⑤
...
上に行くほど複雑度が上がる
例
Totalは⑥の中にいる
一般的には下図のような記され方をする
包含関係$ \subseteqを矢印→で表す
https://gyazo.com/b112ab2eb3d37b5059ea8bc72783a2e2
算術的階層は全て埋まる
上図の①②③...の領域は全て、空にはならない
何かしらの述語が1つ以上入っている
$ n,kを1以上の任意の自然数としたとき以下が成り立つ
$ \Sigma_{n}であって$ \Pi_{n}ではない$ k変数述語が存在する
上図の②⑤⑧..に$ k変数述語が存在する
$ \Pi_{n}であって、$ \Sigma_{n}ではない$ k変数述語が存在する
上図の③⑥⑨..に$ k変数述語が存在する
$ \Sigma_{n+1}かつ$ \Pi_{n+1}であるが、$ \Sigma_{n}でも$ \Pi_{n}でもない$ k変数述語が存在する
上図の①④⑦..に$ k変数述語が存在する
雑に書いても、
$ P\subset$ PH(多項式階層)$ \subset \mathrm{PSPACE}$ \subset決定問題
計算不可能云々に関係なく、算術的階層はあるのかmrsekut.icon
関連
照井一成氏の「算術的階層の厳密性と形式的手法の限界について」