算術階層

数理論理学において、算術的階層、算術的階層、あるいはクリーネ・モストフスキー階層（数学者スティーブン・コール・クリーネとアンジェイ・モストフスキーにちなんで名付けられている）は、集合を定義する式の複雑さに基づいて、特定の集合を分類する。分類された集合は算術的であると呼ばれる。算術的階層は、クリーネ（1943）とモストフスキー（1946）によって独立に発明された。^[1]

算術階層は、計算可能性理論、有効記述集合論、ペアノ算術などの形式理論の研究において重要です。

Tarski -Kuratowski アルゴリズムは、式に割り当てられた分類とそれが定義するセットの上限を取得する簡単な方法を提供します。

超算術階層と解析階層は算術階層を拡張して追加の式と集合を分類します。

数式の算術階層

算術階層は、一階算術言語における式に分類を割り当てる。分類は自然数n （0を含む）に対しておよびで示される。ここでギリシャ文字は細字で表され、式にパラメータが設定されていないことを示している。^[^{説明が必要}^] $\Sigma _{n}^{0}$ $\Pi _{n}^{0}$

式が、無制限の量指定子を持たない式、つまり、すべての量指定子が制限付き量指定子である式と論理的に同等である場合、分類およびが割り当てられます。 $\phi$ $\phi$ $\Sigma _{0}^{0}$ $\Pi _{0}^{0}$

分類とは次の規則を使用して、すべての自然数nに対して帰納的に定義されます。 $\Sigma _{n}^{0}$ $\Pi _{n}^{0}$

が（）の形式と論理的に同等である場合、にはという分類が割り当てられます。 $\phi$ $\exists m_{1}\exists m_{2}\cdots \exists m_{k}\psi$ $\psi$ $\Pi _{n}^{0}$ $\phi$ $\Sigma _{n+1}^{0}$
が（）の形式と論理的に同等である場合、にはという分類が割り当てられます。 $\phi$ $\forall m_{1}\forall m_{2}\cdots \forall m_{k}\psi$ $\psi$ $\Sigma _{n}^{0}$ $\phi$ $\Pi _{n+1}^{0}$

式は、いくつかの存在量指定子で始まり、一連の存在量指定子と全称量指定子の間で交互に繰り返される式と同等です。一方、式は、いくつかの全称量指定子で始まり、同様に交互に繰り返される式と同等です。 $\Sigma _{n}^{0}$ $n-1$ $\Pi _{n}^{0}$

すべての一階論理式は冠頭正規形を持つため、すべての論理式には少なくとも1つの分類が割り当てられます。冗長な量指定子は任意の論理式に追加できるため、論理式に分類またはが割り当てられると、すべてのm > nに対して分類とが割り当てられます。したがって、論理式に割り当てられる唯一の適切な分類はnが最も小さい分類であり、他のすべての分類はそこから決定できます。^[^{説明が必要}^] $\Sigma _{n}^{0}$ $\Pi _{n}^{0}$ $\Sigma _{m}^{0}$ $\Pi _{m}^{0}$

自然数の集合の算術的階層

自然数の集合Xは、ペアノ算術言語（記号「0」が零、後続関数「S」、加算「+」、乗算「×」、等号「=」を用いる一階述語言語）における式φによって定義される。ただし、 Xの要素がφ を満たす数と一致する場合である。つまり、すべての自然数nについて、

n\in X\Leftrightarrow \mathbb {N} \models \varphi ({\underline {n}}),

ここで、は算術言語におけるに対応する数値である。集合が一階算術で定義可能とは、それがペアノ算術言語における何らかの式で定義される場合を言う。 ${\underline {n}}$ $n$

第一階算術で定義可能な自然数の集合Xにはそれぞれ、、、（は自然数）の形式の分類が以下のように割り当てられます。Xが式で定義可能な場合、 Xには分類が割り当てられます。Xが式で定義可能な場合、 Xには分類が割り当てられます。Xがとの両方である場合、Xには追加の分類が割り当てられます。 $\Sigma _{n}^{0}$ $\Pi _{n}^{0}$ $\Delta _{n}^{0}$ $n$ $\Sigma _{n}^{0}$ $\Sigma _{n}^{0}$ $\Pi _{n}^{0}$ $\Pi _{n}^{0}$ $\Sigma _{n}^{0}$ $\Pi _{n}^{0}$ $X$ $\Delta _{n}^{0}$

式について話すことはほとんど意味をなさないことに注意してください。式の最初の量化子は、存在量化子か普遍量化子のいずれかです。したがって、集合は必ずしもとの両方である式で定義されるわけではありません。むしろ、集合を定義する式はとの両方で定義されます。例えば、奇数の自然数の集合はまたはのいずれかで定義できます。 $\Delta _{n}^{0}$ $\Delta _{n}^{0}$ $\Delta _{n}^{0}$ $\Sigma _{n}^{0}$ $\Pi _{n}^{0}$ $\Sigma _{n}^{0}$ $\Pi _{n}^{0}$ $n$ $\forall k(n\neq 2\times k)$ $\exists k(n=2\times k+1)$

自然数の集合の有限な直積冪上の算術階層を定義するために、並列定義が用いられる。1つの自由変数を持つ式の代わりに、 k個の自由一階変数を持つ式を用いて、 k組の自然数の集合上の算術階層を定義する。これらは実際には、ペアリング関数によって関連付けられている。

表記の意味

数式上の算術階層の表記には、次のような意味が考えられます。

記号の添え字と下付き文字は、式中で使用される全称一階量化子と存在一階量化子のブロックの交替回数を示します。さらに、最外郭ブロックは式中では存在量化子、式中では全称です。 $n$ $\Sigma _{n}^{0}$ $\Pi _{n}^{0}$ $\Sigma _{n}^{0}$ $\Pi _{n}^{0}$

記号、、の上付き文字は、量化されるオブジェクトの型を示します。型 0 のオブジェクトは自然数であり、型のオブジェクトは型のオブジェクトのセットを自然数にマップする関数です。自然数から自然数への関数など、より高次の型のオブジェクトに対する量化は、解析階層のように、0 より大きい上付き文字で記述されます。上付き文字 0 は数値に対する量指定子を示し、上付き文字 1 は数値から数値 (型 1 のオブジェクト) への関数に対する量化を示し、上付き文字 2 は型 1 のオブジェクトを受け取って数値を返す関数に対する量化に対応します、などとなります。 $0$ $\Sigma _{n}^{0}$ $\Pi _{n}^{0}$ $\Delta _{n}^{0}$ $i+1$ $i$

例

数の集合とは、有界量指定子のみを持つ形式の式で定義できる集合のことである。これらはまさに再帰的に列挙可能な集合である。 $\Sigma _{1}^{0}$ $\exists n_{1}\cdots \exists n_{k}\psi (n_{1},\ldots ,n_{k},m)$ $\psi$
全関数を計算するチューリングマシンのインデックスとなる自然数の集合はです。直感的に、インデックスがこの集合に含まれるのは、任意の「インデックスを持つチューリングマシンがステップ後の入力で停止するようなが存在する」場合のみです。完全な証明は、前の文で引用符で囲まれた性質が、ペアノ算術の言語で式によって定義可能であることを示します。 $\Pi _{2}^{0}$ $e$ $m$ $s$ $e$ $m$ $s$ $\Sigma _{1}^{0}$
ベール空間またはカントール空間の任意の部分集合は、その空間上の通常の位相において開集合となる。さらに、そのような任意の集合に対して、その和が元の集合となるような基本開集合のゲーデル数の計算可能な列挙が存在する。このため、集合は実効的に開集合と呼ばれることがある。同様に、すべての集合は閉集合であり、それらの集合は実効的に閉集合と呼ばれることがある。 $\Sigma _{1}^{0}$ $\Sigma _{1}^{0}$ $\Pi _{1}^{0}$ $\Pi _{1}^{0}$
カントール空間またはベール空間のすべての算術的部分集合はボレル集合である。ライトフェイス・ボレル階層は、算術階層を拡張して追加のボレル集合を含むようにする。例えば、カントール空間またはベール空間のすべての部分集合は集合、つまり可算個数の開集合の共通集合に等しい集合である。さらに、これらの開集合はそれぞれであり、これらの開集合のゲーデル数のリストには計算可能な列挙が存在する。が自由集合変数と自由数変数を持つ式である場合、集合は自然数集合上の範囲の形式の集合の共通集合である。 $\Pi _{2}^{0}$ $G_{\delta }$ $\Sigma _{1}^{0}$ $\phi (X,n,m)$ $\Sigma _{0}^{0}$ $X$ $n,m$ $\Pi _{2}^{0}$ $\{X\mid \forall n\exists m\phi (X,n,m)\}$ $\Sigma _{1}^{0}$ $\{X\mid \exists m\phi (X,n,m)\}$ $n$
式は、すべてのケースを一つずつ調べることで検証できます。これは、すべての量指定子が有界であるため可能です。この処理時間は引数の多項式です（例えば、の場合、は多項式です）。したがって、対応する決定問題はEに含まれます（はビット数で指数関数であるため）。これは、原始再帰関数の使用を許可するの代替定義では成立しません。なぜなら、量指定子は引数の任意の原始再帰関数によって有界になる可能性があるからです。 $\Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}$ $n$ $\varphi (n)$ $n$ $\Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}$
有界量指定子を用いた原始再帰関数の使用を許可する代替定義における式は、原始再帰関数の形式の自然数集合に対応する。これは、有界量指定子を許可しても定義に何も追加されないためである。原始再帰の場合、はと同じであり、はと同じである。値過程再帰を用いると、これらはそれぞれ単一の原始再帰関数で定義できる。 $\Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}$ $\{n:f(n)=0\}$ $f$ $f$ $\forall k<n:f(k)=0$ $f(0)+f(1)+...f(n-1)=0$ $\exists k<n:f(k)=0$ $f(0)\cdot f(1)\cdot \ldots \cdot f(n-1)=0$

相対化された算術階層

集合Xが別の集合Yに対して再帰的であることが何を意味するかを、 Xを定義する計算がY を神託として参照できるようにすることで定義できるのと同じように、この概念を算術階層全体に拡張して、X が、またはYにおいて（それぞれ、およびと表記）であることが何を意味するかを定義できます。そのためには、自然数集合Yを固定し、Yのメンバーシップに関する述語をペアノ算術の言語に追加します。次に、この拡張言語の式で定義されている場合、 X はにあると言います。言い換えると、Yのメンバーシップについて質問することが許されている式で定義されている場合、 Xはです。あるいは、集合を、 Yにおいて再帰的な集合から始めて、これらの集合の和集合と積集合をn回まで交互に行うことで構築できる集合と見なすこともできます。 $\Sigma _{n}^{0}$ $\Delta _{n}^{0}$ $\Pi _{n}^{0}$ $\Sigma _{n}^{0,Y}$ $\Delta _{n}^{0,Y}$ $\Pi _{n}^{0,Y}$ $\Sigma _{n}^{0,Y}$ $\Sigma _{n}^{0}$ $\Sigma _{n}^{0,Y}$ $\Sigma _{n}^{0}$ $\Sigma _{n}^{0,Y}$

例えば、Y を自然数の集合とします。XをYの元で割り切れる数の集合とします。すると、X は式で定義されるので、Xはに含まれます（実際には、両方の量指定子をnで制限できるため、X もに含まれます）。 $\phi (n)=\exists m\exists t(Y(m)\land m\times t=n)$ $\Sigma _{1}^{0,Y}$ $\Delta _{0}^{0,Y}$

算術的還元可能性と次数

算術的還元可能性は、チューリング還元可能性と超算術的還元可能性の中間の概念です。

集合が算術的(算術的かつ算術的に定義可能ともいう) なのは、それがペアノ算術の言語におけるなんらかの式で定義されている場合です。同様に、Xが算術的であるとは、X が、あるいはなんらかの自然数nに対してである場合です。集合Xが、と表記される集合Yにおいて算術的であるとは、 X が、 Yの帰属関係を述語として拡張されたペアノ算術の言語におけるなんらかの式として定義可能である場合です。同様に、X が、 Yにおいて算術的であるとは、Xが、あるいはなんらかの自然数nに対してである場合です。の同義語は、XがYに算術的に還元可能であることです。 $\Sigma _{n}^{0}$ $\Pi _{n}^{0}$ $X\leq _{A}Y$ $\Sigma _{n}^{0,Y}$ $\Pi _{n}^{0,Y}$ $X\leq _{A}Y$

この関係は反射的かつ推移的であり、したがって、規則によって定義される関係は $X\leq _{A}Y$ $\equiv _{A}$

X\equiv _{A}Y\iff X\leq _{A}Y\land Y\leq _{A}X

は同値関係である。この関係の同値類は算術次数と呼ばれ、の下で部分的に順序付けられる。 $\leq _{A}$

カントール空間とベール空間の部分集合の算術的階層

カントール空間は0 と 1 の無限列全体の集合であり、ベール空間はまたはと表記され、自然数の無限列全体の集合である。カントール空間の元は自然数の集合と同一視でき、ベール空間の元は自然数から自然数への写像と同一視できることに注意されたい。 $2^{\omega }$ $\omega ^{\omega }$ ${\mathcal {N}}$

二階算術の通常の公理化では、集合に基づく言語が用いられ、集合量指定子はカントール空間上で量化を行うものと自然に見なすことができます。カントール空間の部分集合は、式で定義可能な場合、分類が割り当てられます。集合は、式で定義可能な場合、分類が割り当てられます。集合がとの両方を満たす場合、追加の分類が与えられます。例えば、がすべて 0 ではない無限二進文字列の集合（または、空でない自然数の集合の集合）とします。は式で定義されているため、集合であることが分かります。 $\Sigma _{n}^{0}$ $\Sigma _{n}^{0}$ $\Pi _{n}^{0}$ $\Pi _{n}^{0}$ $\Sigma _{n}^{0}$ $\Pi _{n}^{0}$ $\Delta _{n}^{0}$ $O\subseteq 2^{\omega }$ $O=\{X\in 2^{\omega }|\exists n(X(n)=1)\}$ $O$ $\Sigma _{1}^{0}$ $\Sigma _{1}^{0}$

カントール空間の元（自然数の集合とみなされる）とカントール空間の部分集合はどちらも算術階層に分類されますが、これらは同じ階層ではありません。実際、これら2つの階層の関係は興味深く、自明ではありません。例えば、カントール空間の元は（一般に）カントール空間の元と同じではないため、カントール空間の部分集合となります。しかしながら、これら2つの階層を関連付ける興味深い結果は数多く存在します。 $\Pi _{n}^{0}$ $X$ $\{X\}$ $\Pi _{n}^{0}$

ベール空間のサブセットを算術階層で分類する方法は 2 つあります。

ベール空間の部分集合は、各関数をからへ、そのグラフの特性関数へ写像するカントール空間の部分集合に対応する。ベール空間の部分集合が、、に分類されるのは、対応するカントール空間の部分集合が同じ分類を持つ場合のみである。 $\omega$ $\omega$ $\Sigma _{n}^{0}$ $\Pi _{n}^{0}$ $\Delta _{n}^{0}$
ベール空間上の算術的階層構造の同等の定義は、関数型二階算術を用いて公式の算術的階層構造を定義することによって与えられ、カントール空間の部分集合上の算術的階層構造はベール空間上の階層構造から定義できる。この代替定義は、最初の定義と全く同じ分類を与える。

平行定義は、ベール空間またはカントール空間の有限直交座標上の算術階層を、複数の自由変数を含む公式を用いて定義するのに用いられる。この算術階層は任意の有効ポーランド空間上で定義できる。特にカントール空間とベール空間については、通常の二階算術の言語に適合するため、定義は単純である。

カントール空間とベール空間の部分集合の算術階層を、ある自然数の集合に対して定義することもできることに注意してください。実際、太字は自然数集合Yすべてに対するの和集合です。太字の階層はボレル集合の標準的な階層であることに注意してください。 $\mathbf {\Sigma } _{n}^{0}$ $\Sigma _{n}^{0,Y}$

拡張とバリエーション

各原始再帰関数に対応する関数記号を拡張した言語を用いて、式の算術階層を定義することが可能です。この変形によりの分類がわずかに変更されます。これは、一階ペアノ算術において原始再帰関数を使用するには、一般に、有界な存在量化子が必要となるため、この定義でに含まれる集合の一部は、この記事の冒頭で示した定義により厳密にに含まれるためです。クラス、ひいては階層内の上位クラスはすべて影響を受けません。 $\Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}$ $\Sigma _{0}^{0}$ $\Sigma _{1}^{0}$ $\Sigma _{1}^{0}$

階層構造のより意味的なバリエーションは、自然数上のすべての有限関係に対して定義できます。以下の定義を用います。すべての計算可能関係はと定義されます。分類とは、以下の規則を用いて帰納的に定義されます。 $\Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}$ $\Sigma _{n}^{0}$ $\Pi _{n}^{0}$

関係がである場合、関係はと定義されます $R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})\,$ $\Sigma _{n}^{0}$ $S(n_{1},\ldots ,n_{l})=\forall m_{1}\cdots \forall m_{k}R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})$ $\Pi _{n+1}^{0}$
関係がである場合、関係はと定義されます $R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})\,$ $\Pi _{n}^{0}$ $S(n_{1},\ldots ,n_{l})=\exists m_{1}\cdots \exists m_{k}R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})$ $\Sigma _{n+1}^{0}$

この変化は、いくつかの集合の分類をわずかに変更する。特に、集合のクラス（クラス内の関係によって定義可能）としてのは、以前の定義におけると同一である。これは、自然数、ベール空間、カントール空間上の有限関係をカバーするように拡張できる。 $\Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}$ $\Delta _{1}^{0}$

プロパティ

自然数の集合の算術階層とカントール空間またはベール空間の部分集合の算術階層には、次の特性が成り立ちます。

コレクションとコレクションは、それぞれの要素の有限和と有限積に対して閉じています。 $\Pi _{n}^{0}$ $\Sigma _{n}^{0}$
集合がである場合、かつその補集合はである。集合がでありである場合、かつその補集合もである。 $\Sigma _{n}^{0}$ $\Pi _{n}^{0}$ $\Delta _{n}^{0}$ $\Sigma _{n}^{0}$ $\Pi _{n}^{0}$ $\Delta _{n}^{0}$
包含関係とはすべてのに対して成り立つ。したがって、階層構造は崩れない。これはポストの定理の直接的な帰結である。 $\Pi _{n}^{0}\subsetneq \Pi _{n+1}^{0}$ $\Sigma _{n}^{0}\subsetneq \Sigma _{n+1}^{0}$ $n$
包含関係、およびはに対して成り立ちます。 $\Delta _{n}^{0}\subsetneq \Pi _{n}^{0}$ $\Delta _{n}^{0}\subsetneq \Sigma _{n}^{0}$ $\Sigma _{n}^{0}\cup \Pi _{n}^{0}\subsetneq \Delta _{n+1}^{0}$ $n\geq 1$

たとえば、ユニバーサルチューリングマシン Tの場合、 T がnでは停止するがmでは停止しないようなペア ( n、m ) の集合は、（停止問題の神託によって計算可能である）には存在しますが、には存在しません。 $\Delta _{2}^{0}$ $\Sigma _{1}^{0}\cup \Pi _{1}^{0}$
$\Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}=\Sigma _{0}^{0}\cup \Pi _{0}^{0}\subseteq \Delta _{1}^{0}$ 。包含はこの記事で与えられた定義により厳密であるが、上記の定義のバリエーションの 1 つではとの同一性が成立する。 $\Delta _{1}^{0}$

チューリングマシンとの関係

計算可能集合

Sがチューリング計算可能集合である場合、Sとその補集合は両方とも再帰的に列挙可能です（TがSの入力に対して 1 を返し、それ以外の場合は 0 を返すチューリングマシンである場合、前者に対してのみ停止するチューリングマシンと、後者に対してのみ停止する別のチューリングマシンを構築できます）。

ポストの定理によれば、Sとその補集合は両方ともに含まれます。これは、S がとの両方に含まれ、したがってに含まれることを意味します。 $\Sigma _{1}^{0}$ $\Sigma _{1}^{0}$ $\Pi _{1}^{0}$ $\Delta _{1}^{0}$

同様に、内の任意の集合Sについて、Sとその補集合は両方ともに含まれ、したがって（ポストの定理により）それぞれ何らかのチューリングマシンT ₁およびT ₂によって再帰的に列挙可能です。任意の数nについて、これらのうちの1つが停止します。したがって、 T ₁とT ₂を交互に実行し、前者が停止したときに停止して 1 を返し、後者が停止したときに停止して 0 を返すチューリングマシンTを構築できます。したがって、 T はすべてのnで停止し、 Sに含まれるかどうかを返します。したがって、Sは計算可能です。 $\Delta _{1}^{0}$ $\Sigma _{1}^{0}$

主な結果の要約

自然数のチューリング計算可能集合は、算術階層のレベルの集合と全く同じである。再帰的に可算な集合は、レベルの集合と全く同じである。 $\Delta _{1}^{0}$ $\Sigma _{1}^{0}$

オラクルマシンは自身の停止問題を解くことができません（チューリングの証明のバリエーションが適用されます）。オラクルマシンの停止問題は実際にはにあります。 $\Delta _{n}^{0,Y}$ $\Sigma _{n+1}^{0,Y}$

ポストの定理は、自然数の集合の算術的階層とチューリング次数との間に密接な関係を確立する。特に、n ≥ 1 の全ての数に対して以下の事実が成立することを示す。

集合(空集合のn番目のチューリングジャンプ)はにおいて多対一完全です。 $\emptyset ^{(n)}$ $\Sigma _{n}^{0}$
このセットはにおいて多対一完全です。 $\mathbb {N} \setminus \emptyset ^{(n)}$ $\Pi _{n}^{0}$
この集合はにおいてチューリング完全です。 $\emptyset ^{(n-1)}$ $\Delta _{n}^{0}$

多項式階層は、算術階層の「実行可能資源制限型」バージョンであり、関係する数に多項式の長さの上限が設定されます（あるいは、等価的に、関係するチューリングマシンに多項式時間の上限が設定されます）。これは、算術階層のレベルにあるいくつかの自然数の集合をより細かく分類します。 $\Delta _{1}^{0}$

他の階層との関係

ポイントクラス v t e
ライトフェイス		太字
Σ⁰ ₀= Π⁰ ₀= Δ⁰ ₀（Δと同じ場合もある）⁰ ₁）		Σ⁰ ₀= Π⁰ ₀= Δ⁰ ₀（定義されている場合）
Δ⁰ ₁=再帰的		Δ⁰ ₁=閉じた
Σ⁰ ₁=再帰的に列挙可能	Π⁰ ₁= 共再帰的に列挙可能	Σ⁰ ₁= G =オープン	Π⁰ ₁= F =閉じた
Δ⁰ ₂		Δ⁰ ₂
Σ⁰ ₂	Π⁰ ₂	Σ⁰ ₂= Fσ	Π⁰ ₂= G _δ
Δ⁰ ₃		Δ⁰ ₃
Σ⁰ ₃	Π⁰ ₃	Σ⁰ ₃= G _δσ	Π⁰ ₃= F _σδ
⋮		⋮
Σ⁰ _<ω= Π⁰ _<ω= Δ⁰ _<ω= Σ¹ ₀= Π¹ ₀= Δ¹ ₀=算術		Σ⁰ _<ω= Π⁰ _<ω= Δ⁰ _<ω= Σ¹ ₀= Π¹ ₀= Δ¹ ₀= 太字の算術
⋮		⋮
Δ⁰ _α（α再帰的）		Δ⁰ _α（αは可算）
Σ⁰ _α	Π⁰ _α	Σ⁰ _α	Π⁰ _α
⋮		⋮
Σ⁰ _ω^CK1= Π⁰ _ω^CK1= Δ⁰ _ω^CK1= Δ¹ ₁=超算術的		Σ⁰ _{ω ₁}= Π⁰ _{ω ₁}= Δ⁰ _{ω ₁}= Δ¹ ₁= B =ボレル
Σ¹ ₁= ライトフェイス分析	Π¹ ₁= ライトフェイスコアナリティック	Σ¹ ₁= A =分析的	Π¹ ₁= CA =共分析
Δ¹ ₂		Δ¹ ₂
Σ¹ ₂	Π¹ ₂	Σ¹ ₂= PCA	Π¹ ₂= CPCA
Δ¹ ₃		Δ¹ ₃
Σ¹ ₃	Π¹ ₃	Σ¹ ₃= PCPCA	Π¹ ₃= CPCPCA
⋮		⋮
Σ¹ _<ω= Π¹ _<ω= Δ¹ _<ω= Σ² ₀= Π² ₀= Δ² ₀=分析的		Σ¹ _<ω= Π¹ _<ω= Δ¹ _<ω= Σ² ₀= Π² ₀= Δ² ₀= P =射影的
⋮		⋮

参照

参考文献

^ PG Hinman、「再帰理論的階層」（p.89）、Perspectives in Logic、1978年。Springer-Verlag Berlin Heidelberg、ISBN 3-540-07904-1。

ジャパリゼ、ジョルジー（1994）「算術階層の論理」、純粋・応用論理学会誌、66（2）：89-112、doi：10.1016/0168-0072（94）90063-9、Zbl 0804.03045。
モスコヴァキス、ヤニス・N.（1980）「記述的集合論」『論理と数学の基礎研究』第100巻、北ホラント、ISBN 0-444-70199-0、Zbl 0433.03025。
ニース、アンドレ（2009）、計算可能性とランダム性、オックスフォード・ロジック・ガイド、第51巻、オックスフォード：オックスフォード大学出版局、ISBN 978-0-19-923076-1、Zbl 1169.03034。
ロジャース、H. Jr. (1967)、「再帰関数の理論と実効計算可能性」、メイデンヘッド：マグロウヒル、Zbl 0183.01401。

[1] PG Hinman、「再帰理論的階層」（p.89）、Perspectives in Logic、1978年。Springer-Verlag Berlin Heidelberg、ISBN 3-540-07904-1。

v t e 複雑度クラス
実現可能と考えられる	ログタイム AC ⁰ ACC ⁰ TC TC ⁰ L SL RL フロリダ州オランダ NL完全ノースカロライナ州 SC CC P P完全 ZPP RP BPP BQP APX FP
実行不可能と疑われる	上 NP NP完全 NP困難共同NP 共NP完全 TFNP FNP 午前 QMA PH ⊕P PP #P #P完了 IP Pスペース PSPACE完全版
実現不可能とみなされる	有効期限ネクスタイムエクスプスペース 2-EXPTIME 初等非初等広報 R 再エネ全て
その他の複雑性クラス	ポリL QP
クラス階層	多項式階層指数階層グジェゴルチク階層算術階層ブール階層
クラスのファミリー	Dタイム NTIME DSPACE Nスペース確率的に検証可能な証明インタラクティブな証明システム
複雑性クラスのリスト