ゲーデルの不完全性定理（この場合の「完全性」の意味は異なる）は、ある程度の初等算術を含む帰納的可算理論が無矛盾なら、その理論体系内で証明も反証もできない閉論理式が存在することを示した。その場合も、そのような理論体系に完全性定理を適用でき、その理論体系における任意の論理的帰結はその理論体系内で証明可能である。
背景.
一階論理の演繹系としては、自然演繹やヒルベルト系など様々なものがある。演繹系は一般に形式的演繹の記法である。それは論理式の並び（あるいは場合によっては木構造）であり、末尾に特別な帰結がある。演繹とは、有限でアルゴリズム的に（コンピュータや人間の手で）検証可能な論理式の集まりである。
論理式が論理的に妥当であるとは、その論理式の言語におけるあらゆる構造に照らして真であることを言う。完全性定理を形式的に定義し証明するには、演繹系を定義する必要もある。演繹系が完全であるとは、論理的に妥当な全ての論理式が何らかの形式的演繹の帰結であることを意味し、特定の演繹系についての完全性定理は、そういった意味で完全であることを示す定理である。したがって、それぞれの演繹系ごとにそれぞれの完全性定理が存在する。
定理とその帰結.
ゲーデルの完全性定理は、一階述語計算の演繹系が、全ての論理的に妥当な論理式の証明に追加の推論規則を必要としないという意味で「完全」であるとしている。完全性の逆は健全性であり、演繹系において論理的に妥当な論理式のみが証明可能だということを意味する。これらから、論理式が論理的に妥当であることと、それが形式的演繹の帰結であることは同値である。
コンパクト性定理との関係.
コンパクト性定理は、論理式 φ が一連の論理式の（無限もありうる）集合 Γ の論理的帰結であるとき、φ は Γ の有限な部分集合の論理的帰結でもある、というものである。φ の形式的推論で言及される Γ の公理は有限個であるため、これは完全性定理から直接得られる帰結である。演繹系の健全性から、φ がこの有限集合の論理的帰結となる。このコンパクト性定理の証明は本来ゲーデルに帰されるものである。
逆に多くの演繹系では、コンパクト性定理の実効的な帰結として完全性定理を証明可能である。
他の論理の完全性.
証明.