塔斯基不可定义定理

维基百科，自由的百科全书

塔斯基不可定义定理（英语：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”