低基底定理のソースを表示


[[計算可能性理論]]における'''低基底定理'''（{{lang-en-short|low basis theorem}}）は <math>2^{\omega}</math> の任意の空でない[[Π01クラス|<math>\Pi^0_1</math>クラス]]（[[算術的階層]]を見よ）は[[低_(計算可能性理論)|低次数]]の元を含むことを示す（Soare 1987:109）もので、1972年に[[カール・ショカシュ]]と[[ロバート・アーヴィング・ソーア]]によって証明せられた（Nies 2009:57）。Cenzer (1993:53) はこれを"もしかすると <math>\Pi^0_1</math> クラスの理論において最も引用されている結果"と記している。

この定理の証明には <math>\Pi^0_1</math> クラスによる強制法が用いられている（Cooper 2004:330）。未出版の元々の証明では <math>0'</math>-構成が用いられていた（Diamondstone et al.:2010:135）。シェイファーはこの証明が実際には[[超低_(計算可能性理論)|超低次数]]の元の存在を示していることを指摘した。この意味で強化された主張は'''超低基底定理'''と呼ばれる。

<math>\Pi^{0}_{1}</math>クラスは木の概念と密接に関係している。<math>\Pi^{0}_{1}</math>クラスに関する定理はしばしば木に関する定理として定式化される。低基底定理は「任意の計算可能な無限二分木は低次数の無限枝を持つ」ことを述べている。

== 歴史 ==
1936年、[[デネス・ケーニヒ]]は局所有限な無限グラフは無限道を持つことを示した。これは[[ケーニヒの補題]]として知られている。系として有限分岐な無限木は無限枝を持つことが従う。これもケーニヒの補題と呼ばれる。これよりも弱い主張「任意の無限二分木は無限枝を持つ」は[[弱ケーニヒの補題]]と呼ばれる。これらの定理の証明には[[選択公理]]（より正確には[[従属選択公理]]やその弱形）が使用されており、その意味で非構成的である。（ただし、木を構成する各ノードが自然数でラベル付けられている場合、すなわち木が <math>\mathbb{N}^{< \omega}</math> の部分集合として構成されている場合には、選択公理は不要である。）また、無限枝を再帰的に延長していく際に、「子ノードの中で無限部分木になっている側を選ぶ」という操作が必要となるが、この無限性の判定は非実効的である。

[[スティーヴン・コール・クリーネ]]は弱ケーニヒの補題の計算可能バージョンが成立しないことを証明した（Kleene 1952）。すなわち、計算可能な無限二分木であって、計算可能な無限枝を持たないものを構成した。ここで構成されている木はクリーネ・ツリーと呼ばれることがある。クリーネ・ツリーの構成は[[再帰的分離不能対]]の存在と密接に関係している。互いに素な<math>\Sigma^0_1</math>集合の対が与えられると、そこからうまく無限木（クリーネ・ツリー）を構成することで、その任意の無限枝が所与の集合の対を分離するようにできる。したがって、再帰的分離不能対をもとにクリーネ・ツリーを構成すれば、その任意の無限枝は非再帰的（計算不能）でなければならない。

[[ゲオルク・クライゼル]]は計算可能な無限二分木は <math>0'</math>-計算可能（したがって[[極限計算可能関数|極限計算可能]]）な無限枝を持つことを示した（Kreisel 1953）。この定理を利用して[[ジョゼフ・ロバート・シェーンフィールド]]は計算可能な無限二分木は <math>0'</math> よりも真に小さい次数の無限枝を持つことを示した(Shoenfield 1960)。

ショカシュとソーアは計算可能な無限二分木は低次数の無限枝を持つことを示した(Jockusch and Soare: 1972)。この結果が低基底定理と呼ばれるもので、上記の諸結果を精緻化するものである。

== 証明 ==
<math>\mathbb{P}</math> を計算可能な無限二分木の全体を包含関係で並べたものとする。これをショカシュとソーアの強制概念（JS forcing notion）という。いま <math>T</math> を再帰的な無限二分木とする。<math>\mathbb{P}</math> の減少列 <math>T_e</math> を次のように再帰的に定義する：
* <math>T_0 = T</math>、
* <math>T_{e+1} = T_e</math>（<math>T_e \cap U_e</math> が有限なとき）、<math>T_{e+1} = T_e \cap U_e </math>（<math>T_e \cap U_e</math> が無限なとき）、ただし <math>U_e = \{ \sigma \mid \{e\}^{\sigma}_{|\sigma|}(e) \uparrow \}</math> である。
この列は <math>0'</math>-計算可能である。弱ケーニヒの補題より <math>[T_e]</math>（<math>T_e</math> の無限枝の全体）は空でない。<math>[T_e]</math> は[[カントール空間]] <math>2^{\omega}</math> の閉集合であり、<math>2^\omega</math> はコンパクトだから、<math>\bigcap_{e \in \mathbb{N}}[T_e]</math> は空でない。<math>\bigcap_{e \in \mathbb{N}}[T_e]</math> の任意の元は <math>T</math> の無限枝であって低次数を持つ。

== 形式的理論の次数との関係 ==

これらの諸定理は形式的理論の計算可能性と密接に関係している。任意の無矛盾理論 <math>T</math> はヘンキン構成の類似によって無矛盾かつ完全な理論に拡大することができる。それにはまず閉論理式の全体を <math>\varphi_{0},\varphi_{1},\ldots</math> と並べる。<math>T</math> にこれらの閉論理式の肯定形または否定形を付け加えることによって無矛盾完全なものに拡大する。有限な拡大の仕方は幾つもあるので、それらひとつひとつの拡大に対して <math>2^{<\omega}</math> の元を対応させる。その対応は <math>n</math>番目の閉論理式の肯定形と否定形のどちらを付け加えたかによって <math>n</math> 項目の値を <math>0</math> または <math>1</math> にすることで与えられる。このとき <math>T</math> の無矛盾拡大に対応する <math>2^{<\omega}</math> の元の全体は無限二分木を成す。もし無矛盾拡大の木が次数 <math>a</math> の無限枝を持てば、それを用いて <math>T</math> の無矛盾拡大で次数 <math>a</math> のものが得られる。

<math>T</math> が計算可能であったとしても、対応する無矛盾拡大の木が計算可能とは限らないので、基底定理を使用できない。そこで無矛盾拡大の木を次のような木に置き換える。<math>2^{<\omega}</math> の元 <math>\sigma</math> は、<math>T</math> を <math>\sigma</math> で拡大した理論から複雑さ（例：証明図のゲーデル数） <math>|\sigma|</math> 未満で矛盾に至ることがないならば、その木に属すものとする。このように定義された木は計算可能であるから基底定理が使用できる。

低基底定理を上記の木に適用することで <math>T</math> の無矛盾完全拡大で低次数を持つものが構成できる。

== 参考文献 ==
* {{cite book | first=Douglas | last=Cenzer | chapter=<math>\Pi^0_1</math> classes in computability theory | title=Handbook of computability theory | series=Stud. Logic Found. Math. | volume=140 | publisher=North-Holland | year=1999 | pages=37–85 | mr=1720779 | zbl=0939.03047 | editor-last=Griffor | editor-first=Edward R. | isbn=0-444-89882-4 }} Theorem 3.6, [https://books.google.com/books?id=KqeXZ4pPd5QC&pg=PA54 p.&nbsp;54]. 
* {{cite book|author = Cooper, S. Barry| authorlink= S. Barry Cooper | year = 2004 | title = Computability Theory | publisher = Chapman and Hall/CRC | isbn = 1-58488-237-9}}.
* {{cite journal | first1=Carl G., Jr. | last1=Jockusch | first2=Robert I. | last2=Soare | title=&Pi;(0, 1) Classes and Degrees of Theories | journal=Transactions of the American Mathematical Society | year=1972 | jstor=1996261 | zbl=0262.02041 | volume=173 | pages=33–56 | issn=0002-9947 | doi=10.1090/s0002-9947-1972-0316227-0}} The original publication, including additional clarifying prose. 
* {{cite book | last=Nies | first=André | title=Computability and randomness | series=Oxford Logic Guides | volume=51 | location=Oxford | publisher=Oxford University Press | year=2009 | isbn=978-0-19-923076-1 | zbl=1169.03034 }} Theorem 1.8.37.
*  {{cite book | first=Robert I. | last=Soare | title=Recursively enumerable sets and degrees. A study of computable functions and computably generated sets | series=Perspectives in Mathematical Logic | publisher=[[Springer-Verlag]] | location=Berlin | year=1987 | isbn=3-540-15299-7 | zbl=0667.03030 }} 
* {{cite journal | first1=David E. | last1=Diamondstone | first2=Damir D. | last2=Dzhafarov | first3=Robert I. | last3=Soare | title=<math>\Pi^{0}_{1}</math> Classes, Peano Arithmetic, Randomness, and Computable Domination | journal=Notre Dame Journal of Formal Logic | volume=51 | issue=1 | pages=127-159 | year=2010}}

{{デフォルトソート:ていきていていり}}
[[Category:計算可能性理論]]
[[Category:数学に関する記事]]

{{Mathlogic-stub}}