跳至內容

波斯納–羅賓遜定理

維基百科,自由的百科全書

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