低基定理

低基定理是關於不可解度的定理。

定理

設 $A\subseteq 2^{\omega }$ 為無窮長二進制串的集合，若自然數的語言中存在遞歸公式 $\theta$，使 $X\in A$ 若且唯若 $\forall n\,\theta (n,X\vert n)$（註：$X\vert n$ 是二進制串 $X$ 的前 $n$ 位）為真，則定義 $A$ 為 $\Pi _{1}^{0}$ 類。

若將無窮長二進制串的第 $n$ 位理解成「$n$ 是否屬於該集合」，則 $2^{\omega }$ 自然對應了自然數集合的子集集合 ${\mathcal {P}}(\mathbb {N} )$。因此 $2^{\omega }$ 上可以引入不可解度的關係 $\leq _{T}$。

低基定理表明，若 $A$ 是一個 $\Pi _{1}^{0}$ 類，則存在 $G\in A$ 使得 $G^{\prime }\leq _{T}0^{\prime }$（換句話說，$G$ 是一個低不可解度）。稱 $G$ 為 $A$ 的低基。

參考資料

• Cenzer, Douglas. $\Pi _{1}^{0}$ classes in computability theory. Griffor, Edward R. (編). Handbook of computability theory. Stud. Logic Found. Math. 140. North-Holland. 1999: 37–85. ISBN 0-444-89882-4. MR 1720779. Zbl 0939.03047 （英語）. 
• Jockusch, Carl G., jr; Soare, Robert I. Π(0, 1) Classes and Degrees of Theories. Transactions of the American Mathematical Society. 1972, 173: 33–56. ISSN 0002-9947. JSTOR 1996261. Zbl 0262.02041 （英語）. 
• Nies, André. Computability and randomness. Oxford Logic Guides 51. Oxford: Oxford University Press. 2009. ISBN 978-0-19-923076-1. Zbl 1169.03034 （英語）. 
• Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. 2004. ISBN 9780387152998 （英語）.