波斯納–羅賓遜定理

波斯納–羅賓遜定理(英語: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) (英語).