低基底定理
計算可能性理論における低基底定理(英: low basis theorem)は 2 ω {\displaystyle 2^{\omega }} の任意の空でない Π 1 0 {\displaystyle \Pi _{1}^{0}} クラス(算術的階層を見よ)は低次数の元を含むことを示す(Soare 1987:109)もので、1972年にカール・ショカシュとロバート・アーヴィング・ソーアによって証明せられた(Nies 2009:57)。Cenzer (1993:53) はこれを"もしかすると Π 1 0 {\displaystyle \Pi _{1}^{0}} クラスの理論において最も引用されている結果"と記している。
この定理の証明には Π 1 0 {\displaystyle \Pi _{1}^{0}} クラスによる強制法が用いられている(Cooper 2004:330)。未出版の元々の証明では 0 ′ {\displaystyle 0'} -構成が用いられていた(Diamondstone et al.:2010:135)。シェイファーはこの証明が実際には超低次数の元の存在を示していることを指摘した。この意味で強化された主張は超低基底定理と呼ばれる。
Π 1 0 {\displaystyle \Pi _{1}^{0}} クラスは木の概念と密接に関係している。 Π 1 0 {\displaystyle \Pi _{1}^{0}} クラスに関する定理はしばしば木に関する定理として定式化される。低基底定理は「任意の計算可能な無限二分木は低次数の無限枝を持つ」ことを述べている。
P {\displaystyle \mathbb {P} } を計算可能な無限二分木の全体を包含関係で並べたものとする。これをショカシュとソーアの強制概念(JS forcing notion)という。いま T {\displaystyle T} を再帰的な無限二分木とする。 P {\displaystyle \mathbb {P} } の減少列 T e {\displaystyle T_{e}} を次のように再帰的に定義する:
T 0 = T {\displaystyle T_{0}=T} 、
T e + 1 = T e {\displaystyle T_{e+1}=T_{e}} ( T e ∩ U e {\displaystyle T_{e}\cap U_{e}} が有限なとき)、 T e + 1 = T e ∩ U e {\displaystyle T_{e+1}=T_{e}\cap U_{e}} ( T e ∩ U e {\displaystyle T_{e}\cap U_{e}} が無限なとき)、ただし U e = { σ ∣ { e } | σ | σ ( e ) ↑ } {\displaystyle U_{e}=\{\sigma \mid \{e\}_{|\sigma |}^{\sigma }(e)\uparrow \}} である。
これらの諸定理は形式的理論の計算可能性と密接に関係している。任意の無矛盾理論 T {\displaystyle T} はヘンキン構成の類似によって無矛盾かつ完全な理論に拡大することができる。それにはまず閉論理式の全体を φ 0 , φ 1 , ... {\displaystyle \varphi _{0},\varphi _{1},\ldots } と並べる。 T {\displaystyle T} にこれらの閉論理式の肯定形または否定形を付け加えることによって無矛盾完全なものに拡大する。有限な拡大の仕方は幾つもあるので、それらひとつひとつの拡大に対して 2 < ω {\displaystyle 2^{<\omega }} の元を対応させる。その対応は n {\displaystyle n} 番目の閉論理式の肯定形と否定形のどちらを付け加えたかによって n {\displaystyle n} 項目の値を 0 {\displaystyle 0} または 1 {\displaystyle 1} にすることで与えられる。このとき T {\displaystyle T} の無矛盾拡大に対応する 2 < ω {\displaystyle 2^{<\omega }} の元の全体は無限二分木を成す。