ポストの定理のソースを表示

'''ポストの定理'''（[[英語|英]]: '''Post's theorem'''）は、[[計算可能性理論]]における定理で、[[算術的階層]]と[[チューリング次数]]の関係を表している。名称は[[エミール・ポスト]]に因んでいる。

== 背景 ==
ポストの定理は定義可能性と再帰理論に関連したいくつかの概念を必要とする。この節ではそれら概念の概要を解説する。

[[算術的階層]]は、[[ペアノの公理|ペアノ算術]]で定義可能な[[自然数]]の集合を階層的に分類するものである。ある[[論理式 (数学)|論理式]]が <math>\Sigma^{0}_m</math> に属するとは、それが[[冠頭標準形]]（全ての[[量化]]子が先頭にある）の[[存在記号|存在量化式]]で、存在量化と[[全称記号|全称量化]]が <math>m</math> 回交互にあって、それらが量化されていない論理式に適用されている場合である。次のような形式のペアノ算術の言語で書かれた論理式 <math>\phi(s)</math> は <math>\Sigma^{0}_m</math> 論理式である。
:<math>\exists n_1 \forall n_2 \exists n_3 \forall n_4 \cdots Q n_m \rho(n_1,\ldots,n_m,x_1,\ldots,x_k)</math>
ここで ρ は量化子を含まない論理式で、''Q'' は ''m'' が偶数なら <math>\forall</math>、''m'' が奇数なら <math>\exists</math> である。次のように <math>\rho</math> が[[限定量化]]子のみを含む論理式
:<math>\left(\exists n^1_1\exists n^1_2\cdots\exists n^1_{j_1}\right)\left(\forall n^2_1 \cdots \forall n^2_{j_2}\right)\left(\exists n^3_1\cdots\right)\cdots\left(Q_1 n^m_1 \cdots \right)\rho(n^1_1,\ldots n^m_{j_m},x_1,\ldots,x_k)</math>
は、[[ペアノの公理|ペアノ算術]]の公理により、上記形式と等価である。そのため、<math>\Sigma^{0}_m</math> 論理式をこの代替形式で定義することも珍しくない。

自然数の集合 ''A'' が <math>\Sigma^0_m</math> であるとは、それを <math>\Sigma^0_m</math> 論理式で定義できることを意味し、すなわち、<math>\Sigma^0_m</math> 論理式 <math>\phi(s)</math> を使って、自然数 ''n'' について <math>\phi(n)</math> が成り立つときのみ、その自然数が ''A'' に含まれる。ある集合が <math>\Sigma^0_m</math> であるとき、<math>n > m</math> である任意の ''n'' についての <math>\Sigma^0_n</math> でもある。ただし、個々の ''m'' について <math>\Sigma^0_m</math> ではない <math>\Sigma^0_{m+1}</math> 集合が存在する。従って、量化子の交代回数は、集合の複雑さの尺度を定義するのに必要である。

ポストの定理では、上で定義したような絶対的な算術的階層だけでなく、相対化された算術的階層も使う。自然数の集合 ''A'' が ''B'' に対して相対的に <math>\Sigma^0_m</math> であることを <math>\Sigma^{0,B}_m</math> と表記する。これは、''B'' のメンバーシップを表す述語を含めた拡張言語で記述された <math>\Sigma^0_m</math> 論理式で ''A'' を定義可能であることを意味する。

算術的階層が自然数の集合の定義可能性の尺度となる一方、[[チューリング次数]]は自然数の集合の計算不可能性のレベルの尺度となる。集合 ''A'' が集合 ''B'' に[[チューリング還元]]可能であることを <math>A \leq_T B</math> と記述し、''B'' についての神託を与える[[神託機械]]によって ''A'' の[[指示関数|特性関数]]を計算できることを意味する。集合 ''A'' の[[チューリングジャンプ]]は、''A'' に関連する[[停止性問題]]の形式である。集合 ''A'' のチューリングジャンプ <math>A'</math> は、''A'' についての神託機械を持ち ''0'' が入力されたときに停止するチューリング機械のインデックスの集合である。あらゆる集合 ''A'' はそのチューリングジャンプにチューリング還元可能であるが、ある集合のチューリングジャンプは決して元の集合にチューリング還元できない。

ポストの定理は有限回反復されたチューリングジャンプを使用する。任意の自然数の集合 ''A'' について、<math>A^{(n)}</math> とは ''A'' のチューリングジャンプを ''n'' 回反復したものを表す。従って、<math>A^{(0)}</math> は ''A'' そのものであり、<math>A^{(n+1)}</math> は <math>A^{(n)}</math> のチューリングジャンプである。

== ポストの定理とその系 ==
ポストの定理は、算術的階層と <math>\emptyset^{(n)}</math> の形式のチューリング次数、すなわち空集合の有限回反復したチューリングジャンプとの密接な関係を確立する（空集合を任意の計算可能な集合に置き換えても定理は成り立つ）。

ポストの定理は次の通りである。
# 集合 ''B'' が <math>\Sigma^0_{n+1}</math> であるのは、<math>B</math> が <math>\emptyset^{(n)}</math> の神託機械を持つチューリング機械により[[帰納的可算集合|帰納可枚挙]]な場合である。すなわち、''B'' が <math>\Sigma^{0,\emptyset^{(n)}}_1</math> で表される場合である。
# 集合 <math>\emptyset^{(n)}</math> は、<math>n > 0</math> のあらゆる ''n'' について <math>\Sigma^0_n</math> 完全である。すなわち、<math>\Sigma^0_n</math> のあらゆる集合は <math>\emptyset^{(n)}</math> に[[多対一還元]]可能である。

ポストの定理には様々な系があり、算術的階層とチューリング次数の様々な関係を表している。例えば、以下のような系がある。
# ある集合 ''C'' があるとする。集合 ''B'' が <math>\Sigma^{0,C}_{n+1}</math> であるのは、''B'' が <math>\Sigma^{0,C^{(n)}}_1</math> となることと等価である。これはポストの定理の前半部分を ''C'' の神託機械で相対化したものである。
# 集合 ''B'' が <math>\Delta_{n+1}</math> であるのは、<math>B \leq_T \emptyset^{(n)}</math> と等価である。より一般化すると、''B'' が <math>\Delta^C_{n+1}</math> であるのは、<math>B \leq_T C^{(n)}</math> と等価である。
# 集合が算術的に定義できるのは、ある ''n'' について <math>\Sigma^0_n</math> である場合である。ポストの定理によれば、集合が算術的といえるのは、その集合をある ''m'' について <math>\emptyset^{(m)}</math> にチューリング還元可能な場合のみである。

== 参考文献 ==
* Rogers, H.   ''The Theory of Recursive Functions and Effective Computability'', MIT Press. ISBN 0-262-68052-1;  ISBN 0-07-053522-1 
* Soare, R. ''Recursively enumerable sets and degrees.'' Perspectives in Mathematical Logic.  Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7

{{DEFAULTSORT:ほすとのていり}}
[[Category:数理論理学的階層]]
[[Category:数学基礎論の定理]]
[[Category:計算可能性理論]]

[[Category:数学に関する記事]]