Editing Gödel's completeness theorem (section)

==Relationship to the incompleteness theorems==

[[Gödel's incompleteness theorems]] show that there are inherent limitations to what can be proven within any given first-order theory in mathematics. The "incompleteness" in their name refers to another meaning of ''complete'' (see [[Model theory#Using the compactness and completeness theorems|model theory – Using the compactness and completeness theorems]]): A theory <math>T</math> is complete (or decidable) if every sentence <math>S</math> in the language of <math>T</math> is either provable (<math>T\vdash S</math>) or disprovable (<math>T\vdash \neg S</math>).

The first incompleteness theorem states that any <math>T</math> which is [[consistent]], [[effectively computable|effective]] and contains [[Robinson arithmetic]] ("''Q''") must be incomplete in this sense, by explicitly constructing a sentence <math>S_T</math> which is demonstrably neither provable nor disprovable within <math>T</math>. The second incompleteness theorem extends this result by showing that <math>S_T</math> can be chosen so that it expresses the consistency of <math>T</math> itself.

Since <math>S_T</math> cannot be proven in <math>T</math>, the completeness theorem implies the existence of a model of <math>T</math> in which <math>S_T</math> is false. In fact, <math>S_T</math> is a [[Arithmetical hierarchy|Π<sub>1</sub> sentence]], i.e. it states that some finitistic property is true of all natural numbers; so if it is false, then some natural number is a counterexample. If this counterexample existed within the standard natural numbers, its existence would disprove <math>S_T</math> within <math>T</math>; but the incompleteness theorem showed this to be impossible, so the counterexample must not be a standard number, and thus any model of <math>T</math> in which <math>S_T</math> is false must include [[Non-standard model of arithmetic|non-standard numbers]].

In fact, the model of ''any'' theory containing ''Q'' obtained by the systematic construction of the arithmetical model existence theorem, is ''always'' non-standard with a non-equivalent provability predicate and a non-equivalent way to interpret its own construction, so that this construction is non-recursive (as recursive definitions would be unambiguous).

Also, if <math>T</math> is at least slightly stronger than ''Q'' (e.g. if it includes induction for bounded existential formulas), then [[Tennenbaum's theorem]] shows that it has no recursive non-standard models.