低基定理

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

定理
设 A\subseteq 2^\omega 为无穷长二进制串的集合，若自然数的语言中存在递归公式 \theta，使 X\in A 当且仅当 \forall n\,\theta(n,X\vert n)（注：X\vert n 是二进制串 X 的前 n 位）为真，则定义 A 为 \Pi^0_1 类。

若将无穷长二进制串的第 n 位理解成“n 是否属于该集合”，则 2^\omega 自然对应了自然数集合的子集集合 \mathcal{P}(\mathbb{N})。因此 2^\omega 上可以引入不可解度的关系 \le_T。

低基定理表明，若 A 是一个 \Pi^0_1 类，则存在 G\in A 使得 G^\prime\le_T 0^\prime（换句话说，G 是一个低不可解度）。称 G 为 A 的低基。

参考资料
*
*
*
*