波斯納–羅賓遜定理

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

定理

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