Editing Gödel's completeness theorem (section)

==Relationship to the compactness theorem==
The completeness theorem and the [[compactness theorem]] are two cornerstones of first-order logic. While neither of these theorems can be proven in a completely [[effectively computable|effective]] manner, each one can be effectively obtained from the other.

The compactness theorem says that if a formula φ is a logical consequence of a (possibly infinite) set of formulas Γ then it is a logical consequence of a finite subset of Γ. This is an immediate consequence of the completeness theorem, because only a finite number of axioms from Γ can be mentioned in a formal deduction of φ, and the soundness of the deductive system then implies φ is a logical consequence of this finite set. This proof of the compactness theorem is originally due to Gödel.

Conversely, for many deductive systems, it is possible to prove the completeness theorem as an effective consequence of the compactness theorem.

The ineffectiveness of the completeness theorem can be measured along the lines of [[reverse mathematics]]. When considered over a countable language, the completeness and compactness theorems are equivalent to each other and equivalent to a weak form of choice known as [[weak Kőnig's lemma]], with the equivalence provable in RCA<sub>0</sub> (a second-order variant of [[Peano arithmetic]] restricted to induction over  Σ<sup>0</sup><sub style="margin-left:-0.6em">1</sub> formulas). Weak Kőnig's lemma is provable in ZF, the system of [[Zermelo–Fraenkel set theory]] without axiom of choice, and thus the completeness and compactness theorems for countable languages are provable in ZF. However the situation is different when the language is of arbitrary large cardinality since then, though the completeness and compactness theorems remain provably equivalent to each other in ZF, they are also provably equivalent to a weak form of the [[axiom of choice]] known as [[Boolean prime ideal theorem#The ultrafilter lemma|the ultrafilter lemma]]. In particular, no theory extending ZF can prove either the completeness or compactness theorems over arbitrary (possibly uncountable) languages without also proving the ultrafilter lemma on a set of the same cardinality.