第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