高 珂
(北京大學 哲學系,北京 100871)
塔斯基的算術(shù)真不可定義定理(Tarski’s theorem on the undefinability of arithmetical truth)表明一階算術(shù)真語句集在標準自然數(shù)模型上是不可定義的。通過分析證明,可以發(fā)現(xiàn)這一結(jié)果本質(zhì)上依賴對角線引理(diagonalization lemma)的使用。根據(jù)哥德爾(G?del)的工作,可以將元語言算術(shù)化,這樣便可以定義更一般的真語句集。而利用緊致性定理(compactness theorem)很容易證明除標準自然數(shù)模型外,還存在許多非標準的一階算術(shù)模型。本文將推廣塔斯基的結(jié)果,證明通過塔斯基T-語句和語義定義構(gòu)造的真語句集在可數(shù)的非標準算術(shù)模型上都是不可定義的。更進一步,這些證明將不依賴于對角線引理,這表明對于這些真語句集在模型上的不可定義性,對角線性質(zhì)并不是本質(zhì)的。在此基礎(chǔ)上,最后本文還將討論這些真語句集的相對不可定義性。
令一階算術(shù)語言LA={+,·,0,1,<},PA表示皮亞諾算術(shù)(Peano arithmetic)。根據(jù)哥德爾的工作,一階算術(shù)語言中的每個符號、公式、公式序列都有唯一的一個哥德爾編碼,用符號┌┐表示,為了表述方便,一般不區(qū)分這些表達式與他們的哥德爾編碼。又因為一階算術(shù)語言下的項、句子和公式的編碼構(gòu)成的集合是原始遞歸的,所以這些集合在PA中可表示[1],分別用公式Term(x),Sent(x)和Form(x)表示。即M滿足Term(n)當且僅當n是一個項的哥德爾編碼。
根據(jù)塔斯基的T-語句,可以定義滿足去引號性質(zhì)的真語句集如下。
定義1 假設(shè)M是一個PA的模型。M的子集S是M上的T-集合,當且僅當對于所有的一階算術(shù)公式φ(ˉv),
如果模型(M,S)還滿足所有LA∪{S}語言下的歸納法,那么稱這樣的S是一個歸納T-集合。
更一般地,通過對語言的算術(shù)化,還可以定義通過塔斯基語義定義的真語句(編碼)集如下。
定義2 假設(shè)M是一個PA的模型。M的子集S是M上的一個全滿足類(full satisfaction class),當且僅當對于任意滿足MFrom(φ)的公式 φ以及 a∈M,(φ,a)∈S當且僅當下列某項在模型(M,S)中成立①更準確地說,這里應當是對子的編碼屬于S,為了表述方便一般不區(qū)分對子與它的編碼,希望不會引發(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個元素后得到序列的編碼。
定義3 M的子集S是M上的一個部分滿足類(partial satisfaction class),當且僅當對于任意滿足MFrom(φ)的公式 φ以及 a∈M,(φ,a)∈S當且僅當存在 M中的非標準元 c,使得任意 φ<c,(M,S)
類似地,如果一個M上的部分(全)滿足類S使得模型(M,S)還滿足所有LA∪{S}語言下的歸納法,那么我們稱這樣的S是一個歸納部分(全)滿足類(inductive partial(full)satisfaction class)。
定義4 一個M的子集X在模型M上是可定義的,當且僅當存在一個公式φ(x,ˉa)和一組給定的有窮參數(shù)ˉa∈M使得
拉克蘭(Lachlan)、科特拉爾斯基(Kotlarski)和克拉熱夫斯基(Krajewski)在20世紀80年代的工作表明,當M是一個可數(shù)的非標準一階算術(shù)模型時,模型上的全滿足類與模型的遞歸飽和性之間存在著密切聯(lián)系。
定理1 (拉克蘭,1981)假設(shè)M是一個可數(shù)的非標準一階算術(shù)模型。如果M上存在一個全滿足類,那么M是遞歸飽和的[2]。
定理2 (拉克蘭、科特拉爾斯基和克拉熱夫斯基,1981)如果M是一個可數(shù)的一階算術(shù)模型并且M是遞歸飽和的,那么M上一定存在一個全滿足類[3]。
推廣拉克蘭等人的結(jié)果到歸納部分滿足類與歸納T-集合上,可以證明定理1和定理2結(jié)論依然成立。在證明上述命題之前,本小節(jié)將先給出一些模型遞歸飽和性相關(guān)的概念和性質(zhì)。
定義5 假設(shè)L是可數(shù)的一階語言,M是任意L-模型,bˉ∈M是一組給定的有窮參數(shù)。
1.L-公式集p(v,ˉb)={φi(v,bˉ)∶i∈N}是M上的型,當且僅當p(v,bˉ)在M中有窮滿足,即對于任意自然數(shù)構(gòu)成的有窮集I,都存在M中的元素a使得對于任意I中的元素i都有Mφi(a,bˉ)。
2.一個型p(v,bˉ)是遞歸的,當且僅當集合
是遞歸的,這里ˉw是一串有窮長的變元。
3.M是遞歸飽和的,當且僅當所有M上的遞歸型都在M中被實現(xiàn)。
通過下列性質(zhì),很容易得知,并非所有的可數(shù)算術(shù)模型都是遞歸飽和的。
性質(zhì)1 有窮生成的模型不是遞歸飽和的。
證明:假設(shè)K是有窮集合{a0,…,an}的斯克倫閉包,那么K中的元素都應該形如t(a0,…,an),其中t是斯克倫項,考慮如下遞歸集
顯然,p(v)的有窮子集都在K中被實現(xiàn),所以p(v)在K中有窮滿足,依定義p(v)是M上的遞歸型,但同時p(v)在K中無法實現(xiàn),所以K不是遞歸飽和的。
定義6 假設(shè)L是一個一階語言。
其中,X1,…,Xn是新的關(guān)系或運算符號,φ(X1,…,Xn,ˉx)是擴充后的語言L∪{X1,…,Xn}下的公式。如果φ(X1,…,Xn,ˉx)中沒有自由的一階變元,那么?X1,…,Xnφ(X1,…,Xn)是一個∑11句子。一個L-模型滿足句子 Φ=?X1,…,Xnφ(X1,…,Xn)當且僅當存在一個 M的膨脹(M,X1,…,Xn)使得
2.如果T是一個一階理論,那么T+Φ是一致的當且僅當存在一個滿足T的一階模型的膨脹滿足T+φ(X1,…,Xn)。
3.一個L-模型M是華麗的當且僅當對于所有有窮長的參數(shù)ˉa∈M以及LU{ˉa}語言下的句子Φ(ˉa),都有:
根據(jù)克林尼(Kleene)、巴維斯(Barwise)和施利普夫(Schlipf)給出的結(jié)果,對于可數(shù)的算術(shù)模型而言,模型的華麗性與遞歸飽和性是等價的,這一性質(zhì)在以后的工作中將起到重要作用。
命題1 (巴維斯和施利普夫,1975)假設(shè)L是一個遞歸語言,M是L語言下的可數(shù)遞歸飽和模型,ˉa∈M是一組有窮的參數(shù),語言L′是語言L∪{ˉa}的一個遞歸擴張,T是一個L′語言下遞歸可公理化的理論。如果Th(M+ˉa)+T是一致的,那么存在一個(M,ˉa)在L′語言下的膨脹滿足T[4]。
命題2 (克林尼,1952)假設(shè)L是一個只包含有窮多的關(guān)系、函數(shù)和常元符號的一階語言。令{θi(ˉx)∶i∈N}是一個由L-公式構(gòu)成的遞歸集,其中對任意標準自然數(shù)i,θi(ˉx)上都只有有窮的自由變元。存在一個L語言下的公式Φ(ˉx)使得,對任意無窮L-模型M,有
定理3 任給可數(shù)的一階算術(shù)模型M。M是遞歸飽和的當且僅當M是華麗的。
證明:因為一階算術(shù)語言包含的關(guān)系、函數(shù)和常元符號都是有窮的,由命題2可得,如果一個可數(shù)的一階算術(shù)模型是華麗的,那么它一定是遞歸飽和的。上述結(jié)果結(jié)合命題1即所求。
本小節(jié)將主要證明對定理1和定理2的推廣。
定理4
a.假設(shè)M是一個可數(shù)的非標準一階算術(shù)模型,M上存在一個歸納部分滿足類當且僅當M是遞歸飽和的。
b.假設(shè)M是一個可數(shù)的非標準一階算術(shù)模型,M上存在一個歸納T-集合當且僅當M是遞歸飽和的。
先給出一些必要的技術(shù)性結(jié)果。
性質(zhì)2 (溢出原則)假設(shè)M是一個非標準的一階算術(shù)模型,aˉ∈M是一組給定的有窮參數(shù),φ(v,aˉ)是一個標準一階算術(shù)公式。如果對于任意自然數(shù)n,都有Mφ(n,aˉ),那么一定存在一個M中的非標準元 b,使得
證明:假設(shè)不存在這樣的非標準元,即對于所有M中的非標準元b,都沒有M?i≤bφ(i,aˉ)。
驗證,對于任意M中的元素c,有?y≤cφ(y,aˉ)→?y≤c+1φ(y,aˉ)。當c是標準自然數(shù)時,上述命題顯然成立。又根據(jù)假設(shè),如果有?y≤cφ(y,aˉ),那么c一定是標準的,那么由標準自然數(shù)的性質(zhì)可知c+1也一定是標準的。
根據(jù)上述論述,就會有
性質(zhì)3 假設(shè)M是一個非標準一階算術(shù)模型,S是一個M上的部分(全)滿足類,φ(v0,…,vn)是只帶有自由變元v0,…,vn的標準一階算術(shù)公式,那么對所有的M中的元素a,
證明:對標準一階算術(shù)公式φ的復雜度施歸納,由滿足類的定義與賦值函數(shù)的性質(zhì)易得。
首先證明定理4a。
命題3 假設(shè)模型M是一個可數(shù)的非標準一階算術(shù)模型。如果M上存在一個歸納部分滿足類,那么M是遞歸飽和的。
證明:假設(shè)S是M上的一個歸納部分滿足類,p(v)是M上的遞歸型,不失一般性地,可以假設(shè)p(v)中只帶有一個自由變元且p(v)中不帶參數(shù)。因為p(v)是遞歸的,所以存在M中的元素b,使得p(v)被b編碼。那么對于任意標準自然數(shù)n,我們都有
因為S是可歸納的,根據(jù)溢出原則,M中一定存在非標準元c,使得
根據(jù)性質(zhì)3,任意M中的元素d,只要d滿足上述公式,那么d就實現(xiàn)p(v)。
接下來證明定理4a的另一個方向。
引理1 如果模型M是一個可數(shù)的非標準算術(shù)模型,那么存在可數(shù)模型N使得N是M的初等擴張并且N上有一個歸納部分滿足類。
證明:令ˉM=M∪{ca∶a∈M},其中ca是新的常元符號。再令T是如下理論:
其中,φ是標準的一階算術(shù)公式。
首先驗證T是一致的。
取T的有窮子理論T′,使得T′中包含的任意公式θ的哥德爾編碼都小于某個自然數(shù)n,定義M的子集 S′如下
其中,令iθ表示出現(xiàn)在θ中的自由變元的最大指標。顯然,S′在M中可以被一個標準一階算術(shù)公式定義,所以(M,S′)滿足擴張后語言下公式的歸納法,又因為所有哥德爾編碼小于給定n的公式構(gòu)成的集合對子公式封閉,所以(M,S′)滿足T′,再根據(jù)緊致性定理,就得到了T是一致的。
令(N,S″)是T的模型,N是可數(shù)的。根據(jù)T的定義,N是M的初等擴張。接下來只需證明存在N中非標準元b,使得S″限制在<b上是一個歸納部分滿足類。
根據(jù)定義,對于任意標準自然數(shù)n,都有
又因為這是一個擴張后語言下的公式,而(N,S″)滿足所有擴張后語言下公式的歸納法,所以溢出原則對這個公式有效。所以,存在N中的非標準元b使得
令 S={(φ,a)∶φ<a (φ,a)∈S″}。顯然,S在(N,S″)中是可定義的,所以(N,S)滿足歸納公理。這樣,S就是N上的一個歸納部分滿足類。
命題4 如果M是一個可數(shù)的一階算術(shù)模型并且M是遞歸飽和的,那么M上一定存在一個歸納部分滿足類。
證明:根據(jù)定理3,模型M是華麗的。而“存在一個歸納部分滿足類”可以表示為
其中,LS-IND表示擴張后語言LA∪{S}下的歸納公理。(*)中的無窮合取都是遞歸的,所以這些無窮合取等價于一個公式,所以(*)等價于一個公式,根據(jù)引理1可得Th(M)+(*)是一致的,又根據(jù)華麗性的定義,M滿足(*),也就是M上存在一個歸納部分滿足類。
類似地,可以證明定理4b如下。
命題5 假設(shè)M是一個可數(shù)的非標準一階算術(shù)模型。如果M上存在一個歸納T-集合,那么M是遞歸飽和的。
證明:假設(shè)S是M上的一個歸納T-集合,p(v)是M上的遞歸型。類似命題3可以得到存在M中的非標準元c,使得
又根據(jù)定義,T-集合中的都是標準的一階算術(shù)語句,所以對于任意的自然數(shù)n都有Mφn(c,aˉ)。這樣我們就找到了一個c使得遞歸型p(v)在M中被實現(xiàn)。
引理2 如果M是一個可數(shù)的非標準一階算術(shù)模型,那么存在可數(shù)模型N使得N是M的初等擴張并且N上有一個歸納T-集合。
證明:令T=Th(ˉM)+LS語言下公式的歸納法+?y(S(φ,y)?φ(y)),其中φ是標準的一階算術(shù)公式。類似引理1可得。
命題6 如果M是一個可數(shù)的算術(shù)模型并且M是遞歸飽和的,那么M上一定存在一個歸納T-集合。
證明:“存在一個歸納T-集合”可以表示為
其中,LS-IND表示擴張后語言LA∪{S}下的歸納公理。與命題4類似,(**)是一個公式。再根據(jù)引理2,可知(**)與Th(M)是一致的。最后,由華麗性的定義可得,M上存在一個歸納T-集合。
利用上一小節(jié)的結(jié)果,本節(jié)將證明全滿足類、部分滿足類與歸納-集合在非標準算術(shù)模型上的不可定義性,特別地,這些證明將不依賴于對角線引理。此外,本小節(jié)還將討論上述集合的相對可定義性。
如果有對角線引理,根據(jù)塔斯基真不可定義定理和性質(zhì)3,很容易得到部分滿足類在算術(shù)模型上的不可定義性結(jié)果。
定理5 假設(shè)M是一個可數(shù)的非標準一階算術(shù)模型,S是一個M上的部分滿足類,那么S在M中不能被標準算術(shù)公式定義。
證明:假設(shè)S可以被標準一階算術(shù)公式φ(x,y,ˉa)定義,ˉa∈M是一組給定的有窮參數(shù)。根據(jù)性質(zhì)3,對于所有的標準算術(shù)公式ψ,都會有
其中,[ˉa]是ˉa的編碼。這與塔斯基算術(shù)真不可定義定理矛盾。
因為塔斯基的算術(shù)真不可定義定理本質(zhì)上依賴于對角線引理,所以在定理5的證明中,對角線引理是本質(zhì)的,如此,定理5可以被視作對角線引理的一個直接推論。
下面以歸納-集合為例,給出一個不依賴于對角線引理的不可定義性的證明。
定理6 假設(shè)M是一個可數(shù)的非標準一階算術(shù)模型,S是一個M上的歸納T-集合,那么S在M中不能被標準算術(shù)公式定義。
證明:假設(shè)S可以被一個帶有有窮參數(shù)a0,…,an的標準一階算術(shù)公式定義。令K是上述有窮參數(shù)的斯克倫閉包,那么K是M的初等子模型,所以S限制在K上是一個K上的歸納T-集合,根據(jù)定理4b,K是遞歸飽和的,但是由性質(zhì)1,K不可能是遞歸飽和模型,這就導致了矛盾。
歸納部分滿足類和全滿足類在算術(shù)模型上的不可定義性可以用同樣的證明思路獲得。
定理7 假設(shè)M是一個可數(shù)的非標準一階算術(shù)模型,S是一個M上的歸納部分滿足類或全滿足,那么S在M中不能被標準算術(shù)公式定義。
接下來的定理表明,盡管全滿足類、部分滿足類和T-集合都是在可數(shù)的非標準一階算術(shù)模型上不可定義的,但他們之間存在著某種相對可定義性。先給出一些必要的預備知識。
定義7 假設(shè)M和N是兩個一階算術(shù)模型,稱M是N的尾節(jié)擴張當且僅當N是M的子模型并且N對于M的序關(guān)系向下封閉。如果N是M的真子集,則稱N是M的真尾節(jié)擴張。
定理8 (麥克道威爾-施佩克爾定理(MacDowell-Specker Theorem))任意一階算術(shù)模型都有一個真的初等尾節(jié)擴張。
更多算術(shù)模型尾節(jié)的細節(jié),可以參看凱伊(Kaye)的專著[6]。
定理9 假設(shè)M是一個可數(shù)的非標準一階算術(shù)模型。如果M上存在一個歸納部分滿足類S,那么M上一定存在另一個歸納部分滿足類S′使得S′在模型(M,S)中可定義。
證明:根據(jù)擴張后語言下的麥克道威爾-施佩克爾定理,存在(N,S″)使得(N,S″)是模型(M,S)的初等尾節(jié)擴張。根據(jù)定義很容易驗證,S″是 N上的歸納部分滿足類。令S′等于S″限制在M上。因為(N,S″)是(M,S)的初等尾節(jié)擴張,所以 S′在(M,S)中可定義并且是歸納的。
接下來只需證明S′是一個部分滿足類。依定義驗證,其他的條件都是平凡(trivial)成立的,唯一的困難在于帶有量詞的情況。這里,只處理存在量詞,全稱量詞可以類似得到??紤]公式Φ(n,X)定義如下
顯然,標準的一階算術(shù)語句φ使得Φ(φ,S′)成立,而φ被標準自然數(shù)編碼。這樣我們就有
分析上述定理的證明,很容易發(fā)現(xiàn)將定理的條件改成“M上存在一個全滿足類”或者“M上存在一個T-集合”,結(jié)果依然成立。這樣,可以將定理8推廣到更一般的結(jié)果上。
定理10 假設(shè)M是一個可數(shù)的非標準一階算術(shù)模型。如果X是M上的一個不可定義集并且M上存在X可以推導出M是遞歸飽和的,那么M上一定存在一個歸納部分滿足類S使得S在模型(M,X)中是可定義的。
證明:由定理4a和定理9可以直接得到。
一個自然的問題是,除了可以推導出模型遞歸飽和性的不可定義集,是否存在別的不可定義集,使得存在一個在擴充模型上可定義的歸納部分滿足類。
接下來我們給出一個否定的結(jié)果,證明在用科恩力迫(Cohen forcing)構(gòu)造的不可定義集擴充得到的模型上不存在可定義的歸納部分滿足類。通過這個結(jié)果,我們似乎有理由相信能夠推出模型的遞歸飽和性是使得某個歸納可滿足類在擴充后模型上可滿足的必要條件。
定義8 給定一個模型M,令2<M是由可定義函數(shù)p∶{0,…,a}→{o,1}構(gòu)成的集合,其中a是M的元素。
(1)一個集合D?2M是稠密的當且僅當對于任意p∈2<M存在一個q∈D使得p?q。
(2)一個集合G?<M是脫殊的(generic)當且僅當
a.對于所有的G的元素p,q,p和q都可比;
b.對于所有的G的元素p和所有的M的元素a,p限制在a上屬于G;
c.對于所有的可定義稠密集D,G和D的交非空。
(3)給定一個G是脫殊的,令XG={x∈M∶?p∈G(p(x)=1)}。稱XG是M的一個脫殊子集。
下列性質(zhì)可以在奧德弗雷德(Odifreddi)的專著[7]中找到,這里省略具體證明。
性質(zhì)4 假設(shè)M是一個一階算術(shù)模型,則有:
(1)如果M是可數(shù)的,那么M上有一個脫殊集。
(2)脫殊集在模型M中是不可定義的。
(3)脫殊集在模型M中是歸納的。
(4)如果X是M的一個脫殊子集,那么存在一個M的不可定義子集Y,使得Y在模型(M,X)中可定義,但同時X在模型(M,Y)中不可定義。
從性質(zhì)1和定理4a我們可以得到并非所有的可數(shù)非標準算術(shù)模型上存在一個歸納部分滿足類,又由性質(zhì)4中的(1)得所有可數(shù)的算術(shù)模型上都存在一個脫殊集。這樣我們就可以得到以下的結(jié)果。
性質(zhì)5 如果M是一個可數(shù)的非標準一階算術(shù)模型,那么M上的所有歸納部分滿足類都不是脫殊的。
證明:假設(shè)S是M上的一個歸納部分滿足類,并且S是脫殊的。根據(jù)擴張語言下的麥克道威爾-施佩克爾定理,存在(N,S′)使得(N,S′)是(M,S)的一個初等尾節(jié)擴張。給定一個 N中的非標準元 a,令 S″等于S′限制在<a上,根據(jù)尾節(jié)擴張的性質(zhì),S″在 N中是可以被編碼的,令 b是 S″的編碼。令 K是M∪{b}的斯克倫閉包。很容易驗證S″可以被拓展成一個集合G,使得G在K中是脫殊的。又根據(jù)力迫的一般性質(zhì),我們可以得到模型(K,G)是模型(M,S)的一個初等擴張,所以G是K上的一個歸納部分滿足類。另一方面,根據(jù)構(gòu)造可知,K是一個有窮生成模型的共尾擴張,類似性質(zhì)1可以證明這樣的模型不是遞歸飽和的,又由定理4a可知,K上不存在歸納的部分滿足類,這就導出了矛盾。
下列的結(jié)果表明,在可數(shù)的算術(shù)模型看來,歸納部分滿足類的不可定義性要“強于”脫殊集的不可定義性,這也在某種程度上說明了“真”的定義需要極高的要求。
定理11 假設(shè)M是一個可數(shù)的非標準一階算術(shù)模型。如果G是M上的一個脫殊子集,那么不存在M上的歸納部分滿足類S使得S在模型(M,G)中可定義。
證明:假設(shè)存在這樣的歸納部分滿足類,可以利用性質(zhì)5一樣的思路來構(gòu)造矛盾。
定理12 假設(shè)M是一個可數(shù)的非標準一階算術(shù)模型。如果M上存在一個歸納部分滿足類S,那么M上一定存在一個脫殊子集G使得G在模型(M,S)中可定義。
證明:只需要驗證“存在脫殊集”可以被形式化到模型(M,S)中。
結(jié)合性質(zhì)4中的(4)和定理12,我們還能進一步得到某種歸納部分滿足類上的切分性質(zhì)。
推論1 假設(shè)模型M是一個可數(shù)的非標準一階算術(shù)模型。如果M上存在一個歸納部分滿足類,那么一定存在一個M上的不可定義子集X使得在模型(M,S)中可定義,但是S在(M,X)中不可定義。
而根據(jù)定理11,我們還可以得到推論1的加強版。
推論2 假設(shè)M是一個可數(shù)的非標準一階算術(shù)模型。如果M上存在一個歸納部分滿足類S,那么一定存在一個M上的不可定義子集X使得X在模型(M,S)中可定義,但是不存在M上在模型(M,X)中可定義的歸納部分滿足類。
通過繼續(xù)克蘭、科特拉爾斯基和克拉熱夫斯基的工作,得到了如下結(jié)果。
定理13 如果M是一個可數(shù)的非標準一階算術(shù)模型,那么下列命題兩兩等價:
(1)M是一個遞歸飽和模型;
(2)M上存在一個全滿足類;
(3)M上存在一個歸納部分滿足類;
(4)M上存在一個歸納T-集合。
在此基礎(chǔ)上,本文推廣塔斯基的結(jié)果,證明了全滿足類、部分滿足類、部分歸納滿足類以及歸納-集合在可數(shù)的非標準算術(shù)模型上都是不可定義的。需要注意的是,本文只證明這些集合在可數(shù)算術(shù)模型上的不可定義性,這并不能直接推導出塔斯基算術(shù)真不可定義定理。而通過對上述集合的相對不可定義性的分析,發(fā)現(xiàn)對于可數(shù)非標準算術(shù)模型而言,集合在模型上的存在性可以推出模型的遞歸飽和性這一性質(zhì),是使得某個歸納部分滿足類在以這個集合做擴張的模型上可定義的充分條件。進一步地,證明了歸納部分滿足類在用科恩脫殊集做擴張得到的模型上是不可定義的,所以我們有理由猜測集合的存在性可以推導模型的遞歸飽和性也是保證歸納部分滿足類可定義的必要條件。
最后,本文將以一些開問題作為結(jié)束。
問題1 給定一個可數(shù)的非標準一階算術(shù)模型,在上面是否存在別的歸納不可定義集使得某個歸納部分滿足類在用上述不可定義集擴張得到的模型上是可定義的?
斯莫林斯基(Smorynski)證明了存在滿足上述要求的不可定義集[8],但斯莫林斯基的結(jié)果不是歸納的,是否存在這樣的歸納不可定義集仍是個開問題。
問題2 將定理9結(jié)論中的歸納部分滿足類換成全滿足類或者-集合,定理9是否依然成立?