低基定理

低基定理是关于不可解度的定理。

定理

设 $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 （英语）.