跳至内容
Topos Uranos
中文 (中国)

紧致性定理

摘要

一个推演是有穷序列，只用到有穷多个前提；相反，一个无穷公式集的满足要求单独一个赋值同时给无穷多个公式以值 11，而其定义中没有任何东西说检查有穷部分就够了。紧致性定理断言这就够了：一个公式集是可满足的，当且仅当它的每个有穷子集都是可满足的。这一课用直接的语义论证来证明它，而不经过推演：逐一固定变元 v1,v2,…v_1, v_2, \ldots 的值，在每一步保持这样一个不变量，即该集合的每个有穷子集仍可被一个尊重已固定之值的赋值满足；如果两种可能的选择都不能保持它，那么这次失败的两个有穷见证之并就会与先前的不变量矛盾；最后，每个公式都由一致引理而得到满足，因为它只有有穷多个变元。由于变元是编了号的，这个构造不需要选择公理。由紧致性得出它的各种等价形式（一个集合不可满足，当且仅当它的某个有穷部分不可满足；一个公式是一个集合的后承，当且仅当它是某个有穷部分的后承），并且结合上一课对有穷前提的完备性，得出强完备性：Γ⊨φ\Gamma \models \varphi 蕴涵 Γ⊢φ\Gamma \vdash \varphi，对一切集合 Γ\Gamma 成立，由此推演与语义后承总是重合。这一课以组合应用结束：由有穷部分的着色得到无穷图的着色，藏在无穷命题中的有穷的界，以及一个公式集所能表达之物的局限。

学习目标

  1. 定义有穷可满足的集合，并通过逐次固定变元的值来证明紧致性定理，说明不变量、双见证论证和一致引理的作用，以及为什么这个构造不需要选择公理。
  2. 陈述、证明并应用紧致性的等价形式，即不可满足性形式与后承形式，并能从每一种过渡到其他各种。
  3. 由紧致性、对有穷前提集的完备性和单调性推出强完备性，并由此得出推演与语义后承的重合以及一致性与可满足性的重合。
  4. 把关于无穷集合的组合问题（着色、序、配对）编码为公式集，并用紧致性解决它们，分清定理所保证的与它所不保证的。

从前面各课用到的内容

这一课几乎完全在语义学中进行，并从中用到以下内容。一个赋值是一个函数 v ⁣:V→{0,1}v\colon V \to \{0, 1\}，定义在集合 VV 上，即变元 v1,v2,v3,…v_1, v_2, v_3, \ldots 的集合，它以唯一的方式扩张到一切公式；一个赋值满足一个公式集 Γ\Gamma，记作 v⊨Γv \models \Gamma，如果它给其中每个公式以值 11；Γ\Gamma 是可满足的，如果有某个赋值满足它，否则是不可满足的。这些都在关于命题逻辑的语义学的一课中，同时还有这一课的核心工具，一致引理：如果两个赋值在 φ\varphi 的变元（它们构成一个有穷集合 V(φ)V(\varphi)）上一致，那么它们给 φ\varphi 以相同的值。

从关于语义后承与语义等价的一课用到 Γ⊨φ\Gamma \models \varphi 的定义（每个满足 Γ\Gamma 的赋值都满足 φ\varphi）、它的结构性质，特别是单调性（若 Γ⊆Δ\Gamma \subseteq \Delta 且 Γ⊨φ\Gamma \models \varphi，则 Δ⊨φ\Delta \models \varphi）和第五条性质（一个不可满足的集合以一切公式为后承），以及后承与不可满足性定理：Γ⊨φ\Gamma \models \varphi 当且仅当 Γ∪{¬φ}\Gamma \cup \{\neg\varphi\} 不可满足。从关于广义德摩根律与分配律的一课用到值引理：⋀i=1nφi\bigwedge_{i=1}^{n} \varphi_i 取值 11 当且仅当它的所有项都取值 11，而 ⋁i=1nφi\bigvee_{i=1}^{n} \varphi_i 当且仅当某一项取值 11。最后，⊤:=(v1→v1)\top := (v_1 \rightarrow v_1) 是重言式，而 ⊥:=¬⊤\bot := \neg\top 是矛盾式。

在推演一侧，关于形式演绎系统的一课证明了单调性（单调：若 Γ⊆Δ\Gamma \subseteq \Delta 且 Γ⊢φ\Gamma \vdash \varphi，则 Δ⊢φ\Delta \vdash \varphi）和有穷性（有穷：若 Γ⊢φ\Gamma \vdash \varphi，则有某个有穷子集 Γ0\Gamma_0 包含于 Γ\Gamma 并满足 Γ0⊢φ\Gamma_0 \vdash \varphi），而关于四种推演技巧的一课验证了两者在本课程的系统（公理模式 A1、A2 与 A3，分离规则和双重否定替换（双否替换））中成立；以下记号 ⊢\vdash 都指这个系统。最后，关于可靠性与完备性的一课证明了可靠性定理（Γ⊢φ\Gamma \vdash \varphi 蕴涵 Γ⊨φ\Gamma \models \varphi，对一切 Γ\Gamma）和对有穷前提集的完备性：若 {γ1,…,γk}⊨φ\{\gamma_1, \ldots, \gamma_k\} \models \varphi，则 {γ1,…,γk}⊢φ\{\gamma_1, \ldots, \gamma_k\} \vdash \varphi。