低基底定理

ウィキペディア

低基底定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/18 02:55 UTC 版)

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