波斯纳–罗宾逊定理

波斯纳–罗宾逊定理(英语:Posner–Robinson Theorem)是可计算性理论中关于不可解度的定理。

定理

编辑

  不可计算,则存在集合   [1]

证明

编辑

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

为了构造  ,我们给出一对序列  ,其中:

  •  
  •  

该序列满足以下条件,若   则有:

  1.   
  2.   
  3.    

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

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

根据以上描述的序列,显然   满足  ,故定理得证。这一证明方式叫做隈部日语隈部正博斯莱曼英语Theodore Slaman力迫法。[2]

定理

编辑

参考资料

编辑
  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) (英语).