ゲーデルの完全性定理
完全性定理の重要な帰結の1つとして、任意の一階の理論について、その理論の公理を使った正しい演繹を全て数え上げることで、論理的帰結を数え上げることが可能であると示された。すなわち完全性定理は論理的帰結関係 Γ ⊨ φ {\displaystyle \Gamma \models \varphi } と証明可能性関係 Γ ⊢ φ {\displaystyle \Gamma \vdash \varphi } とが一致することを述べているが、後者は帰納的可算であるので前者も帰納的可算であるということである。
ゲーデルの不完全性定理(この場合の「完全性」の意味は異なる)は、ある程度の初等算術を含む帰納的可算理論が無矛盾なら、その理論体系内で証明も反証もできない閉論理式が存在することを示した。その場合も、そのような理論体系に完全性定理を適用でき、その理論体系における任意の論理的帰結はその理論体系内で証明可能である。