跳转到内容

波斯纳–罗宾逊定理

维基百科,自由的百科全书

波斯納–羅賓遜定理(英語:Posner–Robinson Theorem)是可计算性理论中关于不可解度的定理。

定理

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

证明

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

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

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

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

  • 若存在 满足条件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) (英语).