波斯纳–罗宾逊定理(英语:Posner–Robinson Theorem)是可计算性理论中关于不可解度的定理。
这一定理证明如下:令
,则
可以看作是一个函数
,具体定义为
当且仅当存在
使
。
然而
的每一个元素都可以用自然数编码,因此
本身也是
的元素,因此可以求出其图灵跳跃。显然
可以从
计算得出,因此假若存在
使得
,则
。因此证明过程只需给出构造
的方法。
为了构造
,我们给出一对序列
,其中:
![{\displaystyle \Phi _{p}\subseteq \omega \times \{0,1\}\times 2^{<\omega }}](//wikimedia.org/api/rest_v1/media/math/render/svg/303aeff9f52c9597b642c0da3e9d5e73d25f0f85)
![{\displaystyle {\bar {X}}_{p}\subseteq 2^{\omega }}](//wikimedia.org/api/rest_v1/media/math/render/svg/b60ca952ec8c41f3fdbe0da3df1955edd095ff8a)
该序列满足以下条件,若
则有:
且 ![{\displaystyle {\bar {X}}_{p}\subseteq {\bar {X}}_{q}}](//wikimedia.org/api/rest_v1/media/math/render/svg/a3b01c23368f582b1949f13fb0b1cc9537250cfe)
- 若
则 ![{\displaystyle \Phi _{q}(X)=\Phi _{p}(X)}](//wikimedia.org/api/rest_v1/media/math/render/svg/fdceaa046287e508b644025b071ddd943f724003)
- 若
且
则 ![{\displaystyle \vert \eta \vert >\vert \sigma \vert }](//wikimedia.org/api/rest_v1/media/math/render/svg/0523a178ba92f253a12bb70f98a826ede085e800)
首先令
,其后对任何
如下构造
:令
为编号为
的
公式(详见算数阶层)。为了让
,我们需要让
当且仅当
。这是一个自引用的定义:我们需要在
中加入
枝上的元素以表达
为真或为假,但是若
需要为假,则加入元素的过程本身却可能将其变为真,这便是需要
以控制之后可能加入的元素的原因。考虑以下两种情况:
- 若存在
满足条件3,且在
上不变(即满足条件2),则令
、
(
是满足条件3的足够大的自然数)。
- 若不存在如上所述的集合
,则对任何满足条件3的集合
均有
使
。定义类
如下:
当且仅当存在满足条件3的集合
,使若存在
使公式
得以满足,则存在
使
。
- 显然
。注意观察
的定义:这里只有
上的全称量词是无界量词,所以
是
类。因此,根据锥不相交定理,存在
使
,也即
。因此只需令
、
。
根据以上描述的序列,显然
满足
,故定理得证。这一证明方式叫做隈部–斯莱曼力迫法。[2]
Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. 2004. ISBN 9780387152998 (英语).