分類
悖論 邏輯

庫裡的悖論

庫裡的悖論是一種悖論,其中僅從句子C的存在就證明了任意主張F,而句子C本身說“如果C,則F”,只需要一些顯然無害的邏輯推導規則。 由於F是任意的,因此具有這些規則的任何邏輯都可以證明一切。 悖論可以用自然語言和各種邏輯表達,包括集合論,lambda微積分和組合邏輯的某些形式。

悖論以邏輯學家Haskell Curry命名。 由於它與洛伯定理的關係,它在馬丁·雨果·洛伯之後也被稱為洛伯悖論。

用自然語言
“如果是A,則是B”形式的聲明稱為有條件聲明。 庫裡悖論使用了一種特殊的自我指稱條件句,如以下示例所示:

如果這句話是正確的,那麼德國與中國接壤。

儘管德國沒有與中國接壤,但例句肯定是自然語言的句子,因此可以分析該句子的真實性。 悖論來自於此分析。 分析包括兩個步驟。

首先,可以使用常見的自然語言證明技術來證明例句是正確的。

其次,例句的真實性可以用來證明德國與中國接壤。 因為德國不與中國接壤,所以這表明其中一個證據有誤。

“德國與中國接壤”的主張可以用任何其他主張代替,並且該判決仍然可以證明。 因此,每個句子似乎都是可以證明的。 由於證明僅使用公認的推論方法,並且由於這些方法似乎都不正確,因此這種情況是自相矛盾的。

非正式證明
證明條件句子(句子形式為“如果A,那麼B”的標準方法)的標準方法稱為“條件證明”。 在該方法中,為了證明“如果A,則B”,首先假設A,然後在該假設下B被證明是正確的。

為了產生上述兩個步驟中描述的庫裡悖論,請將此方法應用於句子“如果該句子為真,則德國與中國接壤”。 這裡的A,“這句話是正確的”,是指整個句子,而B是“德國與中國接壤”。 因此,假設A與假設“如果A,則B”相同。 因此,在假設A中,我們同時假設了A和“如果A,則B”。 因此,根據慣用法,B是正確的,並且我們已經證明“如果這句話是正確的,那麼“德國與中國接壤”就是正確的。” 通常,通過假設和推論得出結論。

現在,由於我們已經證明“如果這句話是正確的,那麼’德國毗鄰中國’是正確的”,那麼我們就可以再次採用慣用語,因為我們知道“這句話是正確的”主張是正確的。 這樣,我們可以推斷出德國與中國接壤。

正式證明

句子邏輯
上一節中的示例使用了非形式化的自然語言推理。 庫裡悖論也出現在形式邏輯的某些變體中。 在這種情況下,它表明如果我們假設存在一個形式句子(X→Y),其中X本身等於(X→Y),那麼我們可以用形式證明來證明Y。 這種形式證明的一個例子如下。 有關本節中使用的邏輯符號的說明,請參閱邏輯符號列表。

X:=(X→Y)
假設,起點,等同於“如果此句子為真,則為Y”

X→X
身份定律

X→(X→Y)
因為X等於X→Y等於1,所以用2代替右邊

X→Y
從3起收縮

X
用1代替4

ÿ
從5和4通過modus ponens

另一種證明是通過皮爾斯定律。 如果X = X→Y,則(X→Y)→X。這與皮爾斯定律((X→Y)→X)→X和慣性法一起意味著X,然後是Y(如上述證明)。

因此,如果Y在形式系統中是不可證明的陳述,則該系統中沒有陳述X使得X等於蘊涵(X→Y)。 相比之下,上一節顯示了在自然(非形式化)語言中,對於每個自然語言陳述Y,都有一個自然語言陳述Z,使得Z等於自然語言中的(Z→Y)。 即,Z為“如果該句子為真,則為Y”。

在已知Y的分類的特定情況下,只需很少的步驟即可揭示矛盾之處。 例如,當Y為“德國與中國接壤”時,已知Y為假。

X =(X→Y)
假設

X =(X→假)
替代Y的已知值

X =(¬X∨錯誤)
意義

X =¬X
身份

天真的集合論
即使基本的數學邏輯不接受任何自我指稱的句子,某些形式的天真集理論仍然容易受到庫裡悖論的影響。 在允許無限制理解的集合理論中,我們仍然可以通過檢查集合來證明任何邏輯陳述Y

X = def {x ∣ x∈x→Y}。
假設ε優先於→和both,則證明按如下方式進行:

X = {x ∣ x∈x→Y}
X的定義

x = X→(x∈x↔X∈X)
成員相等集的替換

x = X→((x∈x→Y)↔(X∈X→Y))
在雙條件的兩側加一個結果(從2開始)

X∈X↔(X∈X→Y)
固結定律(從1和3開始)

X∈X→(X∈X→Y)
雙條件消除(從4開始)

X∈X→Y
收縮(從5起)

(X∈X→Y)→X∈X
雙條件消除(從4開始)

X∈X
方式(6和7)

ÿ
方式(8和6)

步驟4是一致集理論中唯一無效的步驟。 在Zermelo–Fraenkel集理論中,將需要一個額外的假設來說明X是一個集,這在ZF或其擴展ZFC(帶有選擇公理)中無法得到證明。

因此,在一致集合論中,對於假Y,不存在集合{x ∣ x∈x→Y}。這可以看作是羅素悖論的一種變體,但並不完全相同。 關於集合論的一些建議試圖解決羅素的悖論,不是通過限制理解規則,而是通過限制邏輯規則,以便它可以容忍所有非其自身集合的集合的矛盾性質。 像上面的證明這樣的證明的存在表明這樣的任務不是那麼簡單,因為上面證明中使用的至少一個推導規則必須被省略或限制。

λ演算
咖哩的悖論可以用無類型的Lambda演算來表達,並通過有限的最小邏輯來豐富。 為了應付lambda演算的句法限制,m表示包含兩個參數的蘊涵函數,即lambda項((m A)B)應等效於通常的中綴符號A→B。任意公式Z可以是通過定義λ函數N:=λp證明。 ((mp)Z)和X:=(YN),其中Y表示Curry的定點組合器。 然後,根據Y和N的定義,X =(NX)=((m X)Z),因此可以在演算中復制以上的句法邏輯證明:

X((m X)X)由最小邏輯公理A→A⊢((m X)((m X)Z)),因為X =((m X)Z)⊢((m X)Z)由極小邏輯⊢X的定理(A→(A→B))⊢(A→B),因為X =((m X)Z)⊢Z由模態A構成,(A→B)⊢B由X和(( m X)Z)

在簡單類型的lambda演算中,定點組合器無法鍵入,因此不被接受。

組合邏輯
庫裡悖論也可以表達為組合邏輯,其表達能力與λ演算具有同等的表達力。 任何lambda表達式都可以轉換為組合邏輯,因此在lambda微積分中對Curry悖論的實現進行翻譯就足夠了。

上述項X在組合邏輯中轉換為(rr),其中

r = S(S(K m)(SII))(KZ);
因此
(rr)=((m(rr))Z)。

討論區
Curry悖論可以用支持基本邏輯運算的任何語言來表達,這些語言還允許將自遞歸函數構造為表達式。 支持悖論建構的兩種機制是自我參照(從句子中引用“這個句子”的能力)和天真集合論中的不受限制的理解。 自然語言幾乎總是包含許多可用於構造悖論的功能,就像許多其他語言一樣。 通常,向語言添加元編程功能會添加所需的功能。 數學邏輯通常不支持顯式引用其自身的句子。 然而,哥德爾不完備性定理的核心是觀察到可以添加不同形式的自我參照。 參見哥德爾編號。

無限制理解的公理增加了在集合論中構造遞歸定義的能力。 這個公理不受現代集合論的支持。

證明的構造中使用的邏輯規則是條件證明的假設規則,收縮規則和慣用方式。 這些包含在最常見的邏輯系統中,例如一階邏輯。

一些形式邏輯的後果
在1930年代,Curry悖論和相關的Kleene-Rosser悖論在顯示基於自遞歸表達式的形式邏輯系統不一致方面起了主要作用。 這些包括lambda演算和組合邏輯的某些版本。

Curry從Kleene-Rosser悖論開始,推論核心問題可以用這個簡單的Curry悖論來表達。 他的結論可以說是說,組合邏輯和拉姆達演算不能作為演繹語言保持一致,而仍然允許遞歸。

在對有害(演繹)組合邏輯的研究中,庫裡(Curry)在1941年認識到這種悖論的含義是,它無限制地暗示了組合邏輯的以下特性是不兼容的:

組合完整性。 這意味著抽象運算符在系統中是可定義的(或原始的),這是對系統表示能力的要求。

演繹完整性。 這是對可導性的要求,即在具有實質性含義和慣用語形式的形式系統中,如果根據假設X證明Y,則也存在X→Y的證明。

術語
自然語言和數學邏輯都基於斷言某些陳述為真。 該語句可以表示為邏輯(或布爾)表達式(或公式),可以對其進行評估以得出true或false的值。 語句是一種語句或邏輯表達式,在被求值時將聲明其為真值。

也可以以更複雜的方式考慮示威。 陳述可以通過您主張或相信的陳述以及確定性的等級來限定。 但是,對於邏輯,上面給出的簡單定義就足夠了。

存在問題
這個悖論類似於,

騙子的悖論
羅素悖論
其中每個悖論都試圖給不存在的事物起一個名字。 這些悖論都試圖為方程的解給出名稱或表示,

X =¬X
請注意,悖論不是強制執行¬X語句而引起的,因為這樣的語句將是謊言。 它源於對聲明的審議和命名。 悖論是通過將¬X形式的表達式命名或表示為X來產生的。在Curry悖論的情況下,否定是由蘊涵構成的,

X = X→假=¬X∨假=¬X
布爾變量X的域是集合{true,false}。 但是,對上述方程式的解決方案都不為真或為假。 因此,宣稱X的存在一定是錯誤的,並且將¬X表達式命名為X是一個謊言。

矛盾的是,總是可以構造一個其值不存在的表達式。 這可以使用“ this statement”來實現,但是還有許多其他語言功能,這些功能允許構建不存在的表達。

表達矛盾的語言資源
可以用支持基本邏輯運算的任何語言來表達Curry的悖論,這也允許將自動遞歸函數構造為表達式。 下面的列表提供了一些支持悖論構造的機制,但是列表並不詳盡。

自我參考; “這個句子”。
通過包含名稱的表達式的命名法。
應用樸素集理論(不受限制的理解)。
Lambda表達式。
一個單詞中的一個Eval函數。

構建證據所使用的邏輯規則是:

假設規則
收縮
方式

然後可以使用自動遞歸函數來定義終止計算,該終止計算的值不是方程的解。 在庫裡悖論中,我們使用蘊涵來構造一個否定詞,該否定詞會建立一個沒有解的方程式。

然後,遞歸表達式表示一個不存在的值。 邏輯定律僅對{true,false}中的布爾值有效,因此對錶達式的任何保留都可能是錯誤的。

自然語言幾乎總是包含許多可用於構造悖論的資源,就像許多其他語言一樣。 通常,為一種語言添加元編程功能會添加必要的功能。

數學邏輯通常不容許明確引用其自身的句子。 但是,哥德爾不完備性定理的核心是觀察到可以添加自我參照。 參見哥德爾編號。

不受限制的理解公理增加了在集合論中構造遞歸定義的能力。 這個公理不受現代集合論的支持。

一些形式邏輯的後果
在1930年代,Curry悖論和相關的Kleene-Rosser悖論在表明基於自遞歸表達式的形式邏輯系統不一致方面發揮了重要作用。

λ演算
組合邏輯

Curry從Kleene-Rosser悖論開始,推論出中心問題可以用Curry的這個更簡單的悖論來表達,他的結論可以說是說組合邏輯和Lambda計算不能作為一種演繹語言連貫,允許遞歸。

在對錶示(演繹)組合邏輯的研究中,庫裡(Curry)在1941年認識到這種悖論的含義是,它無限制地暗示了組合邏輯的以下特性是不兼容的:

組合完整性。 這意味著抽象運算符在系統中是可定義的(或原始的),這是對系統表示能力的要求。
演繹完整性。 這是一個可推導性要求,即在具有內蘊和物質模態形式的形式系統中,如果從假設X可以推導Y,那麼也存在X→Y的證明。

解析度
本節未引用任何來源。 請通過在可靠來源中添加引文來幫助改進本節。 無法查證的內容可能被提出異議而移除。
查找來源:“ Curry的悖論” –新聞•報紙•書籍•學者•JSTOR(2019年8月)(了解如何以及何時刪除此模板消息)

本部分的事實準確性存在爭議。 相關討論可以在Talk:Curry的悖論上找到。 請幫助確保有爭議的陳述來源可靠。 (2019年8月)(了解如何以及何時刪除此模板消息)

請注意,與說謊者悖論或羅素悖論不同,庫裡的悖論並不取決於所使用的否定模型,因為它是完全無否定的。 因此,即使相矛盾的邏輯不受騙子悖論的影響,但仍然容易受到這種悖論的影響。

Lambda演算中沒有解析度
阿隆佐·丘奇(Alonzo Church)的lambda演算的起源可能是“如何解決方程式,以提供函數定義?”。 這是等效的,

fx = y⟺f =λxy

如果只有一個函數f滿足方程fx = y,則此定義有效,否則無效。 這是Stephen Cole Kleene和Haskell Curry通過組合邏輯和Lambda微積分發現的問題的核心。

情況可以與定義
y = x 2 x = y。

只要平方根僅允許正值,此定義就可以了。 在數學中,存在量化變量可以表示多個值,但一次只能表示一個。 存在量化是一個方程的許多實例的析取。 在每個方程式中,變量的一個值。

但是,在數學中,沒有自由變量的表達式必須只有一個值和一個值。 因此4只能表示+2。但是,沒有方便的方法將lambda抽象限制為一個值或確保有一個值。

Lambda演算可以通過傳遞與參數相同的函數來進行遞歸。 這允許fx = y對f有多個或沒有解的情況。

如果僅允許代表一個方程式的單個解的lambda抽象,則可以將Lambda微積分視為數學的一部分。 其他lambda抽像在數學上是不正確的。

咖哩的悖論和其他悖論在Lambda演算中出現,因為被認為是演繹系統的Lambda演算的不一致。 另請參見演繹λ演算。

Lambda演算領域

Lambda演算是其自身領域中的一致理論。 但是,將lambda抽象定義添加到通用數學中並不一致。 Lambda術語描述了Lambda演算域中的值。 每個lambda項在該域中都有一個值。

當將表達式從數學轉換為lambda演算時,lambda演算項的域並不總是與數學表達式的域同構。 這種同構的缺乏是明顯矛盾的根源。

不受限制的語言解析

有許多語言構造可隱式調用一個可能沒有解決方案或有很多解決方案的方程式。 解決此問題的合理方法是將這些表達式在語法上鍊接到一個存在的量化變量。 該變量以在普通人類推理中有意義的方式表示多個值,但在數學中也有效。

例如,允許Eval函數的自然語言在數學上不一致。 但是,用這種自然語言對Eval的每次調用都可以以一致的方式轉換為數學。 將Eval轉換為數學是

令x = x中的Eval。
因此,如果s =“評估→y”,

令x = x→y在x中。
如果y為假,則x = x→y為假,但這是一個謬論,而不是悖論。

變量x的存在在自然語言中是隱含的。 當自然語言翻譯成數學時,將創建變量x。 這使我們能夠在保持數學完整性的同時使用具有自然語義的自然語言。

形式邏輯解析
形式邏輯中的參數始於假設將命名(X→Y)的有效性設為X。但是,這不是有效的起點。 首先,我們必須推斷出命名的有效性。 以下定理很容易得到證明,並表示這樣的命名:

∀A,∃X,X = A.
在上面的語句中,公式A命名為X。現在嘗試用(X→Y)實例化A。但是,這是不可能的,因為∃X的範圍在∀A的範圍內。量詞的使用Skolemization可以逆轉:

∃f,∀A,f(A)=A。
但是,現在實例化給出了

f(X→Y)= X→Y,
這不是證明的出發點,不會導致矛盾。 沒有其他實例化A導致悖論的起點。

集合論中的解析

在Zermelo–Fraenkel集理論(ZFC)中,無限制理解的公理被一組允許構建集的公理代替。 因此,Curry的悖論無法在ZFC中陳述。 ZFC的發展是對Russell悖論的回應。