波斯纳–罗宾逊定理

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

 定理 
设  不可计算，则存在集合  令 。

 证明 
这一定理证明如下：令 ，则  可以看作是一个函数 ，具体定义为  当且仅当存在  使 。
然而  的每一个元素都可以用自然数编码，因此  本身也是  的元素，因此可以求出其图灵跳跃。显然  可以从  计算得出，因此假若存在  使得 ，则 。因此证明过程只需给出构造  的方法。

为了构造 ，我们给出一对序列 ，其中：




该序列满足以下条件，若  则有：

  且 
 若  则 
 若  且  则 

首先令 ，其后对任何  如下构造 ：令  为编号为  的  公式（详见算数阶层）。为了让 ，我们需要让  当且仅当 。这是一个自引用的定义：我们需要在  中加入  枝上的元素以表达  为真或为假，但是若  需要为假，则加入元素的过程本身却可能将其变为真，这便是需要  以控制之后可能加入的元素的原因。考虑以下两种情况：

 若存在  满足条件3，且在  上不变（即满足条件2），则令 、（ 是满足条件3的足够大的自然数）。
 若不存在如上所述的集合 ，则对任何满足条件3的集合  均有  使 。定义类  如下：
 当且仅当存在满足条件3的集合 ，使若存在  使公式  得以满足，则存在  使 。
 显然 。注意观察  的定义：这里只有  上的全称量词是无界量词，所以  是  类。因此，根据锥不相交定理，存在  使 ，也即 。因此只需令 、。

根据以上描述的序列，显然  满足 ，故定理得证。这一证明方式叫做–力迫法。

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

 参考资料 

Category:递归论
Category:数学定理