Editing Gödel's incompleteness theorems (section)

== Formal systems: completeness, consistency, and effective axiomatization ==
The incompleteness theorems apply to [[formal system]]s that are of sufficient complexity to express the basic arithmetic of the natural numbers and which are consistent and effectively axiomatized. Particularly in the context of [[first-order logic]], formal systems are also called ''formal theories''. In general, a formal system is a deductive apparatus that consists of a particular set of axioms along with rules of symbolic manipulation (or rules of inference) that allow for the derivation of new theorems from the axioms.  One example of such a system is first-order [[Peano arithmetic]], a system in which all variables are intended to denote natural numbers. In other systems, such as [[set theory]], only some sentences of the formal system express statements about the natural numbers. The incompleteness theorems are about formal provability ''within'' these systems, rather than about "provability" in an informal sense.

There are several properties that a formal system may have, including completeness, consistency, and the existence of an effective axiomatization. The incompleteness theorems show that systems which contain a sufficient amount of arithmetic cannot possess all three of these properties.

=== Effective axiomatization ===

A formal system is said to be ''effectively axiomatized'' (also called ''effectively generated'') if its set of theorems is [[recursively enumerable]]. This means that there is a computer program that, in principle, could enumerate all the theorems of the system without listing any statements that are not theorems. Examples of effectively generated theories include Peano arithmetic and [[Zermelo–Fraenkel set theory]] (ZFC).{{sfn|Franzén|2005|p=112}}

The theory known as [[true arithmetic]] consists of all true statements about the standard integers in the language of Peano arithmetic. This theory is consistent and complete, and contains a sufficient amount of arithmetic. However, it does not have a recursively enumerable set of axioms, and thus does not satisfy the hypotheses of the incompleteness theorems.

=== 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.

=== Consistency ===
A set of axioms is (simply) [[Consistency|consistent]] if there is no statement such that both the statement and its negation are provable from the axioms, and ''inconsistent'' otherwise. That is to say, a consistent axiomatic system is one that is free from contradiction.

Peano arithmetic is provably consistent from ZFC, but not from within itself. Similarly, ZFC is not provably consistent from within itself, but ZFC + "there exists an [[inaccessible cardinal]]" proves ZFC is consistent because if {{mvar|κ}} is the least such cardinal, then {{math|''V''<sub>{{mvar|κ}}</sub>}} sitting inside the [[von Neumann universe]] is a [[Inner model|model]] of ZFC, and a theory is consistent if and only if it has a model.

If one takes all statements in the language of [[Peano arithmetic]] as axioms, then this theory is complete, has a recursively enumerable set of axioms, and can describe addition and multiplication. However, it is not consistent.

Additional examples of inconsistent theories arise from the [[Naïve set theory#Paradoxes in early set theory|paradoxes]] that result when the [[Axiom schema of specification#Unrestricted comprehension|axiom schema of unrestricted comprehension]] is assumed in set theory.

=== Systems which contain arithmetic ===

The incompleteness theorems apply only to formal systems which are able to prove a sufficient collection of facts about the natural numbers. One sufficient collection is the set of theorems of [[Robinson arithmetic]] {{mvar|Q}}. Some systems, such as Peano arithmetic, can directly express statements about natural numbers. Others, such as ZFC set theory, are able to interpret statements about natural numbers into their language. Either of these options is appropriate for the incompleteness theorems.

The theory of [[algebraically closed field]]s of a given [[characteristic (algebra)|characteristic]] is complete, consistent, and has an infinite but recursively enumerable set of axioms. However it is not possible to encode the integers into this theory, and the theory cannot describe arithmetic of integers.  A similar example is the theory of [[real closed field]]s, which is essentially equivalent to [[Tarski's axioms]] for [[Euclidean geometry]]. So Euclidean geometry itself (in Tarski's formulation) is an example of a complete, consistent, effectively axiomatized theory.

The system of [[Presburger arithmetic]] consists of a set of axioms for the natural numbers with just the addition operation (multiplication is omitted). Presburger arithmetic is complete, consistent, and recursively enumerable and can encode addition but not multiplication of natural numbers, showing that for Gödel's theorems one needs the theory to encode not just addition but also multiplication.

{{harvard citations |txt=yes |first=Dan |last=Willard |author1-link=Dan Willard |year=2001}} has studied some weak families of arithmetic systems which allow enough arithmetic as relations to formalise Gödel numbering, but which are not strong enough to have multiplication as a function, and so fail to prove the second incompleteness theorem; that is to say, these systems are consistent and capable of proving their own consistency (see [[self-verifying theories]]).

=== Conflicting goals ===
In choosing a set of axioms, one goal is to be able to prove as many correct results as possible, without proving any incorrect results. For example, we could imagine a set of true axioms which allow us to prove every true arithmetical claim about the natural numbers {{harv|Smith|2007|p=2}}. In the standard system of first-order logic, an inconsistent set of axioms will prove every statement in its language (this is sometimes called the [[principle of explosion]]), and is thus automatically complete. A set of axioms that is both complete and consistent, however, proves a [[maximal set]] of non-[[Contradiction|contradictory]] theorems.{{Citation needed|date=May 2023}}

The pattern illustrated in the previous sections with Peano arithmetic, ZFC, and ZFC + "there exists an inaccessible cardinal" cannot generally be broken. Here ZFC + "there exists an inaccessible cardinal" cannot from itself, be proved consistent. It is also not complete, as illustrated by the continuum hypothesis, which is unresolvable<ref>in technical terms: [[Independence (mathematical logic)|independent]]; see [[Continuum hypothesis#Independence from ZFC]]</ref> in ZFC + "there exists an inaccessible cardinal".

The first incompleteness theorem shows that, in formal systems that can express basic arithmetic, a complete and consistent finite list of axioms can never be created: each time an additional, consistent statement is added as an axiom, there are other true statements that still cannot be proved, even with the new axiom. If an axiom is ever added that makes the system complete, it does so at the cost of making the system inconsistent. It is not even possible for an infinite list of axioms to be complete, consistent, and effectively axiomatized.