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

第 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) ∀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 节同态和同构 “φ(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. 令 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章 一阶语言的结构和真值理论

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