Editing Gödel's completeness theorem (section)

{{short description|Fundamental theorem in mathematical logic}}
{{For|the subsequent theories about the limits of provability|Gödel's incompleteness theorems}}
[[File:Completude logique premier ordre.png|thumb|upright=1.8|The formula ([[Universal quantification|∀]]''x''. ''R''(''x'',''x'')) [[Material conditional|→]] (∀''x''[[Existential quantification|∃]]''y''. ''R''(''x'',''y'')) holds in all [[Structure (mathematical logic)|structures]] (only the simplest 8 are shown left). By Gödel's completeness result, it must hence have a [[natural deduction]] proof (shown right).]]
'''Gödel's completeness theorem''' is a fundamental theorem in [[mathematical logic]] that establishes a correspondence between [[semantics|semantic]] truth and syntactic [[Provability logic|provability]] in [[first-order logic]].

The completeness theorem applies to any first-order [[Theory (mathematical logic)|theory]]: If ''T'' is such a theory, and φ is a sentence (in the same language) and every model of ''T'' is a model of φ, then there is a (first-order) proof of φ using the statements of ''T'' as axioms. One sometimes says this as "anything true in all models is provable". (This does not contradict [[Gödel's <!---first---> incompleteness theorem]], which is about a formula φ<sub>u</sub> that is unprovable in a certain theory ''T'' but true in the "standard" model of the natural numbers: φ<sub>u</sub> is false in some other, "non-standard" models of ''T''.<ref>{{Cite arXiv|last=Batzoglou|first=Serafim|eprint=2112.06641|title=Gödel's Incompleteness Theorem|year=2021|class=math.HO }} (p.17). Accessed 2022-12-01.</ref>)

The completeness theorem makes a close link between [[model theory]], which deals with what is true in different models, and [[proof theory]], which studies what can be formally proven in particular [[formal system]]s.

It was first proved by [[Kurt Gödel]] in 1929. It was then simplified when [[Leon Henkin]] observed in his [[Ph.D. thesis]] that the hard part of the proof can be presented as the Model Existence Theorem (published in 1949).<ref>{{cite journal | jstor=2267044 | url= | author=Leon Henkin | title=The completeness of the first-order functional calculus | journal=[[The Journal of Symbolic Logic]] | volume=14 | number=3 | pages=159–166 | date=Sep 1949 | doi= 10.2307/2267044| s2cid= 28935946}}
</ref> Henkin's proof was simplified by [[Gisbert Hasenjaeger]] in 1953.<ref>{{cite journal | jstor=2266326 | url= | author=Gisbert F. R. Hasenjaeger | title=Eine Bemerkung zu Henkin's Beweis für die Vollständigkeit des Prädikatenkalküls der Ersten Stufe | journal=The Journal of Symbolic Logic | volume=18 | number=1 | pages=42–48 | date=Mar 1953 | doi= 10.2307/2266326| s2cid= 45705695}}</ref>