Editing Gödel's incompleteness theorems (section)

=== Completeness ===

A set of axioms is (''syntactically'', or ''negation''-) [[complete theory|complete]] if, for any statement in the axioms' language, that statement or its negation is provable from the axioms.{{sfn|Smith|2007|p=24}} This is the notion relevant for Gödel's first Incompleteness theorem. It is not to be confused with ''semantic'' completeness, which means that the set of axioms proves all the semantic tautologies of the given language. In his [[Gödel's completeness theorem|completeness theorem]] (not to be confused with the incompleteness theorems described here), Gödel proved that first-order logic is ''semantically'' complete. But it is not syntactically complete, since there are sentences expressible in the language of first-order logic that can be neither proved nor disproved from the axioms of logic alone.

In a system of mathematics, thinkers such as Hilbert believed that it was just a matter of time to find such an axiomatization that would allow one to either prove or disprove (by proving its negation) every mathematical formula.

A formal system might be syntactically incomplete by design, as logics generally are. Or it may be incomplete simply because not all the necessary axioms have been discovered or included. For example, [[Euclidean geometry]] without the [[parallel postulate]] is incomplete, because some statements in the language (such as the parallel postulate itself) can not be proved from the remaining axioms. Similarly, the theory of [[dense linear order]]s is not complete, but becomes complete with an extra axiom stating that there are no endpoints in the order. The [[continuum hypothesis]] is a statement in the language of [[Zermelo–Fraenkel set theory|ZFC]] that is not provable within ZFC, so ZFC is not complete. In this case, there is no obvious candidate for a new axiom that resolves the issue.

The theory of first-order [[Peano arithmetic]] seems consistent. Assuming this is indeed the case, note that it has an infinite but recursively enumerable set of axioms, and can encode enough arithmetic for the hypotheses of the incompleteness theorem. Thus by the first incompleteness theorem, Peano Arithmetic is not complete. The theorem gives an explicit example of a statement of arithmetic that is neither provable nor disprovable in Peano's arithmetic. Moreover, this statement is true in the usual [[Model theory|model]]. In addition, no effectively axiomatized, consistent extension of Peano arithmetic can be complete.