波斯納–羅賓遜定理

定理

${\displaystyle B\subseteq \mathbb {N} }$  不可計算，則存在集合 ${\displaystyle G}$ ${\displaystyle G\oplus B\geq _{T}G^{\prime }}$ [1]

證明

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

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 \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}}}$

參考資料

1. ^ Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. 2004. ISBN 9780387152998 （英語）.
2. ^ Theodore A. Slaman. Turing Degrees and Definability of the Jump (PDF). [2014-04-18]. （原始內容存檔 (PDF)於2010-07-30） （英語）.