Editing Peano axioms (section)

== Peano arithmetic as first-order theory ==

All of the Peano axioms except the ninth axiom (the induction axiom) are statements in [[first-order logic]].{{sfn|Partee|Ter Meulen|Wall|2012|page=215}} The arithmetical operations of addition and multiplication and the order relation can also be defined using first-order axioms. The axiom of induction above is [[second-order logic|second-order]], since it [[Quantifier (logic)|quantifies]] over predicates (equivalently, sets of natural numbers rather than natural numbers). As an alternative one can consider a first-order ''[[axiom schema]]'' of induction. Such a schema includes one axiom per predicate definable in the first-order language of Peano arithmetic, making it weaker than the second-order axiom.{{sfnp|Harsanyi|1983}} The reason that it is weaker is that the number of predicates in first-order language is countable, whereas the number of sets of natural numbers is uncountable. Thus, there exist sets that cannot be described in first-order language (in fact, most sets have this property).

First-order axiomatizations of Peano arithmetic have another technical limitation. In second-order logic, it is possible to define the addition and multiplication operations from the [[successor function|successor operation]], but this cannot be done in the more restrictive setting of first-order logic. Therefore, the addition and multiplication operations are directly included in the [[signature (logic)|signature]] of Peano arithmetic, and axioms are included that relate the three operations to each other.

The following list of axioms (along with the usual axioms of equality), which contains six of the seven axioms of [[Robinson arithmetic]], is sufficient for this purpose:{{sfn|Mendelson|1997|page=155}}

* <math>\forall x \ (0 \neq  S ( x ))</math>
* <math>\forall x, y \ (S( x ) =  S( y ) \Rightarrow x = y)</math>
* <math>\forall x \ (x  + 0 = x )</math>
* <math>\forall x, y \ (x + S( y ) =  S( x + y ))</math>
* <math>\forall x \ (x \cdot 0 = 0)</math>
* <math>\forall x, y \ (x \cdot  S ( y ) = x \cdot y + x )</math>

In addition to this list of numerical axioms, Peano arithmetic contains the induction schema, which consists of a [[Recursively enumerable set|recursively enumerable]] and even decidable set of [[axioms]]. For each formula {{nowrap|''φ''(''x'', ''y''<sub>1</sub>, ..., ''y''<sub>''k''</sub>)}} in the language of Peano arithmetic, the '''first-order induction axiom''' for ''φ'' is the sentence

:<math>\forall \bar{y} \Bigg(\bigg(\varphi(0,\bar{y}) \land \forall x \Big( \varphi(x,\bar{y})\Rightarrow\varphi(S(x),\bar{y})\Big)\bigg) \Rightarrow \forall x \varphi(x,\bar{y})\Bigg)</math>

where <math>\bar{y}</math> is an abbreviation for ''y''<sub>1</sub>,...,''y''<sub>''k''</sub>. The first-order induction schema includes every instance of the first-order induction axiom; that is, it includes the induction axiom for every formula ''φ''.

=== Equivalent axiomatizations ===
The above axiomatization of Peano arithmetic uses a signature that only has symbols for zero as well as the successor, addition, and multiplications operations. There are many other different, but equivalent, axiomatizations. One such alternative{{sfn|Kaye|1991|pages=16–18}} uses an order relation symbol instead of the successor operation and the language of [[Semiring#Discretely ordered semirings|discretely ordered semirings]] (axioms 1-7 for semirings, 8-10 on order, 11-13 regarding compatibility, and 14-15 for discreteness):
<!-- These axioms are taken directly from Kaye 1991. Please don't "tweak" them, add additional axioms, or remove axioms without discussion on the talk page. -->
# <math>\forall x, y, z \ ( (x + y) + z = x + (y + z) )</math>, i.e., addition is [[associative property|associative]].
# <math>\forall x, y \ ( x + y = y + x )</math>, i.e., addition is [[commutative property|commutative]].
# <math>\forall x, y, z \ ( (x \cdot y) \cdot z = x \cdot (y \cdot z) )</math>, i.e., multiplication is associative.
# <math>\forall x, y \ ( x \cdot y = y \cdot x )</math>, i.e., multiplication is commutative.
# <math>\forall x, y, z \ ( x \cdot (y + z) = (x \cdot y) + (x \cdot z) )</math>, i.e., multiplication [[distributive property|distributes]] over addition.
# <math>\forall x \ ( x + 0 = x \land x \cdot 0 = 0 )</math>, i.e., zero is an [[identity element|identity]] for addition, and an [[absorbing element]] for multiplication (actually superfluous{{NoteTag|"<math> \forall x \ ( x \cdot 0 = 0 ) </math>" can be proven from the other axioms (in first-order logic) as follows. Firstly, <math> x \cdot 0 + x \cdot 0 = x \cdot (0+0) = x \cdot 0 = x \cdot 0 + 0 </math> by distributivity and additive identity. Secondly, <math> x \cdot 0 = 0 \lor x \cdot 0 > 0 </math> by Axiom 15. If <math> x \cdot 0 > 0 </math> then <math> x \cdot 0 + x \cdot 0 > x \cdot 0 + 0 </math> by addition of the same element and commutativity, and hence <math> x \cdot 0 + 0 > x \cdot 0 + 0 </math> by substitution, contradicting irreflexivity. Therefore it must be that <math> x \cdot 0 = 0 </math>.}}).
# <math>\forall x \ ( x \cdot 1 = x )</math>, i.e., one is an [[identity element|identity]] for multiplication.
# <math>\forall x, y, z \ ( x < y \land y < z \Rightarrow x < z )</math>, i.e., the '&lt;' operator is [[Transitive relation|transitive]].
# <math>\forall x \ ( \neg (x < x) )</math>, i.e., the '&lt;' operator is [[Reflexive relation|irreflexive]].
# <math>\forall x, y \ ( x < y \lor x = y \lor y < x )</math>, i.e., the ordering satisfies [[trichotomy (mathematics)|trichotomy]].
# <math>\forall x, y, z \ ( x < y \Rightarrow x + z < y + z )</math>, i.e. the ordering is preserved under addition of the same element.
# <math>\forall x, y, z \ ( 0 < z \land x < y \Rightarrow x \cdot z < y \cdot z )</math>, i.e. the ordering is preserved under multiplication by the same positive element.
# <math>\forall x, y \ ( x < y \Rightarrow \exists z \ ( x + z = y ) )</math>, i.e. given any two distinct elements, the larger is the smaller plus another element.
# <math>0 < 1 \land \forall x \ ( x > 0 \Rightarrow x \ge 1 )</math>, i.e. zero and one are distinct and there is no element between them. In other words, 0 is [[Covering relation|covered]] by 1, which suggests that these numbers are discrete.
# <math>\forall x \ ( x \ge 0 )</math>, i.e. zero is the minimum element.

The theory defined by these axioms is known as '''PA<sup>−</sup>'''. It is also incomplete and one of its important properties is that any structure <math>M</math> satisfying this theory has an initial segment (ordered by <math>\le</math>) isomorphic to <math>\N</math>. Elements in that segment are called '''standard''' elements, while other elements are called '''nonstandard''' elements. 

Finally, Peano arithmetic '''PA''' is obtained by adding the first-order induction schema.

=== Undecidability and incompleteness ===

According to [[Gödel's incompleteness theorems]], the theory of '''PA''' (if consistent) is incomplete. Consequently, there are sentences of [[first-order logic]] (FOL) that are true in the standard model of '''PA''' but are not a consequence of the FOL axiomatization. Essential incompleteness already arises for theories with weaker axioms, such as [[Robinson arithmetic]]. 

Closely related to the above incompleteness result (via [[Gödel's completeness theorem]] for FOL) it follows that there is no [[algorithm]] for deciding whether a given FOL sentence is a consequence of a first-order axiomatization of Peano arithmetic or not. Hence, '''PA''' is an example of an [[Decidability_(logic)#Decidability_of_a_theory|undecidable theory]]. Undecidability arises already for the existential sentences of '''PA''', due to the negative answer to [[Hilbert's tenth problem]], whose proof implies that all [[computably enumerable]] sets are [[diophantine set]]s, and thus definable by existentially quantified formulas (with free variables) of '''PA'''. Formulas of '''PA''' with higher [[quantifier rank]] (more quantifier alternations) than existential formulas are more expressive, and define sets in the higher levels of the [[arithmetical hierarchy]].

=== Nonstandard models ===

{{Main|Non-standard model of arithmetic}}
Although the usual [[natural number]]s satisfy the axioms of [[#Equivalent axiomatizations|PA]], there are other models as well (called "[[non-standard model]]s"); the [[compactness theorem]] implies that the existence of nonstandard elements cannot be excluded in first-order logic.{{sfn|Hermes|1973|loc=VI.4.3|ps=, presenting a theorem of [[Thoralf Skolem]]}} The upward [[Löwenheim–Skolem theorem]] shows that there are nonstandard models of PA of all infinite cardinalities. This is not the case for the original (second-order) Peano axioms, which have only one model, up to isomorphism.{{sfn|Hermes|1973|loc=VI.3.1}} This illustrates one way the first-order system PA is weaker than the second-order Peano axioms.

When interpreted as a proof within a first-order [[set theory]], such as [[Zermelo–Fraenkel set theory|ZFC]], Dedekind's categoricity proof for PA shows that each model of set theory has a unique model of the Peano axioms, up to isomorphism, that embeds as an initial segment of all other models of PA contained within that model of set theory. In the standard model of set theory, this smallest model of PA is the standard model of PA; however, in a nonstandard model of set theory, it may be a nonstandard model of PA. This situation cannot be avoided with any first-order formalization of set theory.

It is natural to ask whether a countable nonstandard model can be explicitly constructed. The answer is affirmative as [[Skolem]] in 1933 provided an explicit construction of such a [[Non-standard model of arithmetic|nonstandard model]].  On the other hand, [[Tennenbaum's theorem]], proved in 1959, shows that there is no countable nonstandard model of PA in which either the addition or multiplication operation is [[computable function|computable]].{{sfn|Kaye|1991|loc=Section 11.3}} This result shows it is difficult to be completely explicit in describing the addition and multiplication operations of a countable nonstandard model of PA. There is only one possible [[order type]] of a countable nonstandard model. Letting ''ω'' be the order type of the natural numbers, ''ζ'' be the order type of the integers, and ''η'' be the order type of the rationals, the order type of any countable nonstandard model of PA is {{nowrap|''ω'' + ''ζ''·''η''}}, which can be visualized as a copy of the natural numbers followed by a dense linear ordering of copies of the integers.

==== Overspill ====

A '''cut''' in a nonstandard model ''M'' is a nonempty subset ''C'' of ''M'' so that ''C'' is downward closed (''x'' < ''y'' and ''y'' &isin; ''C'' ⇒ ''x'' &isin; ''C'') and ''C'' is closed under successor. A '''proper cut''' is a cut that is a proper subset of ''M''. Each nonstandard model has many proper cuts, including one that corresponds to the standard natural numbers.   However, the induction scheme in Peano arithmetic prevents any proper cut from being definable.  The overspill lemma, first proved by Abraham Robinson, formalizes this fact.

{{math theorem|name=Overspill lemma{{sfn|Kaye|1991|pages=70ff.}}|math_statement= Let ''M'' be a nonstandard model of PA and let ''C'' be a proper cut of ''M''. Suppose that <math>\bar a</math> is a tuple of elements of ''M'' and <math>\varphi(x, \bar a)</math> is a formula in the language of arithmetic so that
:<math>M \vDash \varphi(b, \bar a)</math> for all ''b'' &isin; ''C''.
Then there is a ''c'' in ''M'' that is greater than every element of ''C'' such that
:<math>M \vDash \varphi(c, \bar a).</math>
}}