哥德尔完备性定理 哥德尔完备性定理是数理逻辑中重要的定理在年由库尔特哥德尔首先证明它的最熟知的形式声称在一阶谓词演算中所有逻辑上有效的公式都是可以证明的 上述词语可证明的意味着有着这个公式的形式演绎这种形式演绎是步骤的有限列表其中每个步骤要么涉及公理要么通过基本推理规则从前面的步骤获得给定这样一种演绎它的每个步骤的正确性可以在算法上检验比如通过计算机或手工 如果一个公式在这个公式的语言的所有模型中都为真它就被称为逻辑上有效的为了形式的陈述哥德尔完备性定理你必须定义这个上下文中词语模型的意义这是模型论的基本定义 在另一个方向上哥德尔完备性定理声称一阶谓词演算的推理规则是完备的在不需要额外的推理规则来证明所有逻辑上有效的公式的意义上完备性的逆命题是可靠性一阶谓词演算的实情是可靠的就是说只有逻辑上有效的陈述可以在一阶逻辑中证明这是可靠性定理断言的 处理在不同的模型中什么为真的数理逻辑分支叫做模型论研究在特定形式系统中什么为可以形式证明的分支叫做证明论完备性定理建立了在这两个分支之间的基本联系给出了在语义和语形之间的连接但完备性定理不应当被误解为消除了在这两个概念之间的区别事实上另一个著名的结果哥德尔不完备定理证实了对在数学中什么是形式证明可以完成的有着固有的限制不完备定理的名声与另一种意义的完备有关参见模型论 更一般版本的哥德尔完备性定理成立它声称对于任何一阶理论T和在这个理论中的任何句子S有一个S的自T的形式演绎当且仅当S被T的所有模型满足这个更一般的定理被隐含使用例如在一个句子被证实可以用群论的公理证明的时候通过考虑一个任意的群并证实这个句子被这个群所满足完备性定理是一阶逻辑的中心性质不在所有逻辑中成立比如二阶逻辑就没有完备性定理 完备性定理等价于超滤子引理它是弱形式的选择公理在不带有选择公理的策梅洛弗兰克尔集合论中有着等价的可证明性