低基底定理

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

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

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

歴史

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

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

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

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

証明

$\mathbb {P}$ を計算可能な無限二分木の全体を包含関係で並べたものとする。これをショカシュとソーアの強制概念（JS forcing notion）という。いま $T$ を再帰的な無限二分木とする。$\mathbb {P}$ の減少列 $T_{e}$ を次のように再帰的に定義する：

• $T_{0}=T$、
• $T_{e+1}=T_{e}$（$T_{e}\cap U_{e}$ が有限なとき）、$T_{e+1}=T_{e}\cap U_{e}$（$T_{e}\cap U_{e}$ が無限なとき）、ただし $U_{e}=\{\sigma \mid \{e\}_{|\sigma |}^{\sigma }(e)\uparrow \}$ である。

この列は $0'$-計算可能である。弱ケーニヒの補題より $[T_{e}]$（$T_{e}$ の無限枝の全体）は空でない。$[T_{e}]$ はカントール空間 $2^{\omega }$ の閉集合であり、$2^{\omega }$ はコンパクトだから、$\bigcap _{e\in \mathbb {N} }[T_{e}]$ は空でない。$\bigcap _{e\in \mathbb {N} }[T_{e}]$ の任意の元は $T$ の無限枝であって低次数を持つ。

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

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

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

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

参考文献

• Cenzer, Douglas (1999). “$\Pi _{1}^{0}$ classes in computability theory”. In Griffor, Edward R.. Handbook of computability theory. Stud. Logic Found. Math.. 140. North-Holland. pp. 37–85. ISBN 0-444-89882-4. MR1720779. Zbl 0939.03047  Theorem 3.6, p. 54.
• Cooper, S. Barry (2004). Computability Theory. Chapman and Hall/CRC. ISBN 1-58488-237-9 .
• Jockusch, Carl G., Jr.; Soare, Robert I. (1972). “Π(0, 1) Classes and Degrees of Theories”. Transactions of the American Mathematical Society 173: 33–56. doi:10.1090/s0002-9947-1972-0316227-0. ISSN 0002-9947. JSTOR 1996261. Zbl 0262.02041.  The original publication, including additional clarifying prose.
• Nies, André (2009). Computability and randomness. Oxford Logic Guides. 51. Oxford: Oxford University Press. ISBN 978-0-19-923076-1. Zbl 1169.03034  Theorem 1.8.37.
• Soare, Robert I. (1987). Recursively enumerable sets and degrees. A study of computable functions and computably generated sets. Perspectives in Mathematical Logic. Berlin: Springer-Verlag. ISBN 3-540-15299-7. Zbl 0667.03030 
• Diamondstone, David E.; Dzhafarov, Damir D.; Soare, Robert I. (2010). “$\Pi _{1}^{0}$ Classes, Peano Arithmetic, Randomness, and Computable Domination”. Notre Dame Journal of Formal Logic 51 (1): 127-159.