高 珂

（北京大學(xué) 哲學(xué)系，北京 100871）

塔斯基的算術(shù)真不可定義定理（Tarski’s theorem on the undefinability of arithmetical truth）表明一階算術(shù)真語(yǔ)句集在標(biāo)準(zhǔn)自然數(shù)模型上是不可定義的。通過(guò)分析證明，可以發(fā)現(xiàn)這一結(jié)果本質(zhì)上依賴對(duì)角線引理（diagonalization lemma）的使用。根據(jù)哥德?tīng)枺℅?del）的工作，可以將元語(yǔ)言算術(shù)化，這樣便可以定義更一般的真語(yǔ)句集。而利用緊致性定理（compactness theorem）很容易證明除標(biāo)準(zhǔn)自然數(shù)模型外，還存在許多非標(biāo)準(zhǔn)的一階算術(shù)模型。本文將推廣塔斯基的結(jié)果，證明通過(guò)塔斯基T-語(yǔ)句和語(yǔ)義定義構(gòu)造的真語(yǔ)句集在可數(shù)的非標(biāo)準(zhǔn)算術(shù)模型上都是不可定義的。更進(jìn)一步，這些證明將不依賴于對(duì)角線引理，這表明對(duì)于這些真語(yǔ)句集在模型上的不可定義性，對(duì)角線性質(zhì)并不是本質(zhì)的。在此基礎(chǔ)上，最后本文還將討論這些真語(yǔ)句集的相對(duì)不可定義性。

一、真語(yǔ)句集的定義

令一階算術(shù)語(yǔ)言LA＝｛+，·，0，1，＜｝，PA表示皮亞諾算術(shù)（Peano arithmetic）。根據(jù)哥德?tīng)柕墓ぷ鳎浑A算術(shù)語(yǔ)言中的每個(gè)符號(hào)、公式、公式序列都有唯一的一個(gè)哥德?tīng)柧幋a，用符號(hào)┌┐表示，為了表述方便，一般不區(qū)分這些表達(dá)式與他們的哥德?tīng)柧幋a。又因?yàn)橐浑A算術(shù)語(yǔ)言下的項(xiàng)、句子和公式的編碼構(gòu)成的集合是原始遞歸的，所以這些集合在PA中可表示［1］，分別用公式Term（x），Sent（x）和Form（x）表示。即M滿足Term（n）當(dāng)且僅當(dāng)n是一個(gè)項(xiàng)的哥德?tīng)柧幋a。

根據(jù)塔斯基的T-語(yǔ)句，可以定義滿足去引號(hào)性質(zhì)的真語(yǔ)句集如下。

定義1 假設(shè)M是一個(gè)PA的模型。M的子集S是M上的T-集合，當(dāng)且僅當(dāng)對(duì)于所有的一階算術(shù)公式φ（ˉv），

如果模型（M，S）還滿足所有LA∪｛S｝語(yǔ)言下的歸納法，那么稱這樣的S是一個(gè)歸納T-集合。

更一般地，通過(guò)對(duì)語(yǔ)言的算術(shù)化，還可以定義通過(guò)塔斯基語(yǔ)義定義的真語(yǔ)句（編碼）集如下。

定義2 假設(shè)M是一個(gè)PA的模型。M的子集S是M上的一個(gè)全滿足類（full satisfaction class），當(dāng)且僅當(dāng)對(duì)于任意滿足MFrom（φ）的公式 φ以及 a∈M，（φ，a）∈S當(dāng)且僅當(dāng)下列某項(xiàng)在模型（M，S）中成立①更準(zhǔn)確地說(shuō)，這里應(yīng)當(dāng)是對(duì)子的編碼屬于S，為了表述方便一般不區(qū)分對(duì)子與它的編碼，希望不會(huì)引發(fā)歧義。。

T1（φ，a）：?t?s（Term（t） Term（s） φ＝（t＝s） val（s）＝val（t））；

T2（φ，a）：?t?s（Term（t） Term（s） φ＝（t＜s） val（s）＜val（t））；

T3（φ，a）：?ψ（Form（ψ） φ＝ ψ （ψ，a）?S）；

T4（φ，a）：?ψ1，ψ2（Form（ψ1） Form（ψ2） φ＝（ψ1ψ2）（（ψ1，a）∈S （ψ2，a）∈S））；

T5（φ，a）：?ψ1，ψ2（Form（ψ1） Form（ψ2） φ＝（ψ1ψ2）（（ψ1，a）∈S （ψ2，a）∈S））；

T6（φ，a）：?i，ψ（From（ψ） φ＝?viψ ?b（（ψ，a［b／i］）∈S））；

T7（φ，a）：?i，ψ（From（ψ） φ＝?viψ ?b（（ψ，a［b／i］）∈S）），

其中，val是PA下可定義的賦值函數(shù)，a是φ中參數(shù)的編碼，a［b／i］表示用b替換a解碼得到的參數(shù)序列中的第i個(gè)元素后得到序列的編碼。

定義3 M的子集S是M上的一個(gè)部分滿足類（partial satisfaction class），當(dāng)且僅當(dāng)對(duì)于任意滿足MFrom（φ）的公式 φ以及 a∈M，（φ，a）∈S當(dāng)且僅當(dāng)存在 M中的非標(biāo)準(zhǔn)元 c，使得任意 φ＜c，（M，S）

類似地，如果一個(gè)M上的部分（全）滿足類S使得模型（M，S）還滿足所有LA∪｛S｝語(yǔ)言下的歸納法，那么我們稱這樣的S是一個(gè)歸納部分（全）滿足類（inductive partial（full）satisfaction class）。

定義4 一個(gè)M的子集X在模型M上是可定義的，當(dāng)且僅當(dāng)存在一個(gè)公式φ（x，ˉa）和一組給定的有窮參數(shù)ˉa∈M使得

二、算術(shù)模型的遞歸飽和性

拉克蘭（Lachlan）、科特拉爾斯基（Kotlarski）和克拉熱夫斯基（Krajewski）在20世紀(jì)80年代的工作表明，當(dāng)M是一個(gè)可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型時(shí)，模型上的全滿足類與模型的遞歸飽和性之間存在著密切聯(lián)系。

定理1 （拉克蘭，1981）假設(shè)M是一個(gè)可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型。如果M上存在一個(gè)全滿足類，那么M是遞歸飽和的［2］。

定理2 （拉克蘭、科特拉爾斯基和克拉熱夫斯基，1981）如果M是一個(gè)可數(shù)的一階算術(shù)模型并且M是遞歸飽和的，那么M上一定存在一個(gè)全滿足類［3］。

推廣拉克蘭等人的結(jié)果到歸納部分滿足類與歸納T-集合上，可以證明定理1和定理2結(jié)論依然成立。在證明上述命題之前，本小節(jié)將先給出一些模型遞歸飽和性相關(guān)的概念和性質(zhì)。

定義5 假設(shè)L是可數(shù)的一階語(yǔ)言，M是任意L-模型，bˉ∈M是一組給定的有窮參數(shù)。

1.L-公式集p（v，ˉb）＝｛φi（v，bˉ）∶i∈N｝是M上的型，當(dāng)且僅當(dāng)p（v，bˉ）在M中有窮滿足，即對(duì)于任意自然數(shù)構(gòu)成的有窮集I，都存在M中的元素a使得對(duì)于任意I中的元素i都有Mφi（a，bˉ）。

2.一個(gè)型p（v，bˉ）是遞歸的，當(dāng)且僅當(dāng)集合

是遞歸的，這里ˉw是一串有窮長(zhǎng)的變?cè)?/p>

3.M是遞歸飽和的，當(dāng)且僅當(dāng)所有M上的遞歸型都在M中被實(shí)現(xiàn)。

通過(guò)下列性質(zhì)，很容易得知，并非所有的可數(shù)算術(shù)模型都是遞歸飽和的。

性質(zhì)1 有窮生成的模型不是遞歸飽和的。

證明：假設(shè)K是有窮集合｛a0，…，an｝的斯克倫閉包，那么K中的元素都應(yīng)該形如t（a0，…，an），其中t是斯克倫項(xiàng)，考慮如下遞歸集

顯然，p（v）的有窮子集都在K中被實(shí)現(xiàn)，所以p（v）在K中有窮滿足，依定義p（v）是M上的遞歸型，但同時(shí)p（v）在K中無(wú)法實(shí)現(xiàn)，所以K不是遞歸飽和的。

定義6 假設(shè)L是一個(gè)一階語(yǔ)言。

其中，X1，…，Xn是新的關(guān)系或運(yùn)算符號(hào)，φ（X1，…，Xn，ˉx）是擴(kuò)充后的語(yǔ)言L∪｛X1，…，Xn｝下的公式。如果φ（X1，…，Xn，ˉx）中沒(méi)有自由的一階變?cè)?，那?X1，…，Xnφ（X1，…，Xn）是一個(gè)∑11句子。一個(gè)L-模型滿足句子 Φ＝?X1，…，Xnφ（X1，…，Xn）當(dāng)且僅當(dāng)存在一個(gè) M的膨脹（M，X1，…，Xn）使得

2.如果T是一個(gè)一階理論，那么T+Φ是一致的當(dāng)且僅當(dāng)存在一個(gè)滿足T的一階模型的膨脹滿足T+φ（X1，…，Xn）。

3.一個(gè)L-模型M是華麗的當(dāng)且僅當(dāng)對(duì)于所有有窮長(zhǎng)的參數(shù)ˉa∈M以及LU｛ˉa｝語(yǔ)言下的句子Φ（ˉa），都有：

根據(jù)克林尼（Kleene）、巴維斯（Barwise）和施利普夫（Schlipf）給出的結(jié)果，對(duì)于可數(shù)的算術(shù)模型而言，模型的華麗性與遞歸飽和性是等價(jià)的，這一性質(zhì)在以后的工作中將起到重要作用。

命題1 （巴維斯和施利普夫，1975）假設(shè)L是一個(gè)遞歸語(yǔ)言，M是L語(yǔ)言下的可數(shù)遞歸飽和模型，ˉa∈M是一組有窮的參數(shù)，語(yǔ)言L′是語(yǔ)言L∪｛ˉa｝的一個(gè)遞歸擴(kuò)張，T是一個(gè)L′語(yǔ)言下遞歸可公理化的理論。如果Th（M+ˉa）+T是一致的，那么存在一個(gè)（M，ˉa）在L′語(yǔ)言下的膨脹滿足T［4］。

命題2 （克林尼，1952）假設(shè)L是一個(gè)只包含有窮多的關(guān)系、函數(shù)和常元符號(hào)的一階語(yǔ)言。令｛θi（ˉx）∶i∈N｝是一個(gè)由L-公式構(gòu)成的遞歸集，其中對(duì)任意標(biāo)準(zhǔn)自然數(shù)i，θi（ˉx）上都只有有窮的自由變?cè)?。存在一個(gè)L語(yǔ)言下的公式Φ（ˉx）使得，對(duì)任意無(wú)窮L-模型M，有

定理3 任給可數(shù)的一階算術(shù)模型M。M是遞歸飽和的當(dāng)且僅當(dāng)M是華麗的。

證明：因?yàn)橐浑A算術(shù)語(yǔ)言包含的關(guān)系、函數(shù)和常元符號(hào)都是有窮的，由命題2可得，如果一個(gè)可數(shù)的一階算術(shù)模型是華麗的，那么它一定是遞歸飽和的。上述結(jié)果結(jié)合命題1即所求。

三、真語(yǔ)句集與模型的遞歸飽和性

本小節(jié)將主要證明對(duì)定理1和定理2的推廣。

定理4

a.假設(shè)M是一個(gè)可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型，M上存在一個(gè)歸納部分滿足類當(dāng)且僅當(dāng)M是遞歸飽和的。

b.假設(shè)M是一個(gè)可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型，M上存在一個(gè)歸納T-集合當(dāng)且僅當(dāng)M是遞歸飽和的。

先給出一些必要的技術(shù)性結(jié)果。

性質(zhì)2 （溢出原則）假設(shè)M是一個(gè)非標(biāo)準(zhǔn)的一階算術(shù)模型，aˉ∈M是一組給定的有窮參數(shù)，φ（v，aˉ）是一個(gè)標(biāo)準(zhǔn)一階算術(shù)公式。如果對(duì)于任意自然數(shù)n，都有Mφ（n，aˉ），那么一定存在一個(gè)M中的非標(biāo)準(zhǔn)元 b，使得

證明：假設(shè)不存在這樣的非標(biāo)準(zhǔn)元，即對(duì)于所有M中的非標(biāo)準(zhǔn)元b，都沒(méi)有M?i≤bφ（i，aˉ）。

驗(yàn)證，對(duì)于任意M中的元素c，有?y≤cφ（y，aˉ）→?y≤c+1φ（y，aˉ）。當(dāng)c是標(biāo)準(zhǔn)自然數(shù)時(shí)，上述命題顯然成立。又根據(jù)假設(shè)，如果有?y≤cφ（y，aˉ），那么c一定是標(biāo)準(zhǔn)的，那么由標(biāo)準(zhǔn)自然數(shù)的性質(zhì)可知c+1也一定是標(biāo)準(zhǔn)的。

根據(jù)上述論述，就會(huì)有

性質(zhì)3 假設(shè)M是一個(gè)非標(biāo)準(zhǔn)一階算術(shù)模型，S是一個(gè)M上的部分（全）滿足類，φ（v0，…，vn）是只帶有自由變?cè)獀0，…，vn的標(biāo)準(zhǔn)一階算術(shù)公式，那么對(duì)所有的M中的元素a，

證明：對(duì)標(biāo)準(zhǔn)一階算術(shù)公式φ的復(fù)雜度施歸納，由滿足類的定義與賦值函數(shù)的性質(zhì)易得。

首先證明定理4a。

命題3 假設(shè)模型M是一個(gè)可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型。如果M上存在一個(gè)歸納部分滿足類，那么M是遞歸飽和的。

證明：假設(shè)S是M上的一個(gè)歸納部分滿足類，p（v）是M上的遞歸型，不失一般性地，可以假設(shè)p（v）中只帶有一個(gè)自由變?cè)襭（v）中不帶參數(shù)。因?yàn)閜（v）是遞歸的，所以存在M中的元素b，使得p（v）被b編碼。那么對(duì)于任意標(biāo)準(zhǔn)自然數(shù)n，我們都有

因?yàn)镾是可歸納的，根據(jù)溢出原則，M中一定存在非標(biāo)準(zhǔn)元c，使得

根據(jù)性質(zhì)3，任意M中的元素d，只要d滿足上述公式，那么d就實(shí)現(xiàn)p（v）。

接下來(lái)證明定理4a的另一個(gè)方向。

引理1 如果模型M是一個(gè)可數(shù)的非標(biāo)準(zhǔn)算術(shù)模型，那么存在可數(shù)模型N使得N是M的初等擴(kuò)張并且N上有一個(gè)歸納部分滿足類。

證明：令ˉM＝M∪｛ca∶a∈M｝，其中ca是新的常元符號(hào)。再令T是如下理論：

其中，φ是標(biāo)準(zhǔn)的一階算術(shù)公式。

首先驗(yàn)證T是一致的。

取T的有窮子理論T′，使得T′中包含的任意公式θ的哥德?tīng)柧幋a都小于某個(gè)自然數(shù)n，定義M的子集 S′如下

其中，令iθ表示出現(xiàn)在θ中的自由變?cè)淖畲笾笜?biāo)。顯然，S′在M中可以被一個(gè)標(biāo)準(zhǔn)一階算術(shù)公式定義，所以（M，S′）滿足擴(kuò)張后語(yǔ)言下公式的歸納法，又因?yàn)樗懈绲聽(tīng)柧幋a小于給定n的公式構(gòu)成的集合對(duì)子公式封閉，所以（M，S′）滿足T′，再根據(jù)緊致性定理，就得到了T是一致的。

令（N，S″）是T的模型，N是可數(shù)的。根據(jù)T的定義，N是M的初等擴(kuò)張。接下來(lái)只需證明存在N中非標(biāo)準(zhǔn)元b，使得S″限制在＜b上是一個(gè)歸納部分滿足類。

根據(jù)定義，對(duì)于任意標(biāo)準(zhǔn)自然數(shù)n，都有

又因?yàn)檫@是一個(gè)擴(kuò)張后語(yǔ)言下的公式，而（N，S″）滿足所有擴(kuò)張后語(yǔ)言下公式的歸納法，所以溢出原則對(duì)這個(gè)公式有效。所以，存在N中的非標(biāo)準(zhǔn)元b使得

令 S＝｛（φ，a）∶φ＜a （φ，a）∈S″｝。顯然，S在（N，S″）中是可定義的，所以（N，S）滿足歸納公理。這樣，S就是N上的一個(gè)歸納部分滿足類。

命題4 如果M是一個(gè)可數(shù)的一階算術(shù)模型并且M是遞歸飽和的，那么M上一定存在一個(gè)歸納部分滿足類。

證明：根據(jù)定理3，模型M是華麗的。而“存在一個(gè)歸納部分滿足類”可以表示為

其中，LS-IND表示擴(kuò)張后語(yǔ)言LA∪｛S｝下的歸納公理。（*）中的無(wú)窮合取都是遞歸的，所以這些無(wú)窮合取等價(jià)于一個(gè)公式，所以（*）等價(jià)于一個(gè)公式，根據(jù)引理1可得Th（M）+（*）是一致的，又根據(jù)華麗性的定義，M滿足（*），也就是M上存在一個(gè)歸納部分滿足類。

類似地，可以證明定理4b如下。

命題5 假設(shè)M是一個(gè)可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型。如果M上存在一個(gè)歸納T-集合，那么M是遞歸飽和的。

證明：假設(shè)S是M上的一個(gè)歸納T-集合，p（v）是M上的遞歸型。類似命題3可以得到存在M中的非標(biāo)準(zhǔn)元c，使得

又根據(jù)定義，T-集合中的都是標(biāo)準(zhǔn)的一階算術(shù)語(yǔ)句，所以對(duì)于任意的自然數(shù)n都有Mφn（c，aˉ）。這樣我們就找到了一個(gè)c使得遞歸型p（v）在M中被實(shí)現(xiàn)。

引理2 如果M是一個(gè)可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型，那么存在可數(shù)模型N使得N是M的初等擴(kuò)張并且N上有一個(gè)歸納T-集合。

證明：令T＝Th（ˉM）+LS語(yǔ)言下公式的歸納法+?y（S（φ，y）?φ（y）），其中φ是標(biāo)準(zhǔn)的一階算術(shù)公式。類似引理1可得。

命題6 如果M是一個(gè)可數(shù)的算術(shù)模型并且M是遞歸飽和的，那么M上一定存在一個(gè)歸納T-集合。

證明：“存在一個(gè)歸納T-集合”可以表示為

其中，LS-IND表示擴(kuò)張后語(yǔ)言LA∪｛S｝下的歸納公理。與命題4類似，（**）是一個(gè)公式。再根據(jù)引理2，可知（**）與Th（M）是一致的。最后，由華麗性的定義可得，M上存在一個(gè)歸納T-集合。

四、真語(yǔ)句集的不可定義性和相對(duì)可定義性

利用上一小節(jié)的結(jié)果，本節(jié)將證明全滿足類、部分滿足類與歸納-集合在非標(biāo)準(zhǔn)算術(shù)模型上的不可定義性，特別地，這些證明將不依賴于對(duì)角線引理。此外，本小節(jié)還將討論上述集合的相對(duì)可定義性。

如果有對(duì)角線引理，根據(jù)塔斯基真不可定義定理和性質(zhì)3，很容易得到部分滿足類在算術(shù)模型上的不可定義性結(jié)果。

定理5 假設(shè)M是一個(gè)可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型，S是一個(gè)M上的部分滿足類，那么S在M中不能被標(biāo)準(zhǔn)算術(shù)公式定義。

證明：假設(shè)S可以被標(biāo)準(zhǔn)一階算術(shù)公式φ（x，y，ˉa）定義，ˉa∈M是一組給定的有窮參數(shù)。根據(jù)性質(zhì)3，對(duì)于所有的標(biāo)準(zhǔn)算術(shù)公式ψ，都會(huì)有

其中，［ˉa］是ˉa的編碼。這與塔斯基算術(shù)真不可定義定理矛盾。

因?yàn)樗够乃阈g(shù)真不可定義定理本質(zhì)上依賴于對(duì)角線引理，所以在定理5的證明中，對(duì)角線引理是本質(zhì)的，如此，定理5可以被視作對(duì)角線引理的一個(gè)直接推論。

下面以歸納-集合為例，給出一個(gè)不依賴于對(duì)角線引理的不可定義性的證明。

定理6 假設(shè)M是一個(gè)可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型，S是一個(gè)M上的歸納T-集合，那么S在M中不能被標(biāo)準(zhǔn)算術(shù)公式定義。

證明：假設(shè)S可以被一個(gè)帶有有窮參數(shù)a0，…，an的標(biāo)準(zhǔn)一階算術(shù)公式定義。令K是上述有窮參數(shù)的斯克倫閉包，那么K是M的初等子模型，所以S限制在K上是一個(gè)K上的歸納T-集合，根據(jù)定理4b，K是遞歸飽和的，但是由性質(zhì)1，K不可能是遞歸飽和模型，這就導(dǎo)致了矛盾。

歸納部分滿足類和全滿足類在算術(shù)模型上的不可定義性可以用同樣的證明思路獲得。

定理7 假設(shè)M是一個(gè)可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型，S是一個(gè)M上的歸納部分滿足類或全滿足，那么S在M中不能被標(biāo)準(zhǔn)算術(shù)公式定義。

接下來(lái)的定理表明，盡管全滿足類、部分滿足類和T-集合都是在可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型上不可定義的，但他們之間存在著某種相對(duì)可定義性。先給出一些必要的預(yù)備知識(shí)。

定義7 假設(shè)M和N是兩個(gè)一階算術(shù)模型，稱M是N的尾節(jié)擴(kuò)張當(dāng)且僅當(dāng)N是M的子模型并且N對(duì)于M的序關(guān)系向下封閉。如果N是M的真子集，則稱N是M的真尾節(jié)擴(kuò)張。

定理8 （麥克道威爾-施佩克爾定理（MacDowell-Specker Theorem））任意一階算術(shù)模型都有一個(gè)真的初等尾節(jié)擴(kuò)張。

更多算術(shù)模型尾節(jié)的細(xì)節(jié)，可以參看凱伊（Kaye）的專著［6］。

定理9 假設(shè)M是一個(gè)可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型。如果M上存在一個(gè)歸納部分滿足類S，那么M上一定存在另一個(gè)歸納部分滿足類S′使得S′在模型（M，S）中可定義。

證明：根據(jù)擴(kuò)張后語(yǔ)言下的麥克道威爾-施佩克爾定理，存在（N，S″）使得（N，S″）是模型（M，S）的初等尾節(jié)擴(kuò)張。根據(jù)定義很容易驗(yàn)證，S″是 N上的歸納部分滿足類。令S′等于S″限制在M上。因?yàn)椋∟，S″）是（M，S）的初等尾節(jié)擴(kuò)張，所以 S′在（M，S）中可定義并且是歸納的。

接下來(lái)只需證明S′是一個(gè)部分滿足類。依定義驗(yàn)證，其他的條件都是平凡（trivial）成立的，唯一的困難在于帶有量詞的情況。這里，只處理存在量詞，全稱量詞可以類似得到?？紤]公式Φ（n，X）定義如下

顯然，標(biāo)準(zhǔn)的一階算術(shù)語(yǔ)句φ使得Φ（φ，S′）成立，而φ被標(biāo)準(zhǔn)自然數(shù)編碼。這樣我們就有

分析上述定理的證明，很容易發(fā)現(xiàn)將定理的條件改成“M上存在一個(gè)全滿足類”或者“M上存在一個(gè)T-集合”，結(jié)果依然成立。這樣，可以將定理8推廣到更一般的結(jié)果上。

定理10 假設(shè)M是一個(gè)可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型。如果X是M上的一個(gè)不可定義集并且M上存在X可以推導(dǎo)出M是遞歸飽和的，那么M上一定存在一個(gè)歸納部分滿足類S使得S在模型（M，X）中是可定義的。

證明：由定理4a和定理9可以直接得到。

一個(gè)自然的問(wèn)題是，除了可以推導(dǎo)出模型遞歸飽和性的不可定義集，是否存在別的不可定義集，使得存在一個(gè)在擴(kuò)充模型上可定義的歸納部分滿足類。

接下來(lái)我們給出一個(gè)否定的結(jié)果，證明在用科恩力迫（Cohen forcing）構(gòu)造的不可定義集擴(kuò)充得到的模型上不存在可定義的歸納部分滿足類。通過(guò)這個(gè)結(jié)果，我們似乎有理由相信能夠推出模型的遞歸飽和性是使得某個(gè)歸納可滿足類在擴(kuò)充后模型上可滿足的必要條件。

定義8 給定一個(gè)模型M，令2＜M是由可定義函數(shù)p∶｛0，…，a｝→｛o，1｝構(gòu)成的集合，其中a是M的元素。

（1）一個(gè)集合D?2M是稠密的當(dāng)且僅當(dāng)對(duì)于任意p∈2＜M存在一個(gè)q∈D使得p?q。

（2）一個(gè)集合G?＜M是脫殊的（generic）當(dāng)且僅當(dāng)

a.對(duì)于所有的G的元素p，q，p和q都可比；

b.對(duì)于所有的G的元素p和所有的M的元素a，p限制在a上屬于G；

c.對(duì)于所有的可定義稠密集D，G和D的交非空。

（3）給定一個(gè)G是脫殊的，令XG＝｛x∈M∶?p∈G（p（x）＝1）｝。稱XG是M的一個(gè)脫殊子集。

下列性質(zhì)可以在奧德弗雷德（Odifreddi）的專著［7］中找到，這里省略具體證明。

性質(zhì)4 假設(shè)M是一個(gè)一階算術(shù)模型，則有：

（1）如果M是可數(shù)的，那么M上有一個(gè)脫殊集。

（2）脫殊集在模型M中是不可定義的。

（3）脫殊集在模型M中是歸納的。

（4）如果X是M的一個(gè)脫殊子集，那么存在一個(gè)M的不可定義子集Y，使得Y在模型（M，X）中可定義，但同時(shí)X在模型（M，Y）中不可定義。

從性質(zhì)1和定理4a我們可以得到并非所有的可數(shù)非標(biāo)準(zhǔn)算術(shù)模型上存在一個(gè)歸納部分滿足類，又由性質(zhì)4中的（1）得所有可數(shù)的算術(shù)模型上都存在一個(gè)脫殊集。這樣我們就可以得到以下的結(jié)果。

性質(zhì)5 如果M是一個(gè)可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型，那么M上的所有歸納部分滿足類都不是脫殊的。

證明：假設(shè)S是M上的一個(gè)歸納部分滿足類，并且S是脫殊的。根據(jù)擴(kuò)張語(yǔ)言下的麥克道威爾-施佩克爾定理，存在（N，S′）使得（N，S′）是（M，S）的一個(gè)初等尾節(jié)擴(kuò)張。給定一個(gè) N中的非標(biāo)準(zhǔn)元 a，令 S″等于S′限制在＜a上，根據(jù)尾節(jié)擴(kuò)張的性質(zhì)，S″在 N中是可以被編碼的，令 b是 S″的編碼。令 K是M∪｛b｝的斯克倫閉包。很容易驗(yàn)證S″可以被拓展成一個(gè)集合G，使得G在K中是脫殊的。又根據(jù)力迫的一般性質(zhì)，我們可以得到模型（K，G）是模型（M，S）的一個(gè)初等擴(kuò)張，所以G是K上的一個(gè)歸納部分滿足類。另一方面，根據(jù)構(gòu)造可知，K是一個(gè)有窮生成模型的共尾擴(kuò)張，類似性質(zhì)1可以證明這樣的模型不是遞歸飽和的，又由定理4a可知，K上不存在歸納的部分滿足類，這就導(dǎo)出了矛盾。

下列的結(jié)果表明，在可數(shù)的算術(shù)模型看來(lái)，歸納部分滿足類的不可定義性要“強(qiáng)于”脫殊集的不可定義性，這也在某種程度上說(shuō)明了“真”的定義需要極高的要求。

定理11 假設(shè)M是一個(gè)可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型。如果G是M上的一個(gè)脫殊子集，那么不存在M上的歸納部分滿足類S使得S在模型（M，G）中可定義。

證明：假設(shè)存在這樣的歸納部分滿足類，可以利用性質(zhì)5一樣的思路來(lái)構(gòu)造矛盾。

定理12 假設(shè)M是一個(gè)可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型。如果M上存在一個(gè)歸納部分滿足類S，那么M上一定存在一個(gè)脫殊子集G使得G在模型（M，S）中可定義。

證明：只需要驗(yàn)證“存在脫殊集”可以被形式化到模型（M，S）中。

結(jié)合性質(zhì)4中的（4）和定理12，我們還能進(jìn)一步得到某種歸納部分滿足類上的切分性質(zhì)。

推論1 假設(shè)模型M是一個(gè)可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型。如果M上存在一個(gè)歸納部分滿足類，那么一定存在一個(gè)M上的不可定義子集X使得在模型（M，S）中可定義，但是S在（M，X）中不可定義。

而根據(jù)定理11，我們還可以得到推論1的加強(qiáng)版。

推論2 假設(shè)M是一個(gè)可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型。如果M上存在一個(gè)歸納部分滿足類S，那么一定存在一個(gè)M上的不可定義子集X使得X在模型（M，S）中可定義，但是不存在M上在模型（M，X）中可定義的歸納部分滿足類。

五、總結(jié)

通過(guò)繼續(xù)克蘭、科特拉爾斯基和克拉熱夫斯基的工作，得到了如下結(jié)果。

定理13 如果M是一個(gè)可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型，那么下列命題兩兩等價(jià)：

（1）M是一個(gè)遞歸飽和模型；

（2）M上存在一個(gè)全滿足類；

（3）M上存在一個(gè)歸納部分滿足類；

（4）M上存在一個(gè)歸納T-集合。

在此基礎(chǔ)上，本文推廣塔斯基的結(jié)果，證明了全滿足類、部分滿足類、部分歸納滿足類以及歸納-集合在可數(shù)的非標(biāo)準(zhǔn)算術(shù)模型上都是不可定義的。需要注意的是，本文只證明這些集合在可數(shù)算術(shù)模型上的不可定義性，這并不能直接推導(dǎo)出塔斯基算術(shù)真不可定義定理。而通過(guò)對(duì)上述集合的相對(duì)不可定義性的分析，發(fā)現(xiàn)對(duì)于可數(shù)非標(biāo)準(zhǔn)算術(shù)模型而言，集合在模型上的存在性可以推出模型的遞歸飽和性這一性質(zhì)，是使得某個(gè)歸納部分滿足類在以這個(gè)集合做擴(kuò)張的模型上可定義的充分條件。進(jìn)一步地，證明了歸納部分滿足類在用科恩脫殊集做擴(kuò)張得到的模型上是不可定義的，所以我們有理由猜測(cè)集合的存在性可以推導(dǎo)模型的遞歸飽和性也是保證歸納部分滿足類可定義的必要條件。

最后，本文將以一些開(kāi)問(wèn)題作為結(jié)束。

問(wèn)題1 給定一個(gè)可數(shù)的非標(biāo)準(zhǔn)一階算術(shù)模型，在上面是否存在別的歸納不可定義集使得某個(gè)歸納部分滿足類在用上述不可定義集擴(kuò)張得到的模型上是可定義的？

斯莫林斯基（Smorynski）證明了存在滿足上述要求的不可定義集［8］，但斯莫林斯基的結(jié)果不是歸納的，是否存在這樣的歸納不可定義集仍是個(gè)開(kāi)問(wèn)題。

問(wèn)題2 將定理9結(jié)論中的歸納部分滿足類換成全滿足類或者-集合，定理9是否依然成立？