ゲーデルの完全性定理
しかし、完全性定理はこれら2つの概念の差異をなくすものではない。実際、もう1つの成果であるゲーデルの不完全性定理によれば、数学における形式的証明で達成できることには本質的な限界がある。不完全性定理でいう「完全」は別の意味で使われている。完全性定理は一階の理論の論理的帰結である論理式を扱い、不完全性定理は特定の理論の論理的帰結にはならない論理式を構築する。
完全性定理の重要な帰結の1つとして、一階の理論での論理的帰結の集合が帰納的可算集合であるという事実がある。論理的帰結の定義は特定の言語でのあらゆる構造上で全称化するもので、論理式が論理的に妥当かどうかをアルゴリズム的に検証する直接の手段とはならない。さらに言えば、ゲーデルの不完全性定理の帰結により、論理的に妥当な論理式の集合は決定可能ではない。しかし完全性定理は、実効的な理論の帰結の集合が枚挙可能であることを示している。そのアルゴリズムは、まずその理論から全ての形式的演繹を枚挙する方法を構成し、それを使って帰結の枚挙を生み出すことになる。形式的演繹の有限かつ統語的性質により、それらを枚挙することが可能になっている。
一階論理の演繹系としては、自然演繹やヒルベルト系など様々なものがある。演繹系は一般に形式的演繹の記法である。それは論理式の並び(あるいは場合によっては木構造)であり、末尾に特別な帰結がある。演繹とは、有限でアルゴリズム的に(コンピュータや人間の手で)検証可能な論理式の集まりである。
論理式が論理的に妥当であるとは、その論理式の言語におけるあらゆる構造に照らして真であることを言う。完全性定理を形式的に定義し証明するには、演繹系を定義する必要もある。演繹系が完全であるとは、論理的に妥当な全ての論理式が何らかの形式的演繹の帰結であることを意味し、特定の演繹系についての完全性定理は、そういった意味で完全であることを示す定理である。したがって、それぞれの演繹系ごとにそれぞれの完全性定理が存在する。