波斯納–羅賓遜定理（）是可计算性理论中关于不可解度的定理。

定理
设 B\subseteq\mathbb{N} 不可计算，则存在集合 G 令 G\oplus B\ge_T G^\prime。

证明
这一定理证明如下：令 \Phi_G\subseteq \omega\times\{0,1\}\times2^{，则 \Phi_G 可以看作是一个函数 2^\omega\to2^\omega，具体定义为 a\in\Phi_G(X) 当且仅当存在 n\in\omega 使 (a,1,X|n)\in\Phi_G。
然而 \Phi_G 的每一个元素都可以用自然数编码，因此 \Phi_G 本身也是 2^\omega 的元素，因此可以求出其图灵跳跃。显然 \Phi_G(X) 可以从 \Phi_G\oplus X 计算得出，因此假若存在 \Phi_G 使得 \Phi_G(X) = \Phi_G^\prime，则 \Phi_G \oplus X \ge_T \Phi_G^\prime。因此证明过程只需给出构造 \Phi_G 的方法。

为了构造 \Phi_G，我们给出一对序列 (\Phi_p,\bar X_p)_{p\in\omega}，其中：

• \Phi_p\subseteq\omega\times\{0,1\}\times2^{
• \bar X_p\subseteq 2^\omega

该序列满足以下条件，若 q>p 则有：

\Phi_p\subseteq\Phi_q 且 \bar X_p\subseteq\bar X_q

若 X\in\bar X_p 则 \Phi_q(X)=\Phi_p(X)

若 (x_p,y_p,\eta)\in\Phi_q\backslash\Phi_p 且 (x_q,y_q,\sigma)\in\Phi_p 则 \vert\eta\vert>\vert\sigma\vert

首先令 \Phi_0=\bar X_0=\varnothing，其后对任何 (\Phi_p,\bar X_p) 如下构造 (\Phi_{p+1},\bar X_{p+1})：令 \phi_p := \exists n\,\theta_p(n,Z\vert n) 为编号为 p 的 \Sigma^0_1 公式（详见算数阶层）。为了让 \Phi_G(B)=\Phi_G^\prime，我们需要让 \phi_p\in\Phi_G(B) 当且仅当 \vDash\exists n\,\theta_p(n,\Phi_G\vert n)。这是一个自引用的定义：我们需要在 \Phi_p 中加入 B 枝上的元素以表达 \phi_p 为真或为假，但是若 \phi_p 需要为假，则加入元素的过程本身却可能将其变为真，这便是需要 \bar X_p 以控制之后可能加入的元素的原因。考虑以下两种情况：

• 若存在 \Psi\supseteq\Phi 满足条件3，且在 \bar X_p\cup\{B\} 上不变（即满足条件2），则令 \Phi_{p+1}:=\Psi\cup\{(p,1,B\vert n)\}、\bar X_{p+1}:=\bar X_p（n 是满足条件3的足够大的自然数）。
• 若不存在如上所述的集合 \Psi，则对任何满足条件3的集合 \Psi\supseteq\Phi 均有 X\in\bar X_p\cup\{B\} 使 \Psi(X)\ne\Phi(X)。定义类 \mathcal{Z} 如下：

::\bar Z\in\mathcal{Z} 当且仅当存在满足条件3的集合 \Psi\supseteq\Phi，使若存在 n 使公式 \theta_p(n,\Psi\vert n) 得以满足，则存在 (a,b,X)\in\Psi\backslash\Phi 使 X\in\bar Z。
: 显然 \bar X_p\cup\{B\}\in\mathcal{Z}。注意观察 \mathcal{Z} 的定义：这里只有 \Psi 上的全称量词是无界量词，所以 \mathcal{Z} 是 \Pi^0_1 类。因此，根据锥不相交定理，存在 \bar Z\in\mathcal{Z} 使 \bar Z\not\ge_T B，也即 B\not\in\bar Z。因此只需令 \Phi_{p+1}:=\Phi_p\cup\{(p,0,B\vert n)\}、\bar X_{p+1}:=\bar X_p\cup\bar Z。

根据以上描述的序列，显然 \Phi_G:=\bigcup_{i\in\omega}\Phi_i 满足 \Phi_G(B)=\Phi_G^\prime，故定理得证。这一证明方式叫做–力迫法。

定理

• 波斯特定理
• 克莱尼–波斯特定理
• 弗里德堡–穆奇尼克定理
• 波斯纳–罗宾逊定理
• 跳躍逆轉定理

参考资料