和谐性质及其应用Ⅱ

D0I:10.13374/i.1ssn1001053x.1990.05.016 第12卷第5期 北京科技大学学报 Vol.12 No.5 1990年9月 Journal of University of Science and Technology Beijing Sept.1990 和谐性质及其应用II 孙晓蓝 摘要：KimB.Bruce于1978年提出了三价逻辑L(Q)的逻辑公理系统。 H.J,Kcis】r在1971年发表了无穷逻辑中的校型论一书，提出了无穷逻辑的公理系统，文中 钻金上迟两种逻辑系统的恩想，应用了无穷逻辑中的模型论一书中介绍的和谐性质的方法， 建立了无穷逻辑中的二阶语言工如1如(Q)的公理系统及模型理论，这部分主要是对1”1(0) 中的省略型定理及素模型定理的证明。 关键词：完备现论，可数片断，和选性质，理想模型，素模刑 Consistency Property and Its Application II Sun Xiaolan ABSTRACT:Kim B.Bruce gave a system of axioms for sccond order logic L(Q).H.J.Keisler in 1977 published a book called (Model Theory for Infinitary Logic)to give a system of axioms for infinitary logic.This article combines the two ideas of the two systems of axioms,applying the consistency property introduced by the book (Model Theory for Infinitary Logic)to give a system of axioms and model theory for infinitary second order logic Lww(Q).This part of the article is mainly the proofs of omittirg type theorem for Lw,w(Q)and prime model theorem for Lwiw(Q). KEY WORDS:complete theory,countable fragment,consistency property, ideal model,prime model 1987-11-10收移 数学力学系(Department of Mathematic and Mechanic) ·495·

第 卷第 弓 期 年 月 北 京 科 技 大 学 学 报 ， 。 。 和谐性质及其应用 孙 晓 蓝 ’ 摘 要 于 年提出了二 价逻辑乙〔。 的逻辑公 理系 统 。 在 年发 表了 无穷逻辑中的模型 论 一 书 ， 提 出了 无穷 逻辑的公理 系统 ， 文中 结 合 卜述 两 种 逻辑 系统 的 思 想 ， 应 用 了无 穷 逻辑 中的模型 论 一 书中介绍 的和 谐 性 质 的 方 法 ， 建立 了 无穷 逻辑 中的二 阶 语 言 ” 。 的公 理 系统 及 模型 理论 。 这 部分 主要 是 对五二， ， ， 哟 中的 省略型 定 理及素模型 定 理 的证 明 。 羔键 词 完备钾 论 可 数 片断 ， 和 诺性质 ， 理想模型 ， 素模 刑 ” ” ， 又 ， 》 ， 《 · 》 父 脚 。 · 卜 。 手 田 田 ， ， 手 · ， ， 几 一 一 收稿 数 学 力学 系 ， 卜 。 。 急 ， DOI ：10．13374／j ．issn1001－053x．1990．05．016

1Lw,w(Q)中的省略型定理 定理1.1（省略型定理）：令L(Q)是Lw1w(Q)的一个可数片断，令T是L4(Q)的一个 命题集，对每一n<,中，(x1,…,x)是L4(Q)的公式集合，自由变元在{x,:1<i一r.} 中，假设： (1)T有一个模型(A,q), (2)对Vn<w和所有L(Q)巾的公式(x1,…,x,),如果TU{3x1,x,.种}有 一个榄型，那么存在b∈中，使T{3x1,,x,.（中八)}有一个模型。 那么有模型(A,q):(A,9)满足T,(A,q)满足AVx1,…x,V中。 证明：令M(Q)是把L(Q)中所有公式的有限多白由变元换为C中元素后得到的所有 公式的集合(LUC=M如文献C1)中所定义)。令S是所有形式如下的S,的集合： S,=SnT刂{V中(C,,C,):n<w,c,∈C}记{VΦ.(c1…,c,.):m<w, c,∈C}为g。其中S。是M(Q)中的命题集。S。=SU{Qx中1(x),,Qxφ，(x),~ Qx.+1(x),,~Qxφ+m(x)}U{p1(c)lc∈t:}U…U{p,(c)|c∈t.}U{~p.+1 (c)!C∈t,1}l…月{~p.+.(c)川c∈t.+n}。S=SgU{Qxp(x),,~Qxp.m (x)},Sn只有C中有限多个元素。t,∩t,=中，t,gs,主j,1i,j≤n:,t,n+1s≤j n+m是(C)中（参考〔1）)S,型集合。C={c/c在5o中出现，c∈C},t:∩C=中，1≤ 行n+m。 这里要求SoUT有模型，|C-(c1t1…t,)=w。 下面证明S是一个和谐性质。 (c1)若p,~p∈5，，由SUT有模型，没有P,~p∈SUT。由~p的形式， ~p使a,只能有p∈0，~p∈SUT,从而0为V(C,1,…,C,)的形状，由s,定义知， 这时TU{~p(C,、·,C,)}有模型。由定理所设(2)，可知存在pF中，使TA3x,1, x,（~p(x,1’",x,)AP(x,1,,x,))有模型，矛盾。没有p,~pES,(C1)成立。 ~p,ヨxp,八中，V×p,Qxp(x),~Qxp(x)属于s,时，由于它们没有o中公式的形 式，必属于soJT。由S。刂T有模型，象完金性定理证明一样可证(Cz),(C3),(C),(Cs), (Ca),(C,),(C)成立。我们例证(C8): (C)~Qxp(x)∈s:,由上述~Qxp(x)∈sg刂To,取s.,使s.∩C=中，易见s.存作，证明 sJTU{~p(c)1rC,}有模型。则有TAA6一V1.~p1c)Vp.e)VV p..(c)Vp (c)V..VV (-p.(c)/p..(c)V..Vo..(c)/V rt。ns。 c.-t,p1(c) V…/p.m(c)Vp(c)恒真。这里s6=s。-U。{~p(c),p1(),…,p.(c). ~p。1,~pwm(c)}。,x)=~p1(x)Vp.1(x)V…/n(x)'p(x),…,的，(x) ·196·

， 中的省略型定理 定 理 省 略型定理 令 ， 旧 是 二 二 的一 个可数片断 ， 令 是 ， 的一 个 命 题集 ， 对 依一 ” 功 ， 巾 ， ， 一 ， ， 是 ， 的公式 集合 ， 自由变元 在 ‘ ， 了 一 尸 。 中 ， 假设 有一 个模 型 ， 口 ， 对 和 所有 ， 旧 中的公 式功 ， … ， 二 ， ， 如 果 日 习 ， … ， 功 右 一 个 模型 ， 那 么存 在苗任 小 ， 使 〕 ，， … ， 尸 护八妇 有一 个模型 。 那 么有模 型 ， 妇 ， 妇 满 足 ， ， 满 足 八 ， ” · 二 ， 小 。 。 证 明 令 ， 是 把 ， 中所有公式 的有限 多 自由变元换 为 中元素后 得到 的所 右 公 式 的 集合 二 如文献 〔 〕 中所定 义 。 令 是 所有形式 如 下的夕 ‘ ，集合 、 ” 。 ’ 一 ’ 由 ， ， ， … ， ， 。 ” 功 ， “ 记 巾 ，· … ， 二 ” ， ， ‘ 〔 为。 。 其 中 。 是 ， 中的 命 题 集 。 。 二 言日 二 价 二 ， … ， 二 功 ， 一 功 ， 、 ， … ， 一 价 。 。 二 尹 〔 工 口 … 必 ， 〔 一 钾 任 。 ， ， … 一 功 。 任 ， 、 。 扩 一 二 功 ， … ， ‘ 办 。 十 ， ， 。 只 有 「飞 有限 多个元 素 。 ‘ 自 ， 二 功 ， ‘ 住叮， ， ’今 ， 了 ￡ ， 镇 。 ‘ ， ，， ” 炙 了 。 ， 是 ‘ 参考〔 〕 夕 。 型集合 。 在 。 中出现 ， 〔 ， ‘ 自 必 ， 犷 一 叮 十 脚 。 这里要求 。 有模型 ， 】 一 ， 工 ’ ， 一 忆， ， 二 。 下面证明 是 一个和 谐性质 。 若 ， ， ， 〔 ‘ ， 由 。 有 模 型 ， 没 有 中 ， ， 厂夕 。 。 由 一 ， 的 形 式 ， 一 甲 健 ， 只 能有， 任叮 ， 一 甲 任 。 从而 为 巾 ， ，， … ， ， 。 的 形状 ， 由 “ ，定 义 知 ， 这 时 一 甲 ，， … ， ， 。 有模 型 。 由定理 所设 ， 可 知存 在 ‘ 小 使 八习 ， ， … ， ， 一 ‘ ， ， … ， ， 八户 ‘ ， ， … ， ， 有模型 ， 矛盾 。 ·，没 有尹 ， 一 甲 〔 成立 。 一 甲 ， 日 甲 ， 八巾 ， 二 甲 ， 甲 二 ， 甲 属 于 ‘ 时 ， 由于它 们没 有， 中公式的形 式 ， 必 属干 。 口 。 由 。 ’ 有模 型 ， 象 完 全性 定理 证 明 一样可 证 ， ， ， 。 ， 。 ， ， 。 成 立 。 我 们例证 。 ， 一 甲 〔 ， 、 ， 由上 述 一 ， 任 。 ’ 。 ， 取 。 ， 使 。 门 必 ， 易见 。 存 在 ， 证 明 「 口 日 一 ， 」。 〔 、 。 有 模 型 。 否 则有 八 八 、 言 一 甲 。 丫 势 ， 一 ， 丫 ” · 丫 ‘ 亡 一门 叼 。 甲 ， ， 丫 切 “ 丫 一 甲 ， 丫 甲 ， 丫… 切 ， 、 。 丫 甲 ， ‘ ‘ 。 几‘ 。 一 ‘ 。 一 ， 一 孟 。 … 丫 甲 ‘ ，。 。 丫切 。 恒真 。 这 里 、 言 。 一 日 一 甲 。 ， 甲 。 ， … ， 甲 。 。 一 尹 。 ， … ， 一 甲 ， 。 冬 。 幼 ， 二 一 甲 ， 丫 甲 ， · 丫 一 丫 ， ‘ ， 丫 卯 ， “ · ， 砂

=~p.Vp.+1(x)V…Vp+n(x)Vp(x),…,中+1(x)=pm+1(x)V…Vp+m(x)Vp(x)。 则由上述可推出T∧∧s。→Vx1(x)V…VVx中.+1(x)恒真，意味着T∧人s。→~Qx~ 的1(x)V…V~Qx~中.+1(x)恒真。又由Qxp1(x),…,Qxp,(x),~Qxp+1(x),…,~ Qx中+m(x),~Qxp(x)∈snUT,有T∧Λs0→Qx~中1(x)八…八Qx~的，(x)恒真。矛盾于 soUT有模型。s:U{~p(c)|c∈s。}∈s。(Cg)成立。 (c)证明略。 (cg)(1)c=d∈s,由c=d不是形式为VD的命题知c=d∈soUT,由SoUT有模型， 易见soUTU{d=c}有模型，由此可知，S:U《d=c}∈s。 (2)c=t,p(t)∈s:,若p(t)∈o与(cs)同理可证sUTU{p(t)}有模型(A,q): (A,q)满足p(t),t=C得到：(A,g)满足p(c)。sUTU{p(c)}有模型，即 s:U{p(c)}∈s。 若c=t,p(t)∈TUs,由TUso有模型易知，TUsU{p(c)}有模型，∴s,U{p (c)}∈s. (3)设t是任意基本项，取不在sa及t中出现的C,中的c,由TUso有模型可证TUsU {c=t}有模型。因否则有TUso→(c=t)恒真推出TUso→~(t=t)恒真(，c不在s0及 t中出现)与TUs有模型矛盾。.sU{c=t}∈s,(C)成立。 到此为止证明了s是一个和谐性质，由s定义知TU{V中.(c1,,c,):n<w,c,∈C} 有模型，凡每一元素是C的元素的解释，记为(A,q),则有(A。,q)满足T,(A,q)满 足AYx1…Vx,V中(x1,…,x,),这里(Ao,9o)是(A,q)到L的归约，证完。 2LW,w(Q)中的素模型定理 定义：令L(Q)是L1(Q)的一个可数片断。L4(Q)中的理论T被称为完备的当仅当 它是L4(Q)中的一个最大和谐理论。 由L4(Q)中的完全性定理，T是La(Q)中的一个完备理论当仅当T是L(Q)中某模型在 L4(Q)中所满足的所有的命题的集。下面设T是工(Q)中的完备理论。 一个公式p(×1,…,x)∈L4(Q)与T和谐当仅当T满足3x1…xp(x1,…,x)。一个 公式集合s(x1,…,x.)与T和谐当仅当T满足3x1…xn八s(x1,…,x)。 L4(Q)中一个公式P(x1,…,x)被称为对T完备的，当仅当p(x1,…,×,)∈L(Q), p与T和谐并且对L4(Q)中每一个公式中(x1,…,x.):或T满足p→冲或T满足p→~中。 L4(Q)中一个公式p(x1,·,￥)被称为对T不可完备化的，当仅当p与T和谐且没有 L4(Q)中对T的完备公式Q(x1,…,x):T满足Q→p。 La(Q)中一个公式集少，(x1,…,x)被称为一个对T的型，当仅当T有一个模型(A,9) 和A的n元组：a1,…,a使中={p(x1,…,x,)∈L4(Q):(A,q）满足p〔a1,…,a门}。 文中模型均指Lw1和(Q)中公理的理想模型。这时称(A,q)中的n元组<a1,…,a>实现型 少。T的一个模型(A,q)被称为实现一个型中(x1,…,×)当仅当A中某n元组<a1,…,a.> 实现中。否则称〈A,q)省略型中(x1,,x)。 引理A:令I是一个至多可数集，对每-i∈I,中：(x1,…,x,)是一个不包含对T的完备 公式的型，那么T有一个可数模型省略每一个型：，∈I。证明略。 ·497·

” 势 。 切 。 、 ， 二 … 甲 。 。 中 二 ，一 ， 叻 。 、 ， 中 。 、 二 … 。 。 戈 中 。 则 由上 述可推 出 八 八 。 功 ， … 丫 沪 。 、 恒 真 ， 意 味着 八 八 。 ， 一 二 一 功 ， 二 … 一 一 叻 。 ， 二 恒真 。 又 由 甲 ， 二 ， … ， 沪 。 ‘ ， 一 尹 ， ‘ ， … ， 一 护 。 ， ， 一 二 尹 任 。 日 ， 有 八 八 。 ， 劝 ， 八… 八 功 。 恒真 。 矛盾 于 。 日 有模 型 。 ， ‘ 一 甲 任 。 任 。 。 成立 。 证 明 略 。 。 任 ， 由 。 了不是形 式为 小 的命题 知。 任 。 ， 由 。 有 模型 ， 易见 。 口 日 。 有 模 型 ， 由此 可知 ， ‘ 任 。 。 二 ， 甲 任 ‘ ， 若 沪 任 与 同理 可证 。 日 沪 有模型 ， ， 。 满足甲 ， 得到 ， 叮 满足， 。 。 势 有模型 ， 即 沪 〔 。 若 二 ， 切 任 口 。 ， 由 口 。 有模型 易知 ， 口 。 甲 有 模 型 ， ’ ， ‘ 任 。 设 一 是 任意基 本项 ， 取不 在 。 及 中出现的 中的。 ， 由 。 有模型可证 “ 。 “ 二 有模型 。 因否则有 。 ， 一 。 二 恒 真推 出 。 ， 一 恒真 ，’ 。 不在 “ 。 及 中出现 与 。 有模型矛盾 。 ‘ 〔 ， 。 成立 。 到 此为 止证 明了 是一个和 谐性 质 ， 由 定义 知 日 小 。 。 ， ， … ， 。 ， ， “ 任 有 模型 ， 且每一元素是 的元 素 的解释 ， 记 为 ， ， 则有 。 ， 。 满足， ， 。 ， 满 足 户 “ ‘ … “ ， 。 必 ， ，， … ， ‘ ， 。 ， 这里 。 ， 。 。 是 ， 。 到 的归约 ， 证完 。 中的 素模型定理 定义 令 ， 是 ，二 的一 个可数片断 。 ， 中的理 论 被 称为完备的当仅当 它是 ， 中的一个最大和谐理 论 。 由 ， 中的完全性定理 ， 是 ， 中的一个完备理 论当仅当 是 ， 中某模型在 ， 中所满足 的所有的命题 的集 。 下面设 是 ， 中的完备理论 。 一个公式甲 ，， … ， 。 〔 ， 与 和谐当仅 当 满足习 …‘ 。 势 ， … ， ‘ 。 。 一个 公式集合 二 ， … ， 。 与 和谐当仅当 满足日， 一 。 “ “ ， … ， 。 。 ， 旧 中一个公式甲 ， … ， 二 。 被称 为对 完备 的 ， 当仅 当甲 二 ， ， … ， 二 。 〔 ， ， 中与 和 谐并且对 ， 中每一个公式功 二 ，， 一 ， 。 或 满足 甲” 叻或 满足 甲” 一 沪 。 ， 中一个公式伊 二 ， … ， 二 。 被称 为对 不 可完备化 的 ， 当仅当甲 与 和谐且 没有 月 中对 的完备公式 ，， … ， “ 二 满足 ” 甲 。 ， 中一个 公式 集少 ‘ ，， … ，二 。 被称 为一 个对 的型 ， 当 仅当 有一个模型 ， 妇 和 的 元组 ，， … ， 。 使少 甲 二 ， 一 ， 二 。 任 ， ， 满足势〔 ， ， … ， 。 〕 。 文 中模型 均 指 。 中公理 的理 想模型 。 这时 称 ， 妇 中的 元组 ‘ ，， … ， 。 ，实现型 由 。 的一个模 型 ， 被称 为实现一 个型少 二 ， … ， 二 。 当仅当 中某 元组 “ ， … ， “ 。 》 实现少 。 否则称 ， 砂 省 略型 少 ， … ， 。 。 引理 令 是一个至 多可数集 ， 对每一 任 ， 小 ‘ ， ， … ， 二 是一 个不包含对 的完备 公式 的型 ， 那 么 有 一个可数模型省略每一 个型 小 ‘ ， ￡任 。 证明略

引理B:T有一个可数模型（A,g),使对Vn<ω，(A,9)中你一n元组a1,…a。或满 足一个完备公式或满足一个对T的不可完备化公式。 证明略。 定义：设(A,q),(B,r)是两个任意模型。∫是A到B上的1一1映射，我们说(A, 9),(B,r)是对L4(Q)语法同构的，当仅当存在A到B上的1一1映射f满足：对任意p(x1, ,x,)∈L4(Q)有(A,9)满足p〔a:,,a)当仅当(B,r)满足p〔fa1,…,fa,这里a,∈ A,fa,∈B。 定义：令(A,q),(B,r)是两个理想模型。(A,q)被称为是(B,r)的初等子模型， 记为(A,q)<(B,r),当仅当ACB且对L(Q)中每一公式P(×1,…,x)(有有限多自由 变元)及A中所有n元组a1,…,a.有：（A,q)满足p〔a1,…,a.〕当仅当(B,r)满足 p〔a1,",an。 我们称(A,g)可初等嵌入(B,r),当仅当(A,q)语法同构于(B,r)的某个对L(Q) 的初等子模型。我们说(A,g)是T的一个素模型，当仅当(A,q)是T的模型且(A,g)可初 等嵌人到T的每一个模型中。 定理2.1(1)(A,q)是T的一个素模型，当仪当(A,q)是T的一个可数模型且(A,9) 的每一n元组满足一个对T的完备公式。 (2)T的任意两个素模型语法同构。 (3)T有一个素模型，当仅当没有对T的不可完备化公式， 证明略。 推论C:如果对每一n<@,T有最多可数多个模型，那么T有一个素横型。证明略。 定义：T是-·个⑩-范畴的，当仅当T的任意两个可数模型语法同构（对任意可数L(Q) 而言)。 推论D:T是@-范畴的当仅当T满足AVx1…x,V{p(x1,…,×,):p对T完备}=p0 (对任意可数L4(Q)成立)。 证明：“充分性”若T满足P,任取T的两个可数模型(A,q)和(B,r)可得(A,q)满 足P0,(B,r)满足Po,由定理2.1(1)(A,9),(B,r)都是素摸型，再巾(2)，(A,9)与 (B,r)语法同构。∴T是w-范畴的。 “必要性”证明略。 参考文献 1孙晓蓝.北京科技大学学报，1989；11(4)，382 2 Bruce Kim B.J.Symbolic Logic,1978;43(2):304 3 Ktisler H.J.Model Theory For Infinitary Logic,North Holland Amste- rdam.1971.Chapterl,Chapter2 4 Chang CC,Keisler H J.Model Theory,North Holland,Amsterdam.Cha- pter1-4.1973. 5 Shoenfield J R.Mathematical Logic.by Addison-Wesley Publishing Company, INC.Chapter1-4,1967 t498

弓‘理 少有一 个可数模型 ， 妇 ， 使对 二 ， 〔注 ， 的 中每一 。 元组 ，， 。 或 满 足 卜 一 个完备公式或满足一 个对 的不可完备化 公式 。 证 明 略 。 定义 设 ， ， ， 是 两 个任 意模 型 。 是 到 上 的 一 映射 ， 我们 说 ， ， ， ， 是对 ， 语 法 同构的 ， 当仅当存 在 到 上 的 一 映 射 满 足 对任意甲 、 ， … ， 。 〔 ， 有 ， 满足 尹〔 。 ， ， 一 ， 。 。 〕 当仅当 ， 犷 满足 沪〔 ， 一 ， 。 〕 ， 这 里 “ ‘ 任 ， 任 。 定义 令 ， 妇 ， ， 是两 个理 想模型 。 ， 妇 被称为是 ， 犷 的初等 子 模 型 ， 记为 ， 〔 ， ， ， 当 仅 当 仁 且对 ， 中每 一 公式 ， ， ， … ， 二 ， 有有 限多 白由 变元 及 中所有 ，元组 ， ， … ， 。 有 ， 满足 尹〔 ， … ， 。 〕当仅 当 ， 满足 尹〔 ，， 一 ， 。 〕 。 我们称 ， 妇可初等嵌入 ， ， 当 仅当 ， 妇 语 法 同构 于 ， 的某 个 对 ， 的初等子模型 。 我们说 ， 的 是 的一 个素模 型 ， 当 仅当 班 ， 妇 是 的模 型且 ， 妇 可初 等嵌人到 的每一 个模 型 中 。 定理 ， 是 的一 个素模 型 ， 当仅 当 ， 是 的一个可数模型且 ， 妇 的每一 元组满足一个对 的完备公式 的任意两 个素模型语 法 同构 。 有一 个素模 型 ， 当仅 当没有对 的不 可完备化 公式 证 明 略 。 推论 如果 对 每一 。 ， 有最 多可数多个模 型 ， 那 么 有一 个素模 型 。 证 明略 。 定义 是一 个。 一 范畴 的 ， 当仅 当 的任意两个可数模型语 法同构 对任意可数 而言 。 推论 ’ 是 。 一 范畴 的 当仅 当 满足 八 二 ，一 。 甲 二 ， … ， 二 。 中对’ 完 备 二 甲。 对 任意可数 ， 成立 。 证 明 “ 充分性 ” 若 满 足 尹。 ， 任取 的两 个可 数模 型 ， 妇 和 ， 可得 才 ， 满 足甲 。 ， ， 满 足甲 。 ， 由定理 ， ， ， 都是素模 型 ， 再 ， ， 叮 与 ， ， 语 法 同构 。 ， 是 。 一 范畴 的 。 “ 必 要性 ” 证明略 。 今 考 文 献 孙晓蓝 北京科技大学学报 ， ， 。 ， ， ， ， ， ， 一 。 。 子 一 ， 一 ， 龟