波斯纳–罗宾逊定理（英语：Posner–Robinson Theorem）是可计算性理论中关于不可解度的定理。

定理

设 ${\displaystyle B\subseteq \mathbb {N} }$ 不可计算，则存在集合 ${\displaystyle G}$ 令 ${\displaystyle G\oplus B\geq _{T}G^{\prime ))$。^[1]

证明

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

为了构造 ${\displaystyle \Phi _{G))$，我们给出一对序列 ${\displaystyle (\Phi _{p},{\bar {X))_{p})_{p\in \omega ))$，其中：

• ${\displaystyle \Phi _{p}\subseteq \omega \times \{0,1\}\times 2^{<\omega ))$
• ${\displaystyle {\bar {X))_{p}\subseteq 2^{\omega ))$

该序列满足以下条件，若 ${\displaystyle q>p}$ 则有：

1. ${\displaystyle \Phi _{p}\subseteq \Phi _{q))$ 且 ${\displaystyle {\bar {X))_{p}\subseteq {\bar {X))_{q))$
2. 若 ${\displaystyle X\in {\bar {X))_{p))$ 则 ${\displaystyle \Phi _{q}(X)=\Phi _{p}(X)}$
3. 若 ${\displaystyle (x_{p},y_{p},\eta )\in \Phi _{q}\backslash \Phi _{p))$ 且 ${\displaystyle (x_{q},y_{q},\sigma )\in \Phi _{p))$ 则 ${\displaystyle \vert \eta \vert >\vert \sigma \vert }$

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

• 若存在 ${\displaystyle \Psi \supseteq \Phi }$ 满足条件3，且在 ${\displaystyle {\bar {X))_{p}\cup \{B\))$ 上不变（即满足条件2），则令 ${\displaystyle \Phi _{p+1}:=\Psi \cup \{(p,1,B\vert n)\))$、${\displaystyle {\bar {X))_{p+1}:={\bar {X))_{p))$（${\displaystyle n}$ 是满足条件3的足够大的自然数）。

• 若不存在如上所述的集合 ${\displaystyle \Psi }$，则对任何满足条件3的集合 ${\displaystyle \Psi \supseteq \Phi }$ 均有 ${\displaystyle X\in {\bar {X))_{p}\cup \{B\))$ 使 ${\displaystyle \Psi (X)\neq \Phi (X)}$。定义类 ${\displaystyle {\mathcal {Z))}$ 如下：

${\displaystyle {\bar {Z))\in {\mathcal {Z))}$ 当且仅当存在满足条件3的集合 ${\displaystyle \Psi \supseteq \Phi }$，使若存在 ${\displaystyle n<\vert \Psi \vert }$ 使公式 ${\displaystyle \theta _{p}(n,\Psi \vert n)}$ 得以满足，则存在 ${\displaystyle (a,b,X)\in \Psi \backslash \Phi }$ 使 ${\displaystyle X\in {\bar {Z))}$。

显然 ${\displaystyle {\bar {X))_{p}\cup \{B\}\in {\mathcal {Z))}$。注意观察 ${\displaystyle {\mathcal {Z))}$ 的定义：这里只有 ${\displaystyle \Psi }$ 上的全称量词是无界量词，所以 ${\displaystyle {\mathcal {Z))}$ 是 ${\displaystyle \Pi _{1}^{0))$ 类。因此，根据锥不相交定理，存在 ${\displaystyle {\bar {Z))\in {\mathcal {Z))}$ 使 ${\displaystyle {\bar {Z))\not \geq _{T}B}$，也即 ${\displaystyle B\not \in {\bar {Z))}$。因此只需令 ${\displaystyle \Phi _{p+1}:=\Phi _{p}\cup \{(p,0,B\vert n)\))$、${\displaystyle {\bar {X))_{p+1}:={\bar {X))_{p}\cup {\bar {Z))}$。

根据以上描述的序列，显然 ${\displaystyle \Phi _{G}:=\bigcup _{i\in \omega }\Phi _{i))$ 满足 ${\displaystyle \Phi _{G}(B)=\Phi _{G}^{\prime ))$，故定理得证。这一证明方式叫做隈部（日语：隈部正博）–斯莱曼（英语：Theodore Slaman）力迫法。^[2]

定理

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

参考资料