完备性

上级：soundness-and-completeness

完备性定理（Gödel，1929，针对

FOL） Γ ⊨ φ ⟹ Γ ⊢ φ —— 任何为真的东西（在 Γ 的每一个模型里都为真）都是可证的。这中间没有缺口：证明系统的能力足以抵达每一个有效公式。

证明——从句法本身构造出一个模型（语义 ← 句法）

这是难的那个方向，它跨越 句法↔语义 这道鸿沟的走法和可靠性定理正好相反：不是把真值沿着一条证明往下推，而是从一个一致的公式集合中制造出一个模型。用逆否命题来做：

Γ ⊬ φ ⟹ Γ ⊭ φ —— 如果 φ 不可证，就构造一个 Γ 的模型，使 φ 在其中为假（一个反模型），这样 φ 就不是有效的。

构造过程（Henkin / Lindenbaum）：

1. Γ ⊬ φ 意味着 Γ ∪ {¬φ} 是一致的（这是句法意义上的一致——不存在能推出矛盾的证明）。
2. 把它扩充成一个极大一致集 Γ*（Lindenbaum 方法：把公式一条条加进去，同时保持一致性；对 FOL 的情形还要加入见证∃x.ψ → ψ[c/x]）。
3. Γ* 本身就是一个模型：真值直接由成员关系读出（φ 为真 ⟺ φ ∈ Γ*）；极大性加一致性使这构成一个良定义的结构（一个项模型），满足 Γ 中的一切以及 ¬φ。 于是 Γ 有一个使 φ 为假的模型 → Γ ⊭ φ。∎

核心就是那句口号——"每一个一致的理论都有一个模型"——一个句法性质（一致性）硬生生逼出了一个语义对象（一个模型）的存在。这就是完备性，也正是两边会重合的原因所在。这里勾勒的构造——Lindenbaum + Henkin + 真值引理——在 canonical-model 中有完整的展开。

它带来了什么

• 有效性是半可判定的：枚举所有证明；由完备性可知，某个证明会出现当且仅当 φ 有效（这正是判定问题（Entscheidungsproblem）中递归可枚举的那一面）。
• 紧致性由此自然得出：如果 Γ 的每一个有限子集都可满足，那么 Γ 就是一致的，因此（由完备性）有一个模型——这是模型论里的一件常用工具。
• 要当心：这里说的完备性，是指该逻辑的证明系统对有效性而言是完备的——它不是哥德尔不完备定理的反面，后者说的是某个理论无法证明所有算术真命题（参见那条提醒）。

真正把这一切干出来的典范模型（canonical model）——把理论自身的句法直接变成一个结构——有它自己的一篇笔记：canonical-model。