塔尔斯基不可定义性定理

也称真理的不可定义性定理，塔尔斯基在20世纪20年代所提出的一条重要定理，是塔尔斯基语义学的一块基石。该定理是说：对一般的形式理论，“真句子”这一概念是不能在该理论的内部定义的。

塔尔斯基原来的定理是针对一阶形式数论系统提出的，他证明：算术中的“真句子”概念不能在一阶算术中定义。

设=｛0，1，+，·｝是一阶算术的形式语言，=〈N，0，1，+，·〉为其标准解释，序列

α，α，α，……(*)

是全体公式的一个能行的枚举。

以a，b，c，……表示自然数，以，，，……表示自然数a，b，c……的形式表达式(无变元项)，例如=0，=1+1，等等。

设SN是一n元数组集合，如果存在一个恰含n个自由变元x，……，x的公式α(x，……，x)使

(a，…，a)∈S当且仅当α(，…，)则称S为可定义集，α称为S的定义公式。

事实上，可定义集就是算术集。

设T是在标准模型中为真的全体句子(闭公式)集，即

T=｛n｜α是句子且α｝，

真理的定义问题就是：T是不是可定义集?或等价地是否存在恰含一个自由变元的公式α(x)使对每个闭公式α

α当且仅当α()?

塔尔斯基定理否定地回答了上述问题：T不是可定义集。

从现代观点来看，证明塔尔斯基定理就是证明T不是算术集，为此只要证明每个算术集A都可图灵归约为T(从而对任何n，T∑n)就可以了，证明的基本思想如下：

任给算术集A，A当然是可定义的，使β(x)为A的定义公式：

n∈A 当且仅当 β()

　　 当且仅当 #(β())∈T

(其中#(ψ)为ψ在序列(*)中的号码)。

由于β是固定的(与n无关)，而从n得到β()，再得到#(β())的过程是能行的(递归的)，于是有

A≤T

塔尔斯基原先的证明(当时递归论尚未诞生)，可以看作哥德尔不完全性定理的证明的一个推论。但塔尔斯基的证明比哥德尔定理要早若干年。

塔尔斯基证明的基本思想可概括如下：

任何一个句子(闭公式)都可以看作是用无变元项代入一个恰含一个自由变元的公式而得到的。

设α(x，y)是这样一个公式：任给一对自然数a，b。

α(，)当且仅当对某个含一个自由变元的公式β(x)，a=#(β(x))且β()

容易证明，如果T可定义，则α(x，y)存在，且对任何含一个自由变元的公式β(x)，

#(β())∈T当且仅当a=#(β(x))且α(，)。(* *)

令β′(x)是α(x，x)，#(β′(x))=p。问β′()(闭公式)是真是假?

如果β′()为真(β′()，即#(β′())∈T)，则由(* *)知α(，)，而β′()正是α(，p)，从而β′()为假，矛盾。

如果β′()为假，即#(β′())T，由(* *)知α(，)，α(，)为真，即β′()为真，矛盾。

这两个矛盾表明α(x，y)不存在，因而T不可定义。