MathLabs
定理已证明

哥德尔完备性定理

命题陈述

在一阶逻辑中,命题 φ\varphi 可由公理集合 Σ\Sigma 推导得出(记作 Σ⊢φ\Sigma\vdash\varphi)当且仅当 φ\varphi 在 Σ\Sigma 的每个模型中都为真(记作 Σ⊨φ\Sigma\models\varphi):语法后承与语义后承是一致的。

为什么成立?

完备性定理表明一阶证明系统不会遗漏任何东西:凡是在满足公理的每个结构中都为真的命题,都能用有限的形式证明实际推导出来。这是后来的不完备定理的积极对应面——不完备定理谈的是为算术设定的某个固定公理系统能证明什么,而不是一般意义上一阶逻辑的可证明性。

证明思路

证明每个相容的一阶命题集合都有模型(亨金构造法):在语言中添加新的常数作为每个存在命题的“见证”,利用这些见证把理论扩张为极大相容集合,再直接从所得的语法数据构造出一个项模型。由此得到完备性:若 Σ⊬φ\Sigma\nvdash\varphi,则 Σ∪{¬φ}\Sigma\cup\{\neg\varphi\} 相容,因而存在使 φ\varphi 为假的模型,即 Σ⊭φ\Sigma\not\models\varphi。

证明者

1929 年证明库尔特·哥德尔

用到此定理的主题

谓词逻辑哥德尔不完备定理

相关定理

哥德尔第一不完备定理

分步证明

该定理暂无分步证明。

参考文献

  1. Kurt Gödel (1930). Die Vollständigkeit der Axiome des logischen Funktionenkalküls · DOI:10.1007/BF01696781
  2. Herbert B. Enderton (2001). A Mathematical Introduction to Logic · DOI:10.1016/C2009-0-22107-6