分類
悖論 邏輯

克萊恩-羅瑟悖論

在數學中,Kleene-Rosser悖論是一個悖論,它表明某些形式邏輯系統是不一致的,特別是1930年引入的Curry組合邏輯版本和1932-1933年引入的Church原始lambda演算版本,兩者原本旨在形式邏輯系統。悖論由斯蒂芬·克萊恩(Stephen Kleene)和JB·羅瑟(JB Rosser)於1935年展出。

悖論
Kleene和Rosser能夠證明這兩個系統都能夠表徵和枚舉其可證明的總體,可定義的數論函數,這使他們能夠構建一個詞,該詞實質上以正式語言複製理查德悖論。

後來,咖哩設法確定了結石的關鍵成分,從而使這一悖論得以構建,並用它來構建一個更簡單的悖論,現在稱為咖哩悖論。

1935年,Kleene和Rosser發表了一個證明,即某種形式邏輯體係是不一致的,在某種意義上,可以用其符號表示的每個公式也都可以證明。碰巧的是,文獻中只有兩個適用這種不一致證明的系統。也就是1932-1933年的教堂系統,以及我在1934年所稱的八系統。但是,儘管應用範圍有限,但Kleene和Rosser的觀點仍然代表著一個定理,對於指導未來的研究非常重要。它是與Löwenheim,Skolem和Godel的著名不完全性定理相同的一般性定理,它們在最近的數學基礎研究中發揮了重要作用。

Kleene和Rosser的證明冗長而復雜,並包含一些複雜性,這些複雜性往往使它們定理的本質含義難以理解。因此,人們對使這個悖論更容易理解,並以一種使這種基本含義更加清晰地突出的方式提出來的問題產生了興趣。這就是本文試圖做的。從所指出的觀點來看,這裡提出的悖論是通過一種方法而得出的,該方法與原始發現者相比具有許多優點。

在我們進行詳細討論之前,最好先以模糊的初步方式檢查這一悖論,並以直觀的方式解釋其衍生的中心思想。

數學家為建立正式系統而努力的目標之一就是完整性-我所說的不是技術意義上的完整性,而僅僅是系統出於某種目的或其他目的的充分性。

有兩種這樣的完整性特別值得關注:它們都是形式邏輯數學系統的理想特性。這些組合完整性和演繹完整性。它們可以大致解釋如下。當且僅當由系統項和輔助不確定或變量x構成的每個表達式A都可以在系統內表示為x的函數時(即,我們可以在系統中形成其函數任何自變量的值都與將該自變量替換為W中的x的結果相同)。如果只要我們能夠在另一個命題A成立的假設上推導一個命題B,那麼我們就可以在沒有假設的情況下推導一個表達該推論的第三個命題(例如A ^ B),那麼一個理論就已經完備。因此,組合完整性是與系統中術語(或公式)的可能構造有關的屬性;演繹完整性與可能的推導有關。演繹完整性是某些系統的眾所周知的屬性。而組合完整性只是在最近幾年才實現。

Kleene-Rosser定理的實質是表明這兩種完整性是不相容的,即,擁有這兩種完整性的任何系統都是不一致的。該論點本質上是對理查德悖論的改進。它表明,實際上,理查德悖論可以在系統內正式設置。

為了初步了解這一點,讓我們如下設置理查德悖論。在任何形式的算術系統中,自然數的可定義數字函數的數量都是可枚舉的;讓他們依次列舉

除了從直觀的角度來解釋這一悖論之外,讓我們考慮一下在既組合又演繹完備的系統的情況下會發生什麼。在這樣的系統中,如果一個函數是一個數值函數,即,如果它為所有數值參數提供數值(u),那麼該事實的形式陳述就可以在系統中得到證明,因為它是演繹完備的。借助於所有定理的遞歸枚舉,然後可以按順序有效地枚舉所有數值函數的集合。由於理論是組合完整的,因此我們可以在系統內定義功能 這顯然是一個數值函數,對此事實的證明將有效地告訴我們n的值,從而肯定會出現上述矛盾。

這粗略地顯示了悖論的性質。在我們進行正式發展之前,我將就當前證據及其與克萊因和羅瑟的關係的關係作一些評論。

在對丘奇和他的學生的調查中,假定的組合完整性被削弱了,因為它要求A實際包含x-從而不需要一種將常數表示為函數的裝置。演繹完整性的得分也有所下降。如Kleene和Rosser所表明的,這些並發症無法避免矛盾。但是它們的確增加了推導的長度和復雜性。如果目標是揭露悖論的中樞神經,則邏輯方法是對更簡單的情況進行證明,即從強烈意義上考慮組合(和演繹)完整性的證明,然後說明對為更複雜的情況進行證明。