波斯纳–罗宾逊定理

波斯納–羅賓遜定理（Template:Lang-en）是可计算性理论中关于不可解度的定理。

定理

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

证明

这一定理证明如下：令 ${\mathrm{\Phi }}_G\subseteq \omega \times \{0,1\}\times 2^{<\omega }$，则 ${\mathrm{\Phi }}_G$ 可以看作是一个函数 $2^{\omega }\to 2^{\omega }$，具体定义为 $a\in {\mathrm{\Phi }}_G(X)$ 当且仅当存在 $n\in \omega$ 使 $(a,1,X|n)\in {\mathrm{\Phi }}_G$。 然而 ${\mathrm{\Phi }}_G$ 的每一个元素都可以用自然数编码，因此 ${\mathrm{\Phi }}_G$ 本身也是 $2^{\omega }$ 的元素，因此可以求出其图灵跳跃。显然 ${\mathrm{\Phi }}_G(X)$ 可以从 ${\mathrm{\Phi }}_G\oplus X$ 计算得出，因此假若存在 ${\mathrm{\Phi }}_G$ 使得 ${\mathrm{\Phi }}_G(X)={\mathrm{\Phi }}_G^{\prime }$，则 ${\mathrm{\Phi }}_G\oplus X{\ge }_T{\mathrm{\Phi }}_G^{\prime }$。因此证明过程只需给出构造 ${\mathrm{\Phi }}_G$ 的方法。

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

• ${\mathrm{\Phi }}_p\subseteq \omega \times \{0,1\}\times 2^{<\omega }$
• ${\overline{X}}_p\subseteq 2^{\omega }$

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

1. ${\mathrm{\Phi }}_p\subseteq {\mathrm{\Phi }}_q$ 且 ${\overline{X}}_p\subseteq {\overline{X}}_q$
2. 若 $X\in {\overline{X}}_p$ 则 ${\mathrm{\Phi }}_q(X)={\mathrm{\Phi }}_p(X)$
3. 若 $(x_p,y_p,\eta )\in {\mathrm{\Phi }}_q\mathrm{\setminus }{\mathrm{\Phi }}_p$ 且 $(x_q,y_q,\sigma )\in {\mathrm{\Phi }}_p$ 则 $|\eta |>|\sigma |$

首先令 ${\mathrm{\Phi }}_0={\overline{X}}_0=\varnothing$，其后对任何 $({\mathrm{\Phi }}_p,{\overline{X}}_p)$ 如下构造 $({\mathrm{\Phi }}_{p+1},{\overline{X}}_{p+1})$：令 ${\varphi }_p:=\mathrm{\exists }n{\theta }_p(n,Z|n)$ 为编号为 $p$ 的 ${\mathrm{\Sigma }}_1^0$ 公式（详见算数阶层）。为了让 ${\mathrm{\Phi }}_G(B)={\mathrm{\Phi }}_G^{\prime }$，我们需要让 ${\varphi }_p\in {\mathrm{\Phi }}_G(B)$ 当且仅当 $\models \mathrm{\exists }n{\theta }_p(n,{\mathrm{\Phi }}_G|n)$。这是一个自引用的定义：我们需要在 ${\mathrm{\Phi }}_p$ 中加入 $B$ 枝上的元素以表达 ${\varphi }_p$ 为真或为假，但是若 ${\varphi }_p$ 需要为假，则加入元素的过程本身却可能将其变为真，这便是需要 ${\overline{X}}_p$ 以控制之后可能加入的元素的原因。考虑以下两种情况：

• 若存在 $\mathrm{\Psi }\supseteq \mathrm{\Phi }$ 满足条件3，且在 ${\overline{X}}_p\cup \{B\}$ 上不变（即满足条件2），则令 ${\mathrm{\Phi }}_{p+1}:=\mathrm{\Psi }\cup \{(p,1,B|n)\}$、${\overline{X}}_{p+1}:={\overline{X}}_p$（$n$ 是满足条件3的足够大的自然数）。

• 若不存在如上所述的集合 $\mathrm{\Psi }$，则对任何满足条件3的集合 $\mathrm{\Psi }\supseteq \mathrm{\Phi }$ 均有 $X\in {\overline{X}}_p\cup \{B\}$ 使 $\mathrm{\Psi }(X)\ne \mathrm{\Phi }(X)$。定义类 $𝒵$ 如下：

$\overline{Z}\in 𝒵$ 当且仅当存在满足条件3的集合 $\mathrm{\Psi }\supseteq \mathrm{\Phi }$，使若存在 $n<|\mathrm{\Psi }|$ 使公式 ${\theta }_p(n,\mathrm{\Psi }|n)$ 得以满足，则存在 $(a,b,X)\in \mathrm{\Psi }\mathrm{\setminus }\mathrm{\Phi }$ 使 $X\in \overline{Z}$。

显然 ${\overline{X}}_p\cup \{B\}\in 𝒵$。注意观察 $𝒵$ 的定义：这里只有 $\mathrm{\Psi }$ 上的全称量词是无界量词，所以 $𝒵$ 是 ${\mathrm{\Pi }}_1^0$ 类。因此，根据锥不相交定理，存在 $\overline{Z}\in 𝒵$ 使 $\overline{Z}{\ge }_{T}B$，也即 $B\in ̸\overline{Z}$。因此只需令 ${\mathrm{\Phi }}_{p+1}:={\mathrm{\Phi }}_p\cup \{(p,0,B|n)\}$、${\overline{X}}_{p+1}:={\overline{X}}_p\cup \overline{Z}$。

根据以上描述的序列，显然 ${\mathrm{\Phi }}_G:=\bigcup _{i\in \omega }{\mathrm{\Phi }}_i$ 满足 ${\mathrm{\Phi }}_G(B)={\mathrm{\Phi }}_G^{\prime }$，故定理得证。这一证明方式叫做Template:Link-ja–Template:Link-en力迫法。

定理

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