第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