波斯纳–罗宾逊定理

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

定理

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

证明

这一定理证明如下：令 $\Phi _{G}\subseteq \omega \times \{0,1\}\times 2^{<\omega }$，则 $\Phi _{G}$ 可以看作是一个函数 $2^{\omega }\to 2^{\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\geq _{T}\Phi _{G}^{\prime }$。因此证明过程只需给出构造 $\Phi _{G}$ 的方法。

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

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

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

1. $\Phi _{p}\subseteq \Phi _{q}$ 且 ${\bar {X}}_{p}\subseteq {\bar {X}}_{q}$
2. 若 $X\in {\bar {X}}_{p}$ 则 $\Phi _{q}(X)=\Phi _{p}(X)$
3. 若 $(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 _{1}^{0}$ 公式（详见算数阶层）。为了让 $\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)\neq \Phi (X)$。定义类 ${\mathcal {Z}}$ 如下：

${\bar {Z}}\in {\mathcal {Z}}$ 当且仅当存在满足条件3的集合 $\Psi \supseteq \Phi$，使若存在 $n<\vert \Psi \vert$ 使公式 $\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 _{1}^{0}$ 类。因此，根据锥不相交定理，存在 ${\bar {Z}}\in {\mathcal {Z}}$ 使 ${\bar {Z}}\not \geq _{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 }$，故定理得证。这一证明方式叫做隈部–斯莱曼力迫法。

定理

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