算術階層

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

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

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

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

算術階層は、一階算術の言語で式に分類を割り当てます。分類は、自然数n (0 を含む)に対しておよびで示されます。ここでのギリシャ文字は淡色記号であり、式に設定パラメータが含まれていないことを示します。^{[説明が必要]}${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$

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

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

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

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

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

自然数の集合X は、 X の要素がφ を満たす数である場合、ペアノ算術言語(ゼロは「0」、後続関数は「S」、加算は「+」、乗算は「×」、等号は「=」の記号を使用する第1 階言語) の式φによって定義されます。つまり、すべての自然数nについて、

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

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

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

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

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

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

記号との下付き文字は、式で使用される全称および存在の第 1 階量指定子のブロックの交替数を示します。また、最も外側のブロックは、式では存在であり、式では全称です。 ${\displaystyle n}$${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$

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

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

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

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

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

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

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

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

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

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

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

カントール空間の要素 (自然数の集合とみなされる) とカントール空間のサブセットはどちらも算術階層に分類されますが、これらは同じ階層ではないことに注意してください。実際、2 つの階層の関係は興味深く、自明ではありません。たとえば、カントール空間の要素は (一般に) カントール空間の要素と同じではないため、カントール空間のサブセットになります。ただし、2 つの階層を関連付ける興味深い結果が多数あります。 ${\displaystyle \Pi _{n}^{0}}$${\displaystyle X}$${\displaystyle \{X\}}$${\displaystyle \Pi _{n}^{0}}$

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

• ベール空間の部分集合には、各関数を から へ、そのグラフの特性関数へ写像する、カントール空間の部分集合が存在します。ベール空間の部分集合には、対応するカントール空間の部分集合が同じ分類を持つ場合に限り、分類、 、が与えられます。${\displaystyle \omega }$${\displaystyle \omega }$${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$${\displaystyle \Delta _{n}^{0}}$
• ベール空間上の算術階層の同等の定義は、関数型の2階算術を使用して式の算術階層を定義することによって与えられます。次に、ベール空間上の階層から、カントール空間の部分集合上の算術階層を定義できます。この代替定義は、最初の定義とまったく同じ分類を与えます。

平行定義は、いくつかの自由変数を持つ式を使用して、ベール空間またはカントール空間の有限直交べき乗上の算術階層を定義するために使用されます。算術階層は任意の有効ポーランド空間上で定義できます。カントール空間とベール空間の場合、定義は通常の2階算術の言語に適合するため特に簡単です。

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

各原始再帰関数の関数記号で拡張された言語を使用して、式の算術階層を定義することができます。 このバリエーションは の分類をわずかに変更します。これは、一次ペアノ算術で原始再帰関数を使用するには、一般に、無制限の存在量指定子が必要であり、したがって、この定義によって に含まれるいくつかの集合は、この記事の冒頭で示した定義によって厳密に に含まれるためです。 クラス、および階層内の上位クラスはすべて影響を受けません。 ${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$${\displaystyle \Sigma _{0}^{0}}$${\displaystyle \Sigma _{1}^{0}}$${\displaystyle \Sigma _{1}^{0}}$

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

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

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

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

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

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

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

ポストの定理により、Sとその補集合は両方とも にあります。つまり、S はと の両方にあるため、 にあります。 ${\displaystyle \Sigma _{1}^{0}}$${\displaystyle \Sigma _{1}^{0}}$${\displaystyle \Pi _{1}^{0}}$${\displaystyle \Delta _{1}^{0}}$

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

自然数のチューリング計算可能集合は、まさに算術階層のレベルの集合です。再帰的に列挙可能な集合は、まさにレベルの集合です。 ${\displaystyle \Delta _{1}^{0}}$${\displaystyle \Sigma _{1}^{0}}$

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

ポストの定理は、自然数の集合の算術的階層とチューリング次数との間に密接な関係を確立します。特に、n ≥ 1 のすべての場合について次の事実を確立します。

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

多項式階層は、算術階層の「実行可能なリソース制限付き」バージョンであり、関係する数値に多項式の長さの制限が設定されます (または、同等に、関係するチューリング マシンに多項式時間の制限が設定されます)。算術階層のレベルにあるいくつかの自然数の集合をより細かく分類します。 ${\displaystyle \Delta _{1}^{0}}$

• 分析階層
• レヴィ階層
• 階層（数学）
• 解釈可能性の論理
• 多項式階層