不可定义性理论

[拼音]：bukedingyixing lilun

[外文]：theory of undefinability

模型论中关于形式语言表达能力的一种研究。在这种研究中，影响较大的有A.帕多瓦、A.塔尔斯基和E.W.贝特等人。可（不可）定义性概念在递归论和公理集合论（见集合论）中被广泛使用，其中有不少特殊的可定义性概念及有关结果，如递归论中的分层理论，公理集合论中的可构成集等。

设u是形式语言L的一个模型，a是u的一个元素，如果存在L中一个式子嗞(x)，使a是u中唯一的适合嗞(x) 的元素，则称a为u中的可定义元素，否则称a为u中的不可定义元素。类似的还可以给出可(不可)定义的函数、集合等概念，它们都可被包含在下述的“可（不可）定义谓词”概念中。设P(x₁，...，x_n)是u上的一个谓词，如果存在L中一个式子嗞(x₁，...，x_n)，使对u中任何元素a₁，...，a_n都有：P(a₁，...，a_n) 成立当且仅当嗞(x₁，...，xn)在u中为真，则称P(x₁，...，x_n)为在u上可定义的谓词；否则称P（x₁，...，x_n）为在u上不可定义的谓词。在一般情况下，并不提出特定的模型_u，而是在形式语言中讨论可定义性概念。设L是一个形式语言，P和P'是L之外的两个不同的n元谓词符号，∑(P)是语言 L∪｛P｝中的一组语句，∑(P')是语言L∪{P'}中相应的语句组。

（1）如果在 ∑(P)∪∑(P')的每一模型中都有 　(凬x₁，...，x_n)[P(x₁，...，x_n)凮P'(x₁，...，x_n)]成立，则称 ∑(P)隐含地定义了谓词P。

（2）如果存在L中一个式子嗞(x₁，...，x_n)，使在∑(P)的每一个模型中都有

(凬x₁，...，x_n)[P(x₁，...，x_n)凮嗞(x₁，...，x_n)]成立，则称∑(P)明显地定义了谓词P。

由以上定义可以看出，如果∑(P)明显地定义P，则它也隐含地定义P。所以，如果要说明某一组语句∑(P)不能明显地定义P，只需说明 ∑(P)不能隐含地定义P就够了，换句话也就是说，只需找到∑(P)∪∑(P')的一个模型，在其中P与P'有不同的解释就够了。这一方法称为帕多瓦方法。在这方面，贝特在帕多瓦和塔尔斯基的工作基础上进一步证明了：∑(P)隐含地定义P当且仅当∑(P)明显地定义P。从而表明，如果∑(P)不能明显地定义P，则这种不可定义性必能用帕多瓦方法来说明。

在具体模型中的不可定义性方面，塔尔斯基有一个关于自然数系统中真语句集不可定义性的著名定理，其内容如下:令语言 L={+，·，S，O}，取L的模型=(N，+，·，S，O)，其中 N为自然数集，S为“后继”运算，考虑L中一切在中为真的语句的集合T，通过适当的有效编码 ，就可以把 T看作N的子集。塔尔斯基定理是说：T是不可定义的。该定理与关于的判定问题的不可解性有一定联系。

80年代以来，在模型论中对于模型的范畴性，也就是它的完备理论的范畴性，有较多的研究，从性质上说，这是一种关于可定义性的广义研究。例如，有理数域不是埲 -范畴的，其含义是：在可数无限域范围内，有理数域不能用关于它的一切一阶真语句所成的集合唯一地刻划；又如，复数域是埌 -范畴的，其含义是：在基数为埌的无限域范围内，复数域可以用关于它的一切一阶真语句所成的集合唯一地刻划。