ポストの定理
ポストの定理は、算術的階層と ∅ ( n ) {\displaystyle \emptyset ^{(n)}} の形式のチューリング次数、すなわち空集合の有限回反復したチューリングジャンプとの密接な関係を確立する(空集合を任意の計算可能な集合に置き換えても定理は成り立つ)。
ポストの定理は次の通りである。
集合 B が Σ n + 1 0 {\displaystyle \Sigma _{n+1}^{0}} であるのは、 B {\displaystyle B} が ∅ ( n ) {\displaystyle \emptyset ^{(n)}} の神託機械を持つチューリング機械により帰納可枚挙な場合である。すなわち、B が Σ 1 0 , ∅ ( n ) {\displaystyle \Sigma _{1}^{0,\emptyset ^{(n)}}} で表される場合である。
集合 ∅ ( n ) {\displaystyle \emptyset ^{(n)}} は、 n > 0 {\displaystyle n>0} のあらゆる n について Σ n 0 {\displaystyle \Sigma _{n}^{0}} 完全である。すなわち、 Σ n 0 {\displaystyle \Sigma _{n}^{0}} のあらゆる集合は ∅ ( n ) {\displaystyle \emptyset ^{(n)}} に多対一還元可能である。
ポストの定理には様々な系があり、算術的階層とチューリング次数の様々な関係を表している。例えば、以下のような系がある。
ある集合 C があるとする。集合 B が Σ n + 1 0 , C {\displaystyle \Sigma _{n+1}^{0,C}} であるのは、B が Σ 1 0 , C ( n ) {\displaystyle \Sigma _{1}^{0,C^{(n)}}} となることと等価である。これはポストの定理の前半部分を C の神託機械で相対化したものである。
集合 B が Δ n + 1 {\displaystyle \Delta _{n+1}} であるのは、 B ≤ T ∅ ( n ) {\displaystyle B\leq _{T}\emptyset ^{(n)}} と等価である。より一般化すると、B が Δ n + 1 C {\displaystyle \Delta _{n+1}^{C}} であるのは、 B ≤ T C ( n ) {\displaystyle B\leq _{T}C^{(n)}} と等価である。
集合が算術的に定義できるのは、ある n について Σ n 0 {\displaystyle \Sigma _{n}^{0}} である場合である。ポストの定理によれば、集合が算術的といえるのは、その集合をある m について ∅ ( m ) {\displaystyle \emptyset ^{(m)}} にチューリング還元可能な場合のみである。