跳至內容

塔斯基不可定義定理

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

塔斯基不可定義定理（英語：Tarski's undefinability theorem），是由阿爾弗雷德·塔斯基在1936年給出並證明，是在數理邏輯、數學基礎及形式化語義方面的一個重要的限制結果。簡單來說：我們無法在算術系統中定義何謂「算術的真理」。從而這個定理可被推廣成適用於任何足夠強的形式系統，以表明：我們無法在系統中定義何謂「系統標準模型的真理」。

歷史

[編輯]

庫爾特·哥德爾在1931年發表了著名的哥德爾不完備定理，他一部分是透過一階算術的語義表達技巧來完成定理的證明。在他的算術語言中，每條表達式都配有各自的編碼。這個過程稱為「哥德爾編碼」，而每組表達式也可配有各自的編碼組。如此一來，各種語義屬性（例如：當成式子或當成句子）變成可計算的。我們就可透過算術式定義任何可計算的編碼組，具體而言，我們可用算術語言中的某些式子（即公理）為算術句子及可證明的算術句子定義出編碼組。

塔斯基不可定義定理則表明：我們無法按照語義的概念給式子進行恰當的編碼，例如：真理的概念。這表明：世上沒有任何直譯語言足以表達出它本身的語義。我們可推論出，元語言必須具備超越對象語言（英語：Object language）的表達能力，才可表達出對象語言的語義。元語言具有對象語言所沒有的原始概念（英語：Primitive notion）、公理及規則，使得某些定理在對象語言中不可證明，在元語言中卻可證明。

一般認為不可定義定理是由塔斯基給出的。儘管哥德爾在1930年證明不完備定理的期間也發現了不可定義定理，遠早於塔斯基的發表，但是哥德爾並未發表自己有關不可定義性的發現，僅在1931年致約翰·馮·紐曼的信中提到它。

塔斯基在1929至1931年間完成了他大部分的論文成果，並向波蘭的聽眾演說。這篇論文就是1936年發表的《形式化語言中的真理概念》（Der Wahrheitsbegriff in den formalisierten Sprachen）。然而，正如他在論文中所強調的，只有不可定義定理這一結果不是他首先發現的。根據論文中不可定義定理的註解（Satz I），這個定理及其證明的草稿是在送印前才加進論文中的。

他在1931年3月21日向波蘭科學院（Warsaw Academy of Science）進行論文演說時，僅寫下一些猜想，而沒有提到他基於自己的研究與哥德爾的簡報所完成的《元數學的完備性與相容性的一些結果》（Einige metamathematische Resultate über Entscheidungsdefinitheit und Widerspruchsfreiheit）。

專有名詞介紹

[編輯]

這個條目中包含了許多邏輯學、數學、語言學的專有名詞，且相同的概念在不同的研究領域可能有不同的名稱，故在此特別獨立出一個小節彙整本條目的專有名詞。

  • 一階算術：指一階邏輯。
  • 算術語言：指形式語言。
  • 對象語言：指被當成研究對象的語言。
  • 元語言：指用以研究對象語言的高階語言。
  • 式子：英文作well-formed formula，指符合語法規則的字串，可以具有自由變數。
  • 句子：英文作sentence，指沒有自由變數的式子。
  • L-式子或L-句子：分別指語言L中的式子或句子。
  • A↔B：讀作「A若且唯若B」，意思是：A與B要麼同時成立，不然同時不成立。可進一步理解為：A等價於B。

定理的內容

[編輯]

我們在這個小節會給出塔斯基定理的簡易版，接着在下個小節才會論及塔斯基在1936年的完整證明。

令L為一階算術語言，令N為L的標準結構。這樣，(L, N)就是「一階算術直譯語言」。L中的每個句子x都有各自的哥德爾數g(x)。令T為在N中為真的L-句子的集合，而T*為T中的句子的哥德爾數的集合。

現在的問題是：一階算術的句子可否定義出T*？

塔斯基不可定義定理的回答是：沒有任何在N中為真的L-式子定義出T*，亦即，沒有任何在N中為真的L-式子使對任何L-式子A，有：True(g(A))↔A。

簡單來說，這個定理告訴我們：我們不可透過任何形式算術本身的表達能力定義出這種形式算術中的真理概念。這指出了自指範圍的主要限制。我們不可定義出一個式子True(n)以擴展出T*，不過我們仍可透過表達能力超越L的元語言來達到這點。例如：二階算術可定義出一階算術的真謂詞。可是元語言只可定義出對象語言中的句子的真謂詞。我們必須以更高階的元語言（即元語言的元語言）來定義元語言的真謂詞，這樣的定義方式是永無止盡的。

這個定理算是波斯特定理（Post's theorem）在算術階層中的引理。這個定理是繼塔斯基不可定義定理發表數年後完成的。在波斯特定理的基礎下，我們可透過歸謬法給出塔斯基定理的語義證明如下：

假設T*是算術上可定義的，那麼，我們可透過自然數n將T*定義在算術階層的第階。然而，對任何k，T*都是-hard的。這樣，算術階層就在第n階崩潰，違反波斯特定理。（表示第a階到第b階的聯集。）

定理的推廣

[編輯]

塔斯基透過完全的語法學方法給出了更有力的證明。該結果適用於具備邏輯非，而且具有充分的自指能力使得對角線引理成立的這樣一類形式語言。一階算術滿足這些前設，不過，此定理對更廣義的一些形式系統也是成立的。

塔斯基不可定義定理之廣義形式如下：

令(L, N)為任何直譯形式語言，包括：邏輯非與歌德爾數g(x)，使對任何L-式子A(x)，存在式子B有：B↔A(g(B))。

令T*為在N中為真的L-式子的哥德爾數的集合。我們試圖證明：不存在可定義T*的L-式子True(n)，亦即，不存在L-式子True(n)使對任何L-式子A，有：True(g(A))↔A。

我們透過歸謬法來證明這一點。

假設L-式子True(n)可定義T*。例如，若A是算術系統的句子，則在N中有True(g(A))若且唯若A在N中為真。所以，對任何A，塔斯基T-句子True(g(A))↔A在N中為真。但我們透過對角線引理可構造出一個反例，即給出一個「謊言」句子S，有：S↔¬True(g(S))。是故，不存在可定義T*的L-式子True(n)。證明完畢。

這個證明的形式構造除了對角線引理的對角線化過程外，都很淺顯易懂。對角線引理的證明，同樣不太困難，因為它不涉及遞迴函數。雖然這個證明假設任何L-式子都配有歌德爾數，但我們並不需要真的去編碼。所以，在一階算術的元數學性質上，塔斯基定理比著名的哥德爾定理還容易想到和證明。

探討

[編輯]

如果一種直譯語言的謂詞與函數符號足以定義出自身中所有語義概念，就稱這語言具有「語義上強自我表達」能力。其中，必要的函數包括：「語義賦值函數」，用以將式子A映射到它的真值||A||，及「語義表示函數」，用以將項t，映射到它所表示的對象。最終，塔斯基定理總結道：「不管一種語言的表達能力有多強，它也不具有語義上強自我表達能力。」

無論如何，塔斯基不可定義定理並未禁止以較強的理論去定義較弱的理論中的真理。例如，在N中為真的一階皮亞諾算術式子（的編碼）的集合，可以被二階算術中的式子所定義；類似地，由二階算術（以及任何的n階算術）的標準模型中的真式子組成的集合，可被一階ZFC系統中的式子所定義。

雷德蒙·斯穆里安強烈建議人們將目光從哥德爾不完備定理轉移到塔斯基不可定義定理上，因為前者主要涉及數學，而在哲學議題的範疇中效果不顯著。反之，塔斯基定理並不直接涉及數學，卻涉及任何形式語言在充分表達能力上的固有限制，值得探討。這種語言須具有充分的自指能力以使得對角線引理適用。引進塔斯基定理對哲學領域的擴展效果更加顯著。

參考資料

[編輯]
取自 "https://zh.wikipedia.org/w/index.php?title=塔斯基不可定義定理&oldid=74016159"