低基底定理

計算可能性理論における低基底定理（）は formula_1 の任意の空でないformula_2クラス（算術的階層を見よ）は低次数の元を含むことを示す（Soare 1987:109）もので、1972年にカール・ショカシュとロバート・アーヴィング・ソーアによって証明せられた（Nies 2009:57）。Cenzer (1993:53) はこれを"もしかすると formula_2 クラスの理論において最も引用されている結果"と記している。
この定理の証明には formula_2 クラスによる強制法が用いられている（Cooper 2004:330）。未出版の元々の証明では formula_5-構成が用いられていた（Diamondstone et al.:2010:135）。シェイファーはこの証明が実際には超低次数の元の存在を示していることを指摘した。この意味で強化された主張は超低基底定理と呼ばれる。
formula_6クラスは木の概念と密接に関係している。formula_6クラスに関する定理はしばしば木に関する定理として定式化される。低基底定理は「任意の計算可能な無限二分木は低次数の無限枝を持つ」ことを述べている。
歴史.
1936年、デネス・ケーニヒは局所有限な無限グラフは無限道を持つことを示した。これはケーニヒの補題として知られている。系として有限分岐な無限木は無限枝を持つことが従う。これもケーニヒの補題と呼ばれる。これよりも弱い主張「任意の無限二分木は無限枝を持つ」は弱ケーニヒの補題と呼ばれる。これらの定理の証明には選択公理（より正確には従属選択公理やその弱形）が使用されており、その意味で非構成的である。（ただし、木を構成する各ノードが自然数でラベル付けられている場合、すなわち木が formula_8 の部分集合として構成されている場合には、選択公理は不要である。）また、無限枝を再帰的に延長していく際に、「子ノードの中で無限部分木になっている側を選ぶ」という操作が必要となるが、この無限性の判定は非実効的である。
スティーヴン・コール・クリーネは弱ケーニヒの補題の計算可能バージョンが成立しないことを証明した（Kleene 1952）。すなわち、計算可能な無限二分木であって、計算可能な無限枝を持たないものを構成した。ここで構成されている木はクリーネ・ツリーと呼ばれることがある。クリーネ・ツリーの構成は再帰的分離不能対の存在と密接に関係している。互いに素なformula_9集合の対が与えられると、そこからうまく無限木（クリーネ・ツリー）を構成することで、その任意の無限枝が所与の集合の対を分離するようにできる。したがって、再帰的分離不能対をもとにクリーネ・ツリーを構成すれば、その任意の無限枝は非再帰的（計算不能）でなければならない。
ゲオルク・クライゼルは計算可能な無限二分木は formula_5-計算可能（したがって極限計算可能）な無限枝を持つことを示した（Kreisel 1953）。この定理を利用してジョゼフ・ロバート・シェーンフィールドは計算可能な無限二分木は formula_5 よりも真に小さい次数の無限枝を持つことを示した(Shoenfield 1960)。
ショカシュとソーアは計算可能な無限二分木は低次数の無限枝を持つことを示した(Jockusch and Soare: 1972)。この結果が低基底定理と呼ばれるもので、上記の諸結果を精緻化するものである。
証明.
formula_12 を計算可能な無限二分木の全体を包含関係で並べたものとする。これをショカシュとソーアの強制概念（JS forcing notion）という。いま formula_13 を再帰的な無限二分木とする。formula_12 の減少列 formula_15 を次のように再帰的に定義する：
この列は formula_5-計算可能である。弱ケーニヒの補題より formula_23（formula_15 の無限枝の全体）は空でない。formula_23 はカントール空間 formula_1 の閉集合であり、formula_27 はコンパクトだから、formula_28 は空でない。formula_28 の任意の元は formula_13 の無限枝であって低次数を持つ。
形式的理論の次数との関係.
これらの諸定理は形式的理論の計算可能性と密接に関係している。任意の無矛盾理論 formula_13 はヘンキン構成の類似によって無矛盾かつ完全な理論に拡大することができる。それにはまず閉論理式の全体を formula_32 と並べる。formula_13 にこれらの閉論理式の肯定形または否定形を付け加えることによって無矛盾完全なものに拡大する。有限な拡大の仕方は幾つもあるので、それらひとつひとつの拡大に対して formula_34 の元を対応させる。その対応は formula_35番目の閉論理式の肯定形と否定形のどちらを付け加えたかによって formula_35 項目の値を formula_37 または formula_38 にすることで与えられる。このとき formula_13 の無矛盾拡大に対応する formula_34 の元の全体は無限二分木を成す。もし無矛盾拡大の木が次数 formula_41 の無限枝を持てば、それを用いて formula_13 の無矛盾拡大で次数 formula_41 のものが得られる。
formula_13 が計算可能であったとしても、対応する無矛盾拡大の木が計算可能とは限らないので、基底定理を使用できない。そこで無矛盾拡大の木を次のような木に置き換える。formula_34 の元 formula_46 は、formula_13 を formula_46 で拡大した理論から複雑さ（例：証明図のゲーデル数） formula_49 未満で矛盾に至ることがないならば、その木に属すものとする。このように定義された木は計算可能であるから基底定理が使用できる。
低基底定理を上記の木に適用することで formula_13 の無矛盾完全拡大で低次数を持つものが構成できる。