波斯纳–罗宾逊定理

波斯納–羅賓遜定理（英語：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]

定理

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