# 波斯纳–罗宾逊定理

## 定理

${\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） （英语）.