哥德爾完備性定理

哥德爾完備性定理是數理邏輯中重要的定理，在1929年由庫爾特·哥德爾首先證明。它的最熟知的形式聲稱在一階謂詞演算中所有邏輯上有效的公式都是可以證明的。

基本介紹

• 中文名：哥德爾完備性定理
• 提出者：庫爾特·哥德爾
• 提出時間：1929年
• 適用領域範圍：數理邏輯

定理定義

上述詞語“可證明的”意味著有著這個公式的形式演繹。這種形式演繹是步驟的有限列表，其中每個步驟要么涉及公理要么通過基本推理規則從前面的步驟獲得。給定這樣一種演繹，它的每個步驟的正確性可以在算法上檢驗（比如通過計算機或手工）。

一個公式被稱為“邏輯上有效”的，如果它在這個公式的語言的所有模型中都為真。為了形式化地陳述哥德爾完備性定理，你必須定義這個上下文中詞語“模型”的意義。這是模型論的基本定義。

在另一方面上，哥德爾完備性定理聲稱，在不需要額外的推理規則來證明所有邏輯上有效的公式的意義上，一階謂詞演算的推理規則是“完備的”。完備性的逆命題是“可靠性”。一階謂詞演算的確是可靠的，就是說，只有邏輯上有效的陳述可以在一階邏輯中證明，這是可靠性定理斷言的。

處理在不同的模型中什麼為真的數理邏輯分支叫做模型論。研究在特定形式系統中什麼為可以形式證明的分支叫做證明論。完備性定理建立了在這兩個分支之間的基本聯繫。給出了在語義和語法之間的連線。但完備性定理不應當被誤解為消除了在這兩個概念之間的區別；事實上另一個著名的結果哥德爾不完備性定理，證實了對“在數學中什麼是形式證明可以完成的”有著固有的限制。不完備定理的名字與另一種意義的“完備”有關，參見模型論。

更一般版本的哥德爾完備性定理成立。它聲稱對於任何一階理論T和在這個理論中的任何句子S，有一個S的自T的形式演繹，若且唯若S被T的所有模型滿足。這個更一般的定理被隱含使用，例如，在一個句子被證實可以用群論的公理證明的時候，通過考慮一個任意的群並證實這個句子被這個群所滿足。完備性定理是一階邏輯的中心性質，不在所有邏輯中成立。比如二階邏輯就沒有完備性定理。

完備性定理等價於超濾子引理，它是弱形式的選擇公理，在不帶有選擇公理的Zermelo–Fraenkel集合論中有著等價的可證明性。

驗證推導

對定理的最初證明的解釋請參見哥德爾完備性定理的最初證明。

在現代邏輯課本中，哥德爾完備性定理通常使用Leon Henkin的證明而不是哥德爾最初的證明。

深入閱讀

Kurt Gödel, "Über die Vollständigkeit des Logikkalküls", doctoral dissertation, University Of Vienna, 1929. This dissertation is the original source of the proof of the completeness theorem.

Kurt Gödel, "Die Vollständigkeit der Axiome des logischen Funktionen-kalküls", Monatshefte für Mathematik und Physik 37 (1930), 349-360. This article contains the same material as the doctoral dissertation, in a rewritten and shortened form. The proofs are more brief, the explanations more succinct, and the lengthy introduction has been omitted.

參考

Vilnis Detlovs and Karlis Podnieks, "Introduction to mathematical logic",