算術的階層
Arithmetical hierarchy
Kleene hierarchy
前提
n: 1以上の自然数
k: 自然数
\vec{x},\vec{y}: 長さkの数の列
それぞれ(x_1,\cdots,x_k)
定理: 述語Aに関する以下の2条件は同値
Aは計算可能
Aは、\Sigma_1でもあり、\Pi_1でもある
証明
Aが1変数述語のときを考える
A=\Sigma_1であり、この補集合は\bar{A}=\bar{\Sigma_1}=\Pi_1である
\Sigma_1も\Pi_1も半決定可能なので、A,\bar{A}もまた半決定可能である
半決定可能#5f943b0319827000009c08c6の定理が成り立つので、Aは計算可能である
Aが2変数以上の述語のときも同様
算術的階層の図的理解 ref 
p.120
決定可能: ①
\Sigma_1述語全体: ①\cup②
\Pi_1述語全体: ①\cup③
\Sigma_2述語全体: ①\cup②\cup③\cup④\cup⑤
...
上に行くほど複雑度が上がる
上の定理算術的階層#5fa0051f1982700000dfd6edは、ちょうど①のことを言っていることがわかる
例
haltは②の中にいる
Totalは⑥の中にいる
一般的には下図のような記され方をする
包含関係\subseteqを矢印→で表す
算術的階層は全て埋まる
上図の①②③...の領域は全て、空にはならない
何かしらの述語が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変数述語が存在する
\Delta_0の中に、多項式階層を含む
雑に書いても、
P\subsetPH(多項式階層)\subset \mathrm{PSPACE}\subset決定問題
計算不可能云々に関係なく、算術的階層はあるのか
量化子が交互であることに必然性はあるのか
関連
照井一成氏の「算術的階層の厳密性と形式的手法の限界について」