ポストの定理

ポストの定理

ポストの定理（英: Post's theorem）は、計算可能性理論における重要な概念で、算術的階層とチューリング次数の関係を示しています。この定理は、エミール・ポストによって名付けられました。

背景

この定理を理解するためには、まずいくつかの関連する概念を把握する必要があります。算術的階層は、ペアノ算術を通じて定義される自然数の集合を階層的に分類します。ある論理式が
A0Σ_m^0 に属する場合、これはその論理式が冠頭標準形となっていることを示し、存在量化と全称量化が交互に m 回繰り返される形を指します。たとえば、次のような論理式がこの形式に当てはまります:

$$ orall n_{2} orall n_{4} ext{ のような論理式 } ρ(n_{1}, ext{...}, n_{m}, x_{1}, ext{...}, x_{k}) $$

ここで、ρ は量化子を含まない論理式で、Q は m が偶数なら全称量化、奇数の場合は存在量化を表します。自然数集合 A が
A0Σ_m^0 であるとは、その集合をこの形式の論理式で定義できることを意味します。ある集合がこの階層に属する場合、その複雑さは量化子の交代回数によって測られます。

ポストの定理では、標準的な算術的階層だけでなく、相対化された算術的階層も用います。ここで、自然数集合 A が別の集合 B に対して相対的に
A0Σ_m^0 であることを表すには、通常の論理式に B のメンバーシップを示す述語を加えた形で記述します。

チューリング次数

算術的階層が自然数の集合の定義の複雑さを表す一方で、チューリング次数は計算不可能性のレベルを示します。集合 A が集合 B にチューリング還元可能であるとは、B に関する情報（神託）を利用して A の特性関数を求めることができることを意味します。すべての集合 A はそのチューリングジャンプにチューリング還元可能ですが、その逆は成り立ちません。ポストの定理は、このチューリングジャンプの有限反復を使用します。

集合 A(n) は、A のチューリングジャンプを n 回反復したものを表します。具体的には、A(0) は A 自体であり、A(n + 1) は A(n) のチューリングジャンプを意味します。

定理の内容

ポストの定理は、計算可能性と算術的な性質の間に強い関係を確立します。具体的には、集合 B が
A0Σ_{n+1}^0 であることは、B が
A0∅(n) の神託を持つチューリング機械によって可枚挙であることと等価です。このことは、空集合や他の計算可能な集合に基づいて推論を行う際に重要です。

そのため、ポストの定理は、算術的階層とチューリング次数の様々な関係を明らかにします。これにより、定義可能性や計算上の性質といった重要なトピックに新たな視座を提供します。さらに、ポストの定理には様々な系があり、他の数学的概念にも応用可能です。たとえば、集合 C に対する相対化された定理や、特定の条件下での算術的な関係を示す結果が報告されています。

結論

ポストの定理は、計算可能性理論において非常に重要な位置を占めており、算術的階層とチューリング次数の相互作用を理解することで、数理論理や計算理論の進展に寄与しています。これらの概念を深く理解することは、数理論理の新しい応用を開く可能性を秘めています。

もう一度検索