第2节完全性定理 第6章哥德尔完全性定理 枚举存在性是由语言的可数性保证的。令1为 vx1921→-(91)a1, 其中c1为第一个不在1中出现的新常数符号。假如我们已经处理完了前k个有序对,并 且定义了辛钦公理{61,O2,…,Ok},则令+1为 xk+142k+1→(k+1)c+1, 其中c+为第一个在1…,9k,9k+1,61,…,k中都不出现的新常数符号。这样不断地 做下去,我们最终得到一个公式集θ={61,2,……}。我们验证rU6仍然是相容的:如 果不相容的话,则根据证明序列的有限性和前面验证的r的相容性,就存在某个m≥0, 使得 rU{61,…,bm+1} 为不相容的。选取最小的这样的m。根据(RAA) rU{61,…,bm} 假设m+1为 ry→-y2o 根据重言规则,我们有 U{61,……,6n} 并且 rU{61,…,bm}+yg 注意到c在表达式左边不出现,根据常数概括定理,我们有 rU{61,…,bm} 这与m的极小性矛盾。 我们在相容公式集r∪θ继续扩张,以得到一个极大相容的公式集Δ,即对任何公式 φ或者φ∈Δ或者(-φ)∈Δ。具体做法与命题逻辑中林登鲍姆引理的证眀完全类似,这 里不再重复。注意任何的极大相容集Δ都对语法后承(或说对推导)封闭:如果△+y, 则相容性告诉我们△Hv所以(-)g△,在根据极大性,就有p∈△。 小结:我们扩充了语言,添加了辛钦公理集θ,并把r∪θ扩充成一个极大相容集 下一步我们将从Δ中“读出”一个新语言LC上的结构,但把等词≈暂时替换成 个新的二元谓词E。(等词的处理将使我们下一步的工作。)结构的定义如下:第 2 节 完全性定理 第 6 章 哥德尔完全性定理 枚举存在性是由语言的可数性保证的。令 θ1 为 ¬∀x1φ1 → ¬(φ1) x1 ci1 , 其中 ci1 为第一个不在 φ1 中出现的新常数符号。假如我们已经处理完了前 k 个有序对，并 且定义了辛钦公理 {θ1, θ2, · · · , θk}，则令 θk+1 为 ¬∀xk+1φk+1 → ¬(φk+1) xk+1 cik+1 , 其中 cik+1 为第一个在 φ1￾ · · · , φk, φk+1, θ1, · · · , θk 中都不出现的新常数符号。这样不断地 做下去，我们最终得到一个公式集 Θ = {θ1, θ2, · · · }。我们验证 Γ ∪ Θ 仍然是相容 的：如 果不相容的话，则根据证明序列的有限性和前面验证的 Γ 的相容 性，就存在某个 m ≥ 0， 使得 Γ ∪ {θ1, · · · , θm+1} 为不相容的。选取最小的这样的 m。根据（RAA） Γ ∪ {θ1, · · · , θm} ⊢ ¬θm+1。 假设 θm+1 为 ¬∀xφ → ¬φ x c。 根据重言规则，我们有 Γ ∪ {θ1, · · · , θm} ⊢ ¬∀xφ, 并且 Γ ∪ {θ1, · · · , θm} ⊢ φ x c。 注意到 c 在表达式左边不出现，根据常数概括定理，我们有 Γ ∪ {θ1, · · · , θm} ⊢ ∀xφ, 这与 m 的极小性矛盾。 我们在相容公式集 Γ ∪ Θ 继续扩张，以得到一个极大相容的公式集 ∆，即对任何公式 φ 或者 φ ∈ ∆ 或者 (¬φ) ∈ ∆。具体做法与命题逻辑中林登鲍姆引理的证明完全类似，这 里不再重复。注意任何的极大相容集 ∆ 都对语法后承（或说对推导）封闭：如果 ∆ ⊢ φ， 则相容性告诉我们 ∆ ̸⊢ ¬φ 所以 (¬φ) ̸∈ ∆，在根据极大性，就有 φ ∈ ∆。 小结：我们扩充了语言，添加了辛钦公理集 Θ，并把 Γ ∪ Θ 扩充成一个极大相容集 ∆。 下一步我们将从 ∆ 中“读出”一个新语言 LC 上的结构 A，但把等词 ≈ 暂时替换成 一个新的二元谓词 E。（等词的处理将使我们下一步的工作。）结构 A 的定义如下： 4