波斯納–羅賓遜定理

波斯納–羅賓遜定理（英語：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 }$，故定理得證。這一證明方式叫做隈部–斯萊曼力迫法。

定理

• 波斯特定理
• 克萊尼–波斯特定理
• 弗里德堡–穆奇尼克定理
• 波斯納–羅賓遜定理
• 跳躍逆轉定理