Editing Consistency (section)

==Consistency and completeness in arithmetic and set theory==
In theories of arithmetic, such as [[Peano arithmetic]], there is an intricate relationship between the consistency of the theory and its [[completeness (logic)|completeness]]. A theory is complete if, for every formula φ in its language, at least one of φ or ¬φ is a logical consequence of the theory.

[[Presburger arithmetic]] is an axiom system for the natural numbers under addition. It is both consistent and complete.

[[Gödel's incompleteness theorems]] show that any sufficiently strong [[recursively enumerable]] theory of arithmetic cannot be both complete and consistent. Gödel's theorem applies to the theories of [[Peano arithmetic]] (PA) and [[primitive recursive arithmetic]] (PRA), but not to [[Presburger arithmetic]].

Moreover, Gödel's second incompleteness theorem shows that the consistency of sufficiently strong recursively enumerable theories of arithmetic can be tested in a particular way. Such a theory is consistent if and only if it does ''not'' prove a particular sentence, called the Gödel sentence of the theory, which is a formalized statement of the claim that the theory is indeed consistent. Thus the consistency of a sufficiently strong, recursively enumerable, consistent theory of arithmetic can never be proven in that system itself. The same result is true for recursively enumerable theories that can describe a strong enough fragment of arithmetic&mdash;including set theories such as [[Zermelo–Fraenkel set theory]] (ZF).  These set theories cannot prove their own Gödel sentence—provided that they are consistent, which is generally believed.

Because consistency of ZF is not provable in ZF, the weaker notion '''{{vanchor|relative consistency}}''' is interesting in set theory (and in other sufficiently expressive axiomatic systems). If ''T'' is a [[theory (mathematical logic)|theory]] and ''A'' is an additional [[axiom]], ''T'' + ''A'' is said to be consistent relative to ''T'' (or simply that ''A'' is consistent with ''T'') if it can be proved that
if ''T'' is consistent then ''T'' + ''A'' is consistent. If both ''A'' and ¬''A'' are consistent with ''T'', then ''A'' is said to be [[Independence (mathematical logic)|independent]] of ''T''.