第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