复旦大学：《数理逻辑》课程教学资源（讲义）第5章 一阶语言的结构和真值理论

第5章一阶语言的结构和真值理论 第1节一阶语言的结构 到现在为止我们都在讨论一阶逻辑的语法部分,所有的公式等等都可以被视为毫无 意义的字符串。现在我们开始讨论它们的“意义”。首先我们要解释语言中的每一个符号 的意义。粗略地说,这个解释是通过挑选“外部的”一个数学“结构”来完成的。结构挑 选的过程,也就是规定量词的范围,并指定谓词、函数、和常数符号意义的过程。 定义51.一个一阶语言的结构是一个定义域为语言中符号的函数,并且满足下列条件 1)%给量词符号指定一个非空集|a|,称作的论域 2)对每个n-元谓词符号P,都指定一个m-元关系PcwP;即P是由论域中 n-元组所组成的集合。 (3)对每个常数符号c,则都指定论域||中的一个元素c 14)对每个m-元函数符号f,都指定论域||上的一个n-元函数八; 即f:P→|。 注:选非空集作为论域是必要的,原因是我们在第??章中的有些公理对空集不适用 (哪一条呢?)。当然约定论域非空并无实质的损害,因为我们并不关心空集的性质。 例5.1.考察集合论的语言L={≈,∈},其中∈为一个二元谓词符号。尽管我们的初衷是 研究“真正的”集合论,但按照以上结构的定义,我们仍有很大的自由来挑选L的结构。 例如,令的论域||为全体自然数的集合N,符号∈在中的解释∈定义为“小于” 关系{(mn,m):m<灬}。下列冋题会帮助我们理解后面要谈到的真值理论。在上述解释下, 你怎样解读语句彐vyy∈x还有 vrvy3zvt(t∈z→(t≈rt≈y)? 1论域, universe,.也被译作“宇宙

第 5 章 一阶语言的结构和真值理论 第 1 节 一阶语言的结构 到现在为止我们都在讨论一阶逻辑的语法部分，所有的公式等等都可以被视为毫无 意义的字符串。现在我们开始讨论它们的“意义”。首先我们要解释语言中的每一个符号 的意义。粗略地说，这个解释是通过挑选“外部的”一个数学“结构”来完成的。结构挑 选的过程，也就是规定量词的范围，并指定谓词、函数、和常数符号意义的过程。 定义 5.1. 一个一阶语言的结构 A 是一个定义域为语言中符号的函数，并且满足下列条件： (1) A 给量词符号 ∀ 指定一个非空集 | A |，称作 A 的论域 1 。 (2) 对每个 n-元谓词符号 P，A 都指定一个 n-元关系 P A ⊆| A | n；即 P A 是由论域中 n-元组所组成的集合。 (3) 对每个常数符号 c，A 都指定论域 | A | 中的一个元素 c A。 (4) 对每个 n-元函数符号 f，A 都指定论域 | A | 上的一个 n-元函数 f A； 即 f A :| A | n→| A |。 注：选非空集作为论域是必要的，原因是我们在第?? 章中的有些公理对空集不适用 （哪一条呢？）。当然约定论域非空并无实质的损害，因为我们并不关心空集的性质。 例 5.1. 考察集合论的语言 L = {≈,∈}，其中 ∈ 为一个二元谓词符号。尽管我们的初衷是 研究“真正的”集合论，但按照以上结构的定义，我们仍有很大的自由来挑选 L 的结构。 例如，令 A 的论域 | A | 为全体自然数的集合 N，符号 ∈ 在 A 中的解释 ∈ A 定义为“小于” 关系 {(m, n) : m < n}。下列问题会帮助我们理解后面要谈到的真值理论。在上述解释下， 你怎样解读语句 ∃x∀y¬y ∈ x 还有 ∀x∀y∃z∀t(t ∈ z → (t ≈ x ∨ t ≈ y))? 1论域，universe，也被译作“宇宙”。 1

第1节一阶语言的结构 第5章一阶语言的结构和真值理论 下面我们将定义“一个闭语句σ在结构中为真”,记作σ。由于定义是对语句 归纳完成的,我们不可避免地要处理带有自由变元的公式。但如果变元可以随便变的话 讨论公式的真假是无意义的。例如,在结构(N,0)中如果变元x的值不确定,讨论x≈0 是否为真毫无意义。因此,我们需要一个赋值s告诉我们自由变元指的是哪些元素。令V 为所有自由变元的集合。一个赋值s就是一个从V到%的论域的函数,即s:V→|。 固定一个语言L。令φ为L中的一个公式,则为L的一个结构,s为一个赋值。我们 下面定义和s满足φ这个短语,记作(,s)=9。直观上说,“(,s)φ”的意思是 我们先把符号串φ里的谓词符号、函数符号和常数符号按照结构的规定来解释,把量 词的论域限制在集合||,把自由变元x解释成它的赋值s(x),从而把公式φ翻译成 个元语言中的数学陈述,而用我们数学知识我们知道所得到的陈述成立。精确定义如下 定义52 门以)项的解释。我们把赋值s扩展到项,令T表示所有项的集合。我们递归定义一个项 的赋值函数3:T小|如下 a)对每一个变元符号r,s(x)=s(x) b)对每一个常数符号c,3(c)=c2 c)如果t1,t2,…,tn是项并且∫是一个n元函数符号,则 5(ft2…tn)=f2(3(t1),3(t2)…,5(tn) 处理原子公式。 a)(2,s)≈t2当且仅当(t1)=8(t) b)对n元谓词符号P,(,s)}=Pt1t2…tn当且仅当((t1),3(t2)…,5(tn)∈P (3)其它公式的处理。定义 a)(,s)当且仅当和s不满足φ,记作(,s)≠φ。 b)(,s)}(y→v)当且仅当或者(,s)≠φ或者(,s)v。 c)(2,8)上Wry当且仅当对任何的d∈||,我们有(l,s)上φ,其中s为一个 由s、x和d诱导出来新的赋值函数,定义为 (y),如果y≠ 8a(y)= d,如果y=x 注

第 1 节 一阶语言的结构 第 5 章 一阶语言的结构和真值理论 下面我们将定义 “一个闭语句 σ 在结构 A 中为真”，记作 A |= σ。由于定义是对语句 归纳完成的，我们不可避免地要处理带有自由变元的公式。但如果变元可以随便变的话， 讨论公式的真假是无意义的。例如，在结构 (N, 0) 中如果变元 x 的值不确定，讨论 x ≈ 0 是否为真毫无意义。因此，我们需要一个赋值 s 告诉我们自由变元指的是哪些元素。令 V 为所有自由变元的集合。一个赋值 s 就是一个从 V 到 A 的论域的函数，即 s : V →| A |。 固定一个语言 L。令 φ 为 L 中的一个公式，A 为 L 的一个结构，s 为一个赋值。我们 下面定义 A 和 s 满足 φ 这个短语，记作 (A, s) |= φ。直观上说，“(A, s) |= φ”的意思是： 我们先把符号串 φ 里的谓词符号、函数符号和常数符号按照结构 A 的规定来解释，把量 词的论域限制在集合 | A |，把自由变元 x 解释成它的赋值 s(x)，从而把公式 φ 翻译成一 个元语言中的数学陈述，而用我们数学知识我们知道所得到的陈述成立。精确定义如下： 定义 5.2. (1) 项的解释。 我们把赋值 s 扩展到项，令 T 表示所有项的集合。我们递归定义一个项 的赋值函数 s : T →| A | 如下： (a) 对每一个变元符号 x，s(x) = s(x)。 (b) 对每一个常数符号 c，s(c) = c A。 (c) 如果 t1, t2, · · · , tn 是项并且 f 是一个 n 元函数符号，则 s(f t1t2 · · ·tn) = f A (s(t1), s(t2)· · · , s(tn))。 (2) 处理原子公式。 (a) (A, s) |=≈ t1t2 当且仅当 s(t1) = s(t2)。 (b) 对 n 元谓词符号 P，(A, s) |= P t1t2 · · ·tn 当且仅当 (s(t1), s(t2)· · · , s(tn)) ∈ P A。 (3) 其它公式的处理。 定义 (a) (A, s) |= ¬φ 当且仅当 A 和 s 不满足 φ，记作 (A, s) ̸|= φ。 (b) (A, s) |= (φ → ψ) 当且仅当或者 (A, s) ̸|= φ 或者 (A, s) |= ψ。 (c) (A, s) |= ∀xφ 当且仅当对任何的 d ∈| A |，我们有 (A, sx d ) |= φ，其中 s x d 为一个 由 s、x 和 d 诱导出来新的赋值函数，定义为 s x d (y) =    s(y), 如果 y ̸= x； d, 如果 y = x。 注： 2

第5章一阶语言的结构和真值理论 第1节一阶语言的结构 1.(c)的本意是把p(x)中的变元x用d来取代,非正式的写法为φ(d)。但严格讲这 样写没有意义,因为d不是我们语言中的符号。因此我们只有采用赋值的方法把变 元x赋值为d。有的教科书把它简记成φd。当我们概念清楚之后,例如在后面可 定义性的部分也会采用这种简记。 2.定义52是一阶逻辑真值理论的核心。它是由逻辑学家塔尔斯基1933年给出的。 3.对初学者来说首先要搞清楚我们是用什么在定义什么,或者说它是否是循环定义 答案是我们是用数学(元语言中)的知识来定义(对象语言中)一阶语句的真假。 例如,固定域的语言L={+,,0,1}。考察一阶语句g:a(x·x1+1)就φ本身 而言,它只是一个字符串,到现在为止尚不具有任何意义。只有当我们固定好L的 个结构以时,我们才能决定φ的真假。就φ而言,它在有理数域Q中为真,而 在实数域R中为假。至于为什么它在有理数域Q为真,则是我们的数学中背景知识 告诉我们的。因此我们是用数学中关于的知识来定义一个形式语句(或说一阶公 式)φ在中的真假,即a}φ 4.从上面的讨论我们可以看出用数学语言在这一点上比用自然语言要清晰。自然语言 中常用的例子为“雪是白的为真当且仅当雪是白的。 定义53.令r为一个公式集并且φ为一个公式。我们称I语义蕴涵φ,2记作r}φ,如 果对每一个结构和每个赋值函数s:V→|都有一旦和s满足r中的所有成员,则 和s也满足φp 定义5.3是本课程中最重要的概念之一。语义蕴涵的目标是严格定义“必然地得出” 这一概念。前面的语法蕴涵概念尽管非常精确,但人们多少会怀疑它是否过于依赖形式系 统的选取。而语义蕴涵则没有这一缺陷。因此一个“好的”推演系统从假设集I能“推” 出的命題应该不多不少恰恰是r语义蕴涵的那些命题,这就是我们后面要讲的所谓可靠 性和完全性。 我们在命题逻辑中曾用符号}表示过重言蕴涵,但从现在起,除非特别声明,符 号}只表示语义蕴涵。我们仍然沿用过去的一些约定,比如,我们用?卡φ来表示 {}φ;我们说两个公式φ和v是语义等价的3如果φv并且v卡φ。一个公式φ 被称为普遍有效的如果0卡φ,记作φ。4注意:公式φ是普遍有效的当且仅当对所有 的结构和所有的赋值s:V→|,和s都满足φ(为什么?)。因此普遍有效的公式 在一阶逻辑中与重言式在命题逻辑中的地位类似。 2语义蕴涵,英文为 logically imply,也被译为逻辑蕴涵,或说φ是r的语义后承 3语义等价,英文为 logically equivalent,也被译为逻辑等价。 4普遍有效的,英文为 valide。通常直译为“有效的

第 5 章 一阶语言的结构和真值理论 第 1 节 一阶语言的结构 1. （c）的本意是把 φ(x) 中的变元 x 用 d 来取代，非正式的写法为 φ(d)。但严格讲这 样写没有意义，因为 d 不是我们语言中的符号。因此我们只有采用赋值的方法把变 元 x 赋值为 d。有的教科书把它简记成 φ[d]。当我们概念清楚之后，例如在后面可 定义性的部分也会采用这种简记。 2. 定义 5.2 是一阶逻辑真值理论的核心。它是由逻辑学家塔尔斯基 1933 年给出的。 3. 对初学者来说首先要搞清楚我们是用什么在定义什么，或者说它是否是循环定义。 答案是我们是用数学（元语言中）的知识来定义（对象语言中）一阶语句的真假。 例如，固定域的语言 L = {+, ·, 0, 1}。考察一阶语句 φ: ∀x(x · x ̸≈ 1 + 1)。就 φ 本身 而言，它只是一个字符串，到现在为止尚不具有任何意义。只有当我们固定好 L 的 一个结构 A 时，我们才能决定 φ 的真假。就 φ 而言，它在有理数域 Q 中为真，而 在实数域 R 中为假。至于为什么它在有理数域 Q 为真，则是我们的数学中背景知识 告诉我们的。因此我们是用数学中关于 A 的知识来定义一个形式语句（或说一阶公 式）φ 在 A 中的真假，即 A |= φ。 4. 从上面的讨论我们可以看出用数学语言在这一点上比用自然语言要清晰。自然语言 中常用的例子为 ‘雪是白的’ 为真当且仅当雪是白的。 定义 5.3. 令 Γ 为一个公式集并且 φ 为一个公式。我们称 Γ 语义蕴涵 φ，2 记作 Γ |= φ，如 果对每一个结构 A 和每个赋值函数 s : V →| A | 都有一旦 A 和 s 满足 Γ 中的所有成员，则 A 和 s 也满足 φ。 定义 5.3 是本课程中最重要的概念之一。语义蕴涵的目标是严格定义“必然地得出” 这一概念。前面的语法蕴涵概念尽管非常精确，但人们多少会怀疑它是否过于依赖形式系 统的选取。而语义蕴涵则没有这一缺陷。因此一个“好的”推演系统从假设集 Γ 能“推” 出的命题应该不多不少恰恰是 Γ 语义蕴涵的那些命题，这就是我们后面要讲的所谓可靠 性和完全性。 我们在命题逻辑中曾用符号 |= 表示过重言蕴涵，但从现在起，除非特别声明，符 号 |= 只表示语义蕴涵。我们仍然沿用过去的一些约定，比如，我们用 γ |= φ 来表示 {γ} |= φ；我们说两个公式 φ 和 ψ 是语义等价的 3 如果 φ |= ψ 并且 ψ |= φ。一个公式 φ 被称为普遍有效的 如果 ∅ |= φ，记作 |= φ。4 注意：公式 φ 是普遍有效的当且仅当对所有 的结构 A 和所有的赋值 s : V →| A |，A 和 s 都满足 φ （为什么？）。因此普遍有效的公式 在一阶逻辑中与重言式在命题逻辑中的地位类似。 2语义蕴涵，英文为 logically imply，也被译为逻辑蕴涵，或说 φ 是 Γ 的语义后承。 3语义等价，英文为 logically equivalent，也被译为逻辑等价。 4普遍有效的，英文为 valid。通常直译为“有效的”。 3

第1节一阶语言的结构 第5章一阶语言的结构和真值理论 最后相信大家不会把(Q,s)}φ(还有后面马上定义的φ)和r卡φ搞混,虽 然都用了卡这个符号。有的教科书(例如安德顿[?])也会把(,s)}φ记作卡]并 且把卡φ记作 定理51.假定s1和s2为两个从V到||的赋值函数,并且它们在公式φ中所有自由出 现的变元上取值相同。则(,s)=p当且仅当(,s2)}g。 证明:固定结构。我们对公式φ施行归纳。假定赋值函数s1和s2在公式y中所有自由 出现的变元上取值相同。首先我们有 情形1:φ是一个原子公式Pt2…tn或t1≈t2。首先我们有对任意i≥1, 51(t1)=32(t1)。详细证明需要对项t施行归纳并要用到对赋值s1和s2的假设,我们 留给读者。因此(,s1)Pt1t2…tn当且仅当(1(t1),1(t2),…,31(tn)∈P当且仅当 (2(t1),52(t2),…,52(t1))∈P当且仅当(a,s2)Pt1t2…tn。当φ为t1≈t2时证明与此 类似 情形2和3:φ分别具有形式和a→β。我们把验证留给读者 情形4:φ具有形式xv。在此情形下在v中自由出现的变元至多是x加上在φ中自 由出现的变元。所以对任何的d∈|,诱导出的赋值函数(s1)和(s2)在中所有自由 出现的变元上取值相同。根据归纳假定和(s1)a满足ψ当且仅当和(s2)满足ψ。所 以%和s1满足φ当且仅当%和s2满足φ 推论51.对任何闭语句σ,或者 a)对所有函数s:V→,都有(al,s)}=σ;或者 b)对所有函数s:v→都有(,s)kσ 当情形(a)成立时,我们就称σ在以中为真,记作}σ;也经常使用下列短语:σ 在中成立;满足σ和α是σ的一个模型 推论5说明对闭语句来说,赋值函数是不重要的。类似地,如果公式y中仅有 个自由变元ω1,则对赋值函数来说,重要的只有它在n上的赋值。 例52.给定一阶语言L包含一个二元谓词符号P,一元函数符号f和一个常数符号c,考 察它的如下结构: (N,≤,S,0) 令s:V→N使得s(v) 即s(n1)=0,s(2)=1等等。什么是(fn3)?还有 s(fc)?结构w和赋值s满足下列公式吗? () Pcfa

第 1 节 一阶语言的结构 第 5 章 一阶语言的结构和真值理论 最后相信大家不会把 (A, s) |= φ （还有后面马上定义的 A |= φ）和 Γ |= φ 搞混，虽 然都用了 |= 这个符号。有的教科书（例如安德顿 [?]）也会把 (A, s) |= φ 记作 |=A φ[s] 并 且把 A |= φ 记作 |=A φ。 定理 5.1. 假定 s1 和 s2 为两个从 V 到 | A | 的赋值函数，并且它们在公式 φ 中所有自由出 现的变元上取值相同。则 (A, s1) |= φ 当且仅当 (A, s2) |= φ。 证明: 固定结构 A。我们对公式 φ 施行归纳。假定赋值函数 s1 和 s2 在公式 φ 中所有自由 出现的变元上取值相同。首先我们有 情形 1：φ 是一个原子公式 P t1t2 · · ·tn 或 t1 ≈ t2。首先我们有对任意 i ≥ 1， s1(ti) = s2(ti)。详细证明需要对项 t 施行归纳并要用到对赋值 s1 和 s2 的假设，我们 留给读者。因此 (A, s1) |= P t1t2 · · ·tn 当且仅当 (s1(t1), s1(t2), · · · , s1(tn)) ∈ P A 当且仅当 (s2(t1), s2(t2), · · · , s2(tn)) ∈ P A 当且仅当 (A, s2) |= P t1t2 · · ·tn。当 φ 为 t1 ≈ t2 时证明与此 类似。 情形 2 和 3：φ 分别具有形式 ¬α 和 α → β。我们把验证留给读者。 情形 4：φ 具有形式 ∀xψ。在此情形下在 ψ 中自由出现的变元至多是 x 加上在 φ 中自 由出现的变元。所以对任何的 d ∈| A |，诱导出的赋值函数 (s1) x d 和 (s2) x d 在 ψ 中所有自由 出现的变元上取值相同。根据归纳假定 A 和 (s1) x d 满足 ψ 当且仅当 A 和 (s2) x d 满足 ψ。所 以 A 和 s1 满足 φ 当且仅当 A 和 s2 满足 φ。 推论 5.1. 对任何闭语句 σ，或者 (a) 对所有函数 s : V →| A |, 都有 (A, s) |= σ；或者 (b) 对所有函数 s : V →| A |, 都有 (A, s) ̸|= σ。 当情形 (a) 成立时，我们就称σ 在 A 中为真，记作 A |= σ；也经常使用下列短语：σ 在 A 中成立；A 满足 σ 和A 是 σ 的一个模型 。 推论 5.1 说明对闭语句来说，赋值函数是不重要的。类似地，如果公式 φ 中仅有一 个自由变元 v1，则对赋值函数来说，重要的只有它在 v1 上的赋值。 例 5.2. 给定一阶语言 L 包含一个二元谓词符号 P，一元函数符号 f 和一个常数符号 c，考 察它的如下结构： A = (N, ≤, S, 0)。 令 s : V → N 使得 s(vi) = i − 1，即 s(v1) = 0, s(v2) = 1 等等。什么是 s(ffv3)？还有 s(ff c)？结构 A 和赋值 s 满足下列公式吗？ (1) P cfv1； 4

第5章一阶语言的结构和真值理论 第2节可定义性 (2)Vu1 Pcu; (3)v1Pv201 例53.证明或否证下列命题 (1) Vu1 QU1 2)Qu1}v1Qn1° 第2节可定义性 有了}σ的概念之后,我们可以利用它来讨论所谓的可定义性。一方面我们可以 固定一个(或一族)公式σ(或∑)来探讨什么样的结构可以满足它(或它们);另一方 面,我们也可以固定一个结构α来探讨|a哪些子集或关系可以被公式φ描述。前者是 在数学中很常见;后者则在数理逻辑中非常重要。 对一个闭语句集∑我们用Mod∑来表示由∑的模型所组成的类。5如果∑是单个闭 语句的集合{r},我们则用"Modr”而不用“Mod{r}。我们称(同一个一阶语言上) 的结构类K为一个初等类(EC)6如果存在闭语句r使得K是Modr。我们称人为一个 广义初等类(EC△)如果存在闭语句集∑,使得K是Mod∑。 例54.令一阶语言L={≈,P}其中P是一个二元谓词符号。令T为下列三个闭语句的合 Vary vz(xPy→yP2→xPz); vry( cPy v.≈ yVyPa); vrvy(xPy→=yPx) 则任何τ的模型都是一个(严格的)线序。所以,所有非空的线序集构成的类是一个初等 类 注:从上例我们可以看出:如果∑是一个有穷的闭语句集,则K=Mod∑是一个初 等类。 5这里的类是相对集合而言,一般说来,Md∑不是一个集合,不然会有悖论。但类和集合的差异对我们的讨论影响 不大,初学者可以暂时忽略 6初等类,英文为 elementary class;广义初等类,英文为 elementary class in a wider sense。有人也把 elementary翻译成 基本。大致上说,初等也好,基本也好,都指的是一阶逻辑所表达的性质,而非所谓的用“高阶”语言描述的“高阶” 性质

第 5 章 一阶语言的结构和真值理论 第 2 节 可定义性 (2) ∀v1P cv1； (3) ∀v1P v2v1。 例 5.3. 证明或否证下列命题： (1) ∀v1Qv1 |= Qv1； (2) Qv1 |= ∀v1Qv1。 第 2 节 可定义性 有了 A |= σ 的概念之后，我们可以利用它来讨论所谓的可定义性。一方面我们可以 固定一个（或一族）公式 σ（或 Σ）来探讨什么样的结构可以满足它（或它们）；另一方 面，我们也可以固定一个结构 A 来探讨 | A | 哪些子集或关系可以被公式 φ 描述。前者是 在数学中很常见；后者则在数理逻辑中非常重要。 对一个闭语句集 Σ 我们用 Mod Σ 来表示由 Σ 的模型所组成的类。5如果 Σ 是单个闭 语句的集合 {τ}，我们则用“Mod τ”而不用“Mod {τ}”。我们称（同一个一阶语言上） 的结构类 K 为一个初等类 （EC）6 如果存在闭语句 τ 使得 K 是 Mod τ。我们称 K 为一个 广义初等类 （EC∆）如果存在闭语句集 Σ，使得 K 是 Mod Σ。 例 5.4. 令一阶语言 L = {≈, P} 其中 P 是一个二元谓词符号。令 τ 为下列三个闭语句的合 取： ∀x∀y∀z (xP y → yP z → xP z); ∀x∀y (xP y ∨ x ≈ y ∨ yP x); ∀x∀y (xP y → ¬yP x)。 则任何 τ 的模型都是一个（严格的）线序。所以，所有非空的线序集构成的类是一个初等 类。 注：从上例我们可以看出：如果 Σ 是一个有穷的闭语句集，则 K = Mod Σ 是一个初 等类。 5这里的类是相对集合而言，一般说来，Mod Σ 不是一个集合，不然会有悖论。但类和集合的差异对我们的讨论影响 不大，初学者可以暂时忽略。 6初等类，英文为 elementary class；广义初等类，英文为 elementary class in a wider sense。有人也把 elementary 翻译成 基本。大致上说，初等也好，基本也好，都指的是一阶逻辑所表达的性质，而非所谓的用“高阶”语言描述的“高阶” 性质。 5

第2节可定义性 第5章一阶语言的结构和真值理论 前面我们提到过“群”这个概念。我们想说明所有的群组成一个初等类,并说明我们 可以选择不同的语言。在第??章第??节中,我们选的语言为Lo=(e,+)。现在我们选取 L1={≈,o,1,e},其中。和-1分别是一个二元和一元函数符号,e是一个常数符号。在 L1上,所有群的类可以被下列闭语句描述,因而是一个初等类 VarvyVz (ao(yo z)a(aoy)oz) vx(xoe≈eox≈x); r(xox1≈r-lor≈e) 我们也可以选取L2={≈,o},其中。是一个二元函数符号。在L2上,所有群的类仍 是一个初等类,因为它可以被下列闭语句描述(见习题) VarvyVz(o(yo)a(oy)ox); vrvy3z(xoz≈y) vry3z(zox≈y)o 注:选取不同的语言对本课程关系不大,但如果我们对句法复杂性感兴趣的话,我们 会注意到在L1上,我们只用到了全称量词,而在L2中我们需要两种不同的量词。这样 的细微差别有时会产生一些影响。 如果语言中有等词的话,我们有闭语句彐表示“结构中至少有n个不同的元素”,例 如,丑2和彐3分别为 丑x3y(x米y) x3y32(x米y∧y关2∧x2) 这样所有的无限群组成的类就是一个广义初等类,因为它是由所有满足群的公理并且满 足{2,3,…}的结构组成的。后面我们会证明它不是一个初等类。 我们再来讨论结构内的可定义性。这种可定义性在数理逻辑是很普遍的,比如,在哥 德尔可构成集的类L中可定义性是最重要的概念。此外,模型论学家也经常研究可定义 的集合或关系,因为同没有限制的任意集合相比,人们更愿意讨论自然的集合,而可定义 的集合可以说是自然的。至少退一步说,不可定义的集合是不太自然的。熟悉集合论公理 的同学可以比较分离公理和选择公理,由分离公理得到的集合是由某个公式定义出来的, 而由选择公理得到的集合往往是不可定义的,因而分离公理比选择公理显得自然。 固定一个语言L和L上面的一个结构。我们先引进一个写法来避免s之类的 繁琐(该写法在练习?中已经出现过)。假定φ(v1,2,…,k)为L的一个公式,并且 t1,2,…,tk包括了中的所有自由变元。对于||中的元素a1,a2,…,ak,我们想说

第 2 节 可定义性 第 5 章 一阶语言的结构和真值理论 前面我们提到过“群”这个概念。我们想说明所有的群组成一个初等类，并说明我们 可以选择不同的语言。在第 ?? 章第 ?? 节中，我们选的语言为 L0 = (e, +)。现在我们选取 L1 = {≈, ◦, −1 , e}，其中 ◦ 和 −1 分别是一个二元和一元函数符号，e 是一个常数符号。在 L1 上，所有群的类可以被下列闭语句描述，因而是一个初等类： ∀x∀y∀z (x ◦ (y ◦ z) ≈ (x ◦ y) ◦ z); ∀x (x ◦ e ≈ e ◦ x ≈ x); ∀x (x ◦ x −1 ≈ x −1 ◦ x ≈ e)。 我们也可以选取 L2 = {≈, ◦}，其中 ◦ 是一个二元函数符号。在 L2 上，所有群的类仍 是一个初等类，因为它可以被下列闭语句描述（见习题）： ∀x∀y∀z (x ◦ (y ◦ z) ≈ (x ◦ y) ◦ z); ∀x∀y∃z (x ◦ z ≈ y); ∀x∀y∃z (z ◦ x ≈ y)。 注：选取不同的语言对本课程关系不大，但如果我们对句法复杂性感兴趣的话，我们 会注意到在 L1 上，我们只用到了全称量词，而在 L2 中我们需要两种不同的量词。这样 的细微差别有时会产生一些影响。 如果语言中有等词的话，我们有闭语句 ∃n 表示“结构中至少有 n 个不同的元素”，例 如，∃2 和 ∃3 分别为： ∃x∃y(x ̸≈ y), ∃x∃y∃z(x ̸≈ y ∧ y ̸≈ z ∧ x ̸≈ z)。 这样所有的无限群组成的类就是一个广义初等类，因为它是由所有满足群的公理并且满 足 {∃2, ∃3, · · · } 的结构组成的。后面我们会证明它不是一个初等类。 我们再来讨论结构内的可定义性。这种可定义性在数理逻辑是很普遍的，比如，在哥 德尔可构成集的类 L 中可定义性是最重要的概念。此外，模型论学家也经常研究可定义 的集合或关系，因为同没有限制的任意集合相比，人们更愿意讨论自然的集合，而可定义 的集合可以说是自然的。至少退一步说，不可定义的集合是不太自然的。熟悉集合论公理 的同学可以比较分离公理和选择公理，由分离公理得到的集合是由某个公式定义出来的， 而由选择公理得到的集合往往是不可定义的，因而分离公理比选择公理显得自然。 固定一个语言 L 和 L 上面的一个结构 A。我们先引进一个写法来避免 s x d 之类的 繁琐（该写法在练习 ?? 中已经出现过）。假定 φ(v1, v2, · · · , vk) 为 L 的一个公式，并且 v1, v2, · · · , vk 包括了 φ 中的所有自由变元。对于 | A | 中的元素 a1, a2, · · · , ak，我们想说 6

第5章一阶语言的结构和真值理论 第3节同态和同构 p(a1,a2,…,ak)成立”,但严格地说,那些a2不在语言L里面,因此上面的写法没有意 义。我们必须换一个说法。具体做法是:7定义 Oh cla1, a 如果存在某个赋值s:V→满足s(v2)=a1(1≤i≤k),使得和s满足φ。注意 由于t1,t2,…,vk包括了φ中的所有自由变元,我们有对任意满足s()=a1的赋值s, 都有和s满足 我们称k元关系 {(a1,a2,…,ak):}φ{a1,a2,…,al} 为公式φ在中定义的关系。我们称一个||上的k元关系为可定义的如果存在某个 公式y在中定义它。 例5.5.考察关于数论的语言L={0,S,+,}。令结构的论域为自然数集N,其它的符号 都按照自然的解释。则序关系{(m,n):m<n}在中是可定义的(为什么?)。对每一个 自然数n,单点集{n}都是中可定义的(为什么?)。所有素数的集合在中是可定义 的(为什么?)。 第3节同态和同构 先看两段小故事 个女画家在飞机上被谋杀了。机上有好几个人都和她有过节。空姐和她 的男朋友还有张三一起侦破。在五个小时的飞行途中,他们终于确定凶手是副 驾驶员。案情明朗后,凶手试图劫机冲向大海,但在驾驶员的帮助下,大家齐 心制服了凶手,成功降落。 个雕塑家在长途车上被谋杀了。车上有好几个人都和他有仇。售票员和 他的女朋友还有李四一起侦破。在八个小时的车程中,他们终于确定凶手是副 司机。案情明朗后,凶手试图将车冲下悬崖,但在司机的帮助下,大家齐心制 服了凶手,转危为安 这两段故事原本是讨论创意抄袭的例子8。它与我们要讲的内容有什么关系留给大家 去想 7另一种常见的做法是扩张语言L使得对每个||中的元素a都有常数符号a当然a3=a SE E Mace and Vincent-Northam, The Writer's abc checklist, Accent Press, 2010

第 5 章 一阶语言的结构和真值理论 第 3 节 同态和同构 “φ(a1, a2, · · · , ak) 成立”，但严格地说，那些 ai 不在语言 L 里面，因此上面的写法没有意 义。我们必须换一个说法。具体做法是：7定义 A |= φ[a1, a2, · · · , ak] 如果存在某个赋值 s : V →| A | 满足 s(vi) = ai （1 ≤ i ≤ k），使得 A 和 s 满足 φ。注意： 由于 v1, v2, · · · , vk 包括了 φ 中的所有自由变元，我们有对任意满足 s(vi) = ai 的赋值 s， 都有 A 和 s 满足 φ。 我们称 k-元关系 {(a1, a2, · · · , ak) : A |= φ[a1, a2, · · · , ak]} 为公式 φ 在 A 中定义 的关系。我们称一个 | A | 上的 k-元关系为可定义的 如果存在某个 公式 φ 在 A 中定义它。 例 5.5. 考察关于数论的语言 L = {0, S, +, ·}。令结构 A 的论域为自然数集 N，其它的符号 都按照自然的解释。则序关系 {(m, n) : m < n} 在 A 中是可定义的（为什么？）。对每一个 自然数 n，单点集 {n} 都是 A 中可定义的（为什么？）。所有素数的集合在 A 中是可定义 的（为什么？）。 第 3 节 同态和同构 先看两段小故事： 一个女画家在飞机上被谋杀了。机上有好几个人都和她有过节。空姐和她 的男朋友还有张三一起侦破。在五个小时的飞行途中，他们终于确定凶手是副 驾驶员。案情明朗后，凶手试图劫机冲向大海，但在驾驶员的帮助下，大家齐 心制服了凶手，成功降落。 一个雕塑家在长途车上被谋杀了。车上有好几个人都和他有仇。售票员和 他的女朋友还有李四一起侦破。在八个小时的车程中，他们终于确定凶手是副 司机。案情明朗后，凶手试图将车冲下悬崖，但在司机的帮助下，大家齐心制 服了凶手，转危为安。 这两段故事原本是讨论创意抄袭的例子8。它与我们要讲的内容有什么关系留给大家 去想。 7另一种常见的做法是扩张语言 L 使得对每个 | A | 中的元素 a, 都有常数符号 a。当然 a A = a。 8改编自 Mace and Vincent-Northam, The Writer’s abc checklist, Accent Press, 2010。 7

第3节同态和同构 第5章一阶语言的结构和真值理论 定义5.4.令以和为某个固定语言的两个结构。我们称一个函数h:|→0|为一个 从到的一个同态如果它满足下列条件 a)对每个(不是等词≈)的n元谓词P,和每组||中的元素a1,a2,…,an都有 (a1,a2…,an)∈P(h(a1),h(a2),…,h(an)∈P b)对每个n元函数符号f和每组||中的元素a1,a2,…,an都有 h(f2(a1,a2,…,an)=f3(h(a1),h(a2),…,h(an)。 c)对每个常数符号c我们有h(c2)=c3 在上述定义中,如果h是一个双射,则称h为从到9上的一个同构,并称和 同构,记作坐。 注 1.学过抽象代数的同学立刻可以看出这里定义的同态是群同态,环同态,偏序的同态 和图的同态等等的抽象。但我们的条件(a)要求双向箭头,这比代数中通常要求的 单向→要强,是所谓的“强同态”。但基本思想是一样的,即,同态是“保持结构” 的映射 2.有些参考书把是单射的同态称为同构,而把双射的同态称为映上的同构。由于我们 关于同构的讨论不多,因此为了避免混乱,我们所谈的同构都是映上的同构 下面的同态定理告诉我们公式的真假是怎样通过同态从一个结构传到另一个结构中 的。 定理52(同态定理)假定h为从纵到仍的一个同态,并且s:V→w|。则 a)对任意项t,h(5(t)=hos(t) b)对任何不含量词且不含等词的公式a,(Q,s)a当且仅当(,hos)ao c)如果h是单射,则b)中的公式a可以包含等词 d如果h是到9的满射,则/b)中的公式a可以包含量词 证明:我们将(a)留作习题。 b)令a为一个不含等词和量词的公式,我们对a施行归纳来证:(,s)}a当且仅 当(9,h。s)ao 8

第 3 节 同态和同构 第 5 章 一阶语言的结构和真值理论 定义 5.4. 令 A 和 B 为某个固定语言的两个结构。我们称一个函数 h :| A |→| B | 为一个 从 A 到 B 的一个同态 如果它满足下列条件： (a) 对每个（不是等词 ≈）的 n 元谓词 P，和每组 | A | 中的元素 a1, a2, · · · , an 都有 (a1, a2, · · · , an) ∈ P A ⇔ (h(a1), h(a2), · · · , h(an)) ∈ P B。 (b) 对每个 n 元函数符号 f 和每组 | A | 中的元素 a1, a2, · · · , an 都有 h(f A (a1, a2, · · · , an)) = f B(h(a1), h(a2), · · · , h(an))。 (c) 对每个常数符号 c 我们有 h(c A ) = c B。 在上述定义中，如果 h 是一个双射，则称 h 为从 A 到 B 上的一个同构，并称 A 和 B 同构，记作 A ∼= B。 注： 1. 学过抽象代数的同学立刻可以看出这里定义的同态是群同态，环同态，偏序的同态 和图的同态等等的抽象。但我们的条件（a）要求双向箭头，这比代数中通常要求的 单向 ⇒ 要强，是所谓的“强同态”。但基本思想是一样的，即，同态是“保持结构” 的映射。 2. 有些参考书把是单射的同态称为同构，而把双射的同态称为映上的同构。由于我们 关于同构的讨论不多，因此为了避免混乱，我们所谈的同构都是映上的同构。 下面的同态定理告诉我们公式的真假是怎样通过同态从一个结构传到另一个结构中 的。 定理 5.2 (同态定理). 假定 h 为从 A 到 B 的一个同态，并且 s : V →| A |。则 (a) 对任意项 t，h(s(t)) = h ◦ s(t)。 (b) 对任何不含量词且不含等词的公式 α，(A, s) |= α 当且仅当 (B, h ◦ s) |= α。 (c) 如果 h 是单射，则 (b) 中的公式 α 可以包含等词。 (d) 如果 h 是 A 到 B 的满射，则 (b) 中的公式 α 可以包含量词。 证明: 我们将 (a) 留作习题。 (b) 令 α 为一个不含等词和量词的公式，我们对 α 施行归纳来证：(A, s) |= α 当且仅 当 (B, h ◦ s) |= α。 8

第5章一阶语言的结构和真值理论 第3节同态和同构 如果α是一个原子公式Pt1t2……tn,其中P是n-元谓词符号,t1,t2,…,tn是项。则 (l,s)Pt1t2…tn 兮(5(t1),3(t2),…,3(tn)∈P 兮(h(3(t1),h((t2),…,h(8(tn)∈P3 兮(h°s(t1,h°s(t2)…,h°s(tn)∈P3 兮(9,hos)FPt1t2…tn 如果a形为-B或者形为β→,则例行地利用归纳假设即可得到证明。 (c)无论h是不是单射,我们总有 (l,s)ku≈t兮8(u)=5(t) →h(3(u)=h(3(t) ho s(u)=hos(t) 兮(8,hos)u≈t。 如果h是单射,则第二步的“→”可以逆转。 (d)无论h是不是满射,我们总有 (,s)}xB分对所有的d∈|a|(q,sa)=B 台对所有的d∈||(9,ho(sa)B 台对所有的d∈||(,(hos)ha)=B 台对所有的e(,(hos)2)B hos)vaB. 如果h是满射,则倒数第二步的“<”可以逆转。并且注意第三个“兮”是因为赋值函数 ho(s)和(hos)h作为从V到9的函数是相等的(练习) 定义5.5.固定一个语言L和其上的两个结构和9。我们称它们为初等等价的,记作 ≡,如果对L中的任何一个闭语句a都有卡a当且仅当9}a 注 1.初等等价是一个非常重要的概念,只有在数理逻辑里面,人们才会如此重视研究对 象的性质对其描述语言的依赖程度 2.同态定理告诉我们:任何两个同构的模型都是初等等价的。这在直观上很好理解, 因为同构的两个结构本质上就是同一个,只不过是“标签”不同罢了。因此在一个 结构里成立的事实在它的同构体中自然也成立

第 5 章 一阶语言的结构和真值理论 第 3 节 同态和同构 如果 α 是一个原子公式 P t1t2 · · ·tn，其中 P 是 n-元谓词符号，t1, t2, · · · , tn 是项。则 (A, s) |= P t1t2 · · ·tn ⇔ (s(t1), s(t2), · · · , s(tn)) ∈ P A ⇔ (h(s(t1)), h(s(t2)), · · · , h(s(tn))) ∈ P B ⇔ (h ◦ s(t1), h ◦ s(t2), · · · , h ◦ s(tn)) ∈ P B ⇔ (B, h ◦ s) |= P t1t2 · · ·tn。 如果 α 形为 ¬β 或者形为 β → γ，则例行地利用归纳假设即可得到证明。 (c) 无论 h 是不是单射，我们总有： (A, s) |= u ≈ t ⇔ s(u) = s(t) ⇒ h(s(u)) = h(s(t)) ⇔ h ◦ s(u) = h ◦ s(t) ⇔ (B, h ◦ s) |= u ≈ t。 如果 h 是单射，则第二步的“⇒”可以逆转。 (d) 无论 h 是不是满射，我们总有： (A, s) |= ∀xβ ⇔ 对所有的 d ∈| A | (A, sx d ) |= β ⇔ 对所有的 d ∈| A | (B, h ◦ (s x d )) |= β ⇔ 对所有的 d ∈| A | (B,(h ◦ s) x h(d) ) |= β ⇐ 对所有的 e ∈| B | (B,(h ◦ s) x e ) |= β ⇔ (B, h ◦ s) |= ∀xβ。 如果 h 是满射，则倒数第二步的“⇐”可以逆转。并且注意第三个“⇔”是因为赋值函数 h ◦ (s x d ) 和 (h ◦ s) x h(d) 作为从 V 到 B 的函数是相等的（练习）。 定义 5.5. 固定一个语言 L 和其上的两个结构 A 和 B。我们称它们为初等等价的，记作 A ≡ B，如果对 L 中的任何一个闭语句 σ 都有 A |= σ 当且仅当 B |= σ。 注： 1. 初等等价是一个非常重要的概念，只有在数理逻辑里面，人们才会如此重视研究对 象的性质对其描述语言的依赖程度。 2. 同态定理告诉我们：任何两个同构的模型都是初等等价的。这在直观上很好理解， 因为同构的两个结构本质上就是同一个，只不过是“标签”不同罢了。因此在一个 结构里成立的事实在它的同构体中自然也成立。 9

第3节同态和同构 第5章一阶语言的结构和真值理论 3.有意思的是其逆命题是否成立?即是否初等等价的结构都是同构的?后面我们会给 出反例说明它不成立。道理不难理解,两个结构初等等价只不过说明,用我们规定 的语言我们无法描述出它们的区别,并不意味着它们没有别的区别。换句话说,初 等等价但不同构的现象只说明我们语言的匮乏而已。 结构Ⅻ上的一个自同构就是从到w自身的一个同构。由同态定理,我们可以得出 下列推论,说明任何自同构都保持可定义的关系。 推论52.令h为结构%上的一个自同构,并且R是|则|上的一个中可定义的m-元关 系。则对任意||中的元素a1,a2,…,a (a1,a2,…,an)∈R兮(h(a1),h(a2)……,h(an)∈R 证明:令φ为以中定义R的公式。根据同态定理(为什么?), an兮Fyh(a1),h(a2),……,h(an 因此 (a1,a2,…,an)∈R分(h(a1),h(a2),…,h(an)∈R (而这正是我们“保持”R的意思)。 如果一个结构上有很多自同构,我们经常用推论5.2的逆否命题来证明某些集合或关 系的不可定义性 例56.考察由全体实数和其上的自然序组成的结构(R,<)。定义h:R→R为h(x)=x3 则h是该结构的一个自同构(为什么?)。h-1(x)=√也是自同构。利用h-1我们可以证 明N在结构(R,<)中是不可定义的(为什么?)

第 3 节 同态和同构 第 5 章 一阶语言的结构和真值理论 3. 有意思的是其逆命题是否成立？即是否初等等价的结构都是同构的？后面我们会给 出反例说明它不成立。道理不难理解，两个结构初等等价只不过说明，用我们规定 的语言我们无法描述出它们的区别，并不意味着它们没有别的区别。换句话说，初 等等价但不同构的现象只说明我们语言的匮乏而已。 结构 A 上的一个自同构 就是从 A 到 A 自身的一个同构。由同态定理，我们可以得出 下列推论，说明任何自同构都保持可定义的关系。 推论 5.2. 令 h 为结构 A 上的一个自同构，并且 R 是 | A | 上的一个 A 中可定义的 n-元关 系。则对任意 | A | 中的元素 a1, a2, · · · , an， (a1, a2, · · · , an) ∈ R ⇔ (h(a1), h(a2)· · · , h(an)) ∈ R。 证明: 令 φ 为 A 中定义 R 的公式。根据同态定理（为什么？）， A |= φ[a1, a2, · · · , an] ⇔ A |= φ[h(a1), h(a2), · · · , h(an)]。 因此， (a1, a2, · · · , an) ∈ R ⇔ (h(a1), h(a2), · · · , h(an)) ∈ R （而这正是我们“保持”R 的意思）。 如果一个结构上有很多自同构，我们经常用推论 5.2 的逆否命题来证明某些集合或关 系的不可定义性。 例 5.6. 考察由全体实数和其上的自然序组成的结构 (R, <)。定义 h : R → R 为 h(x) = x 3。 则 h 是该结构的一个自同构（为什么？）。h −1 (x) = √3 x 也是自同构。利用 h −1 我们可以证 明 N 在结构 (R, <) 中是不可定义的（为什么？）。 10