塔斯基不可定義定理

维基百科,自由的百科全书
跳转至: 导航搜索

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

歷史[编辑]

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

塔斯基不可定義定理則表明:這種編碼不能帶給我們語義的概念,例如:真理的概念。這表明:世上沒有任何直譯語言足以表達出它本身的語義。我們可推論出,元語言必須具備超越對象語言的表達能力,才可表達出對象語言的語義。元語言具有對象語言所沒有的原始概念、公理及規則,使得某些定理在對象語言中不可證明,在元語言中卻可證明。

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

塔斯基在1929至1931年間完成了他大部分的論文成果,並向波蘭的聽眾演說。這篇論文就是1936年發表的《形式化語言中的真理概念》(Der Wahrheitsbegriff in den formalisierten Sprachen)。然而,正如他在論文中所強調的,不可定義定理was the only result not obtained by him earlier.根據論文中不可定義定理的註解(Satz I),這個定理及其證明的草稿是在送印前才加進論文中的。

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

專有名詞介紹[编辑]

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

  • 一階算術:指一階邏輯
  • 算術語言:指形式語言
  • 對象語言:指被當成研究對象的語言。
  • 元語言:指用以研究對象語言的高階語言。
  • 式子:英文作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*定義在算術階層的第\Sigma^0_n階。然而,對任何k,T*都是\Sigma^0_k-hard的。這樣,算術階層就在第n階崩潰,違反波斯特定理。(\Sigma^a_b表示第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為真;而透過一階策梅洛-弗蘭克爾集合論(ZFC)可定義二階算術(直到n階算術)的真式子。

雷蒙·史慕揚(Raymond Smullyan)強烈建議人們將目光從哥德爾不完備定理轉移到塔斯基不可定義定理上,因為後者主要涉及數學,而在哲學議題的範疇中效果不顯著。反之,塔斯基定理並不直接涉及數學,卻涉及任何形式語言在充分表達能力上先天限制,使我們深感興趣。這種語言藉由對角線引理(diagonal lemma)的作用產生充分的自指能力。引進塔斯基定理對哲學領域的擴展效果更加顯著。

參考資料[编辑]