分類
悖論 邏輯

漿果悖論

貝里悖論是一種自我指稱的悖論,它是由諸如“無法在60個字母以下定義的最小正整數”(一個包含57個字母的短語)之類的表達式引起的。 貝特朗·羅素(Bertrand Russell)是第一個討論印刷版悖論的人,將其歸因於牛津Bodleian圖書館的初級圖書管理員GG Berry(1867–1928)。

總覽
考慮以下表達式:
“不可在60個字母以下定義的最小正整數。”

由於英語字母表中只有26個字母,因此有限地存在少於60個字母的短語,因此也有有限的許多正整數,由少於60個字母的短語定義。 由於存在無限多個正整數,所以這意味著存在不能用少於60個字母的短語定義的正整數。 如果存在滿足給定屬性的正整數,則存在一個滿足該屬性的最小正整數; 因此,存在一個最小的正整數,滿足屬性“不能在60個字母以下定義”。 這是上面表達式所指的整數。 但是上面的表達式只有57個字母長,因此可以在60個字母以內定義,並且不是不能在60個字母以內定義的最小正整數,因此不由該表達式定義。 這是一個悖論:此表達式必須定義一個整數,但是由於該表達式是自相矛盾的(它定義的任何整數都可以用少於60個字母定義),因此不能定義任何整數。

也許與貝瑞悖論的另一個有用比喻是“難以形容的感覺”。 如果感覺確實難以言喻,那麼對這種感覺的描述就不會是真的。 但是,如果“難以形容”一詞傳達了某種關於感覺的信息,那麼它可能被認為是一種描述:這是自相矛盾的。

數學家和計算機科學家Gregory J. Chaitin在《未知》(1999)中添加了以下評論:“好吧,墨西哥數學史學家亞歷杭德羅·加西迪哥(Alejandro Garcidiego)費勁地找到了[貝里(Russell)致辭的那封信),一個不同的悖論。 貝里的信實際上談到的是第一個序號,它不能用有限的單詞來命名。 根據Cantor的理論,這樣的序數必須存在,但是我們只是用有限數量的單詞來命名它,這是一個矛盾。”

說明
自然數可以用以下語句來描述(用法語):“十冪一百”或“二十世紀已知的最大質數”。 因此,“用十五個或更少的單詞表示可描述的整個自然數”的集合是有限的; 因此在此集合之外肯定會有許多整數。 因此,它們中最小的是“不能用十五個或更少的單詞表示的最小自然整數”。 但恰恰是,這條描述得很完美的陳述只包含15個字。

我們也可以建議創建新單詞,但是如果我們限製字母的數量,它們就不是無限數量的:用單詞(而不是單詞)的限制來重寫措辭就可以繞開該論點。

這個悖論與理查德的悖論非常接近(有時也用這個名字來稱呼),可以將其視為有限變體。 龐加萊想了解邏輯悖論在不安全處理無限時的原因,他說,關於貝里悖論只使用有限的概念,“他們(某些邏輯學家)自己趨向於陷落樂趣的陷阱,甚至他們也必須非常小心,不要跌落到陷阱旁邊”。

我們還可以認為,它與某些形式的說謊者悖論(涉及自欺欺人的句子)所涉及的問題類型相同。 通常可以通過形式化語言(在這裡可以描述整數)並將其與標有Berry句子的元語言區別開來解決,因為Berry句子不再是自相矛盾的(另請參閱有關Richard悖論的文章,以及以證明Kolmogorov的複雜性不可計算的形式翻譯此悖論(參考)。

解析度
由於“可定義”一詞在系統上含糊不清,因此出現了上述Berry悖論。 在有關Berry悖論的其他表述中,例如改為:“……用更少的名字無法命名……”,“可命名”一詞也具有這種系統的模糊性。 這種說法會引起惡性循環謬誤。 具有此類歧義的其他術語包括:可滿足,正確,錯誤,函數,屬性,類,關係,基數和順序。 要解決這些悖論之一,就必須準確查明我們使用語言的地方出了問題,並規定了可以避免使用的語言使用限制。

可以通過合併語言中的意義分層來解決這一悖論。 具有系統歧義的術語可以用下標寫成,表示在解釋中,一個意義級別被認為比另一個意義級別更高。 在此方案下,“不能少於11個單詞的數字不能命名為0”可以少於11個單詞的名稱命名為1。

正式類似物
使用程序或有界長度的證明,有可能像格雷戈里·柴廷(Gregory Chaitin)所做的那樣,用正式的數學語言構造貝瑞表達式的類似物。 儘管形式類似物不會導致邏輯上的矛盾,但它確實證明了某些不可能的結果。

喬治·布洛斯(George Boolos,1989)建立在貝里悖論的形式化版本上,以一種新穎且簡單得多的方式證明了哥德爾的不完全性定理。 他的證明的基本思想是,當且僅當x = n代表某個自然數n時,擁有x的命題可以稱為n的定義,並且集合{(n,k):n的定義為可以表示是可表示的(使用Gödel編號)。 然後,可以將命題“ m是無法在少於k個符號中定義的第一個數字”定為正則,並表明它是一個定義。

與Kolmogorov複雜性的關係
通常,不能明確定義描述給定字符串所需的最小符號數(給定特定的描述機制)。 在這種情況下,術語“字符串”和“數字”可以互換使用,因為數字實際上是一串符號,例如英語單詞(例如悖論中使用的單詞“十一”),而另一方面用數字來指任何單詞,例如通過給定字典中其位置的數量或通過適當的編碼。 某些長字符串可以使用比完整表示所需的符號少的符號來精確描述,這通常是使用數據壓縮實現的。 然後,將給定字符串的複雜度定義為描述((明確)引用該字符串的完整表示形式)所需的最小長度。

Kolmogorov複雜度是使用形式語言或Turing機器定義的,這避免了給定描述導致哪個字符串產生歧義。 可以證明Kolmogorov複雜度是不可計算的。 矛盾的證明表明,如果有可能計算Kolmogorov複雜度,那麼也有可能係統地生成與此相似的悖論,即描述比所描述字符串的複雜性所暗示的要短。 就是說,貝里數的定義是自相矛盾的,因為實際上不可能計算出定義一個數需要多少個單詞,並且我們知道,由於悖論,這種計算是不可能的。