不可定义性理论

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

## 歷史

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

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

一般認為不可定義定理是由塔斯基給出的。儘管哥德爾在 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\* 定義在算術階層的第 $\Sigma _{n}^{0}$ 階。然而，對任何 k，T\* 都是 $\Sigma _{k}^{0}$ -hard 的。這樣，算術階層就在第 n 階崩潰，違反波斯特定理。（ $\Sigma _{b}^{a}$ 表示第 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 系統中的式子所定義。

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

## 參考資料

* J.L. Bell, and M. Machover, 1977. _A Course in Mathematical Logic_. North-Holland.
* G. Boolos, J. Burgess, and R. Jeffrey, 2002. _Computability and Logic_, 4th ed. Cambridge University Press.
* J.R. Lucas, 1961. "Mind, Machines, and Gödel （頁面存檔備份，存於網際網路檔案館）". Philosophy 36: 112-27.
* R. Murawski, 1998. Undefinability of truth. The problem of the priority: Tarski vs. Gödel. History and Philosophy of Logic 19, 153-160
* R. Smullyan, 1991. _Godel's Incompleteness Theorems_. Oxford Univ. Press.
* R. Smullyan, 2001. "Gödel’s Incompleteness Theorems". In L. Goble, ed., _The Blackwell Guide to Philosophical Logic_, Blackwell, 72-89.
* A. Tarski. Der Wahrheitsbegriff in den formalisierten Sprachen (PDF). Studia Philosophica. 1936, **1**: 261–405 [26 June 2013]. （原始內容 (PDF) 存檔於 2014 年 1 月 9 日）.
* A. Tarski, tr J.H. Woodger, 1983. "The Concept of Truth in Formalized Languages". English translation of Tarski's 1936 article. （頁面存檔備份，存於網際網路檔案館） In A. Tarski, ed. J. Corcoran, 1983, _Logic, Semantics, Metamathematics_, Hackett.