In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are a set of axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly unchanged in a number of metamathematical investigations, including research into fundamental questions of consistency and completeness of number theory.
The need for formalism in arithmetic was not well appreciated until the work of Hermann Grassmann, who showed in the 1860s that many facts in arithmetic could be derived from more basic facts about the successor operation and induction.^{[1]} In 1881, Charles Sanders Peirce provided an axiomatization of naturalnumber arithmetic.^{[2]} In 1888, Richard Dedekind proposed a collection of axioms about the numbers, and in 1889 Peano published a more precisely formulated version of them as a collection of axioms in his book, The principles of arithmetic presented by a new method (Latin: Arithmetices principia, nova methodo exposita).
The Peano axioms contain three types of statements. The first axiom asserts the existence of at least one member of the set "number". The next four are general statements about equality; in modern treatments these are often not taken as part of the Peano axioms, but rather as axioms of the "underlying logic".^{[3]} The next three axioms are firstorder statements about natural numbers expressing the fundamental properties of the successor operation. The ninth, final axiom is a second order statement of the principle of mathematical induction over the natural numbers. A weaker firstorder system called Peano arithmetic is obtained by explicitly adding the addition and multiplication operation symbols and replacing the secondorder induction axiom with a firstorder axiom schema.
The axioms
When Peano formulated his axioms, the language of mathematical logic was in its infancy. The system of logical notation he created to present the axioms did not prove to be popular, although it was the genesis of the modern notation for set membership (∈, which comes from Peano's ε) and implication (⊃, which comes from Peano's reversed 'C'.) Peano maintained a clear distinction between mathematical and logical symbols, which was not yet common in mathematics; such a separation had first been introduced in the Begriffsschrift by Gottlob Frege, published in 1879.^{[4]} Peano was unaware of Frege's work and independently recreated his logical apparatus based on the work of Boole and Schröder.^{[5]}
The Peano axioms define the arithmetical properties of natural numbers, usually represented as a set N or $\backslash mathbb\{N\}.$ The signature (a formal language's nonlogical symbols) for the axioms includes a constant symbol 0 and a unary function symbol S.
The constant 0 is assumed to be a natural number:
 0 is a natural number.
The next four axioms describe the equality relation. Since they are logically valid in firstorder logic with equality, they are not considered to be part of "the Peano axioms" in modern treatments.^{[6]}
 For every natural number x, x = x. That is, equality is reflexive.
 For all natural numbers x and y, if x = y, then y = x. That is, equality is symmetric.
 For all natural numbers x, y and z, if x = y and y = z, then x = z. That is, equality is transitive.
 For all a and b, if a is a natural number and a = b, then b is also a natural number. That is, the natural numbers are closed under equality.
The remaining axioms define the arithmetical properties of the natural numbers. The naturals are assumed to be closed under a singlevalued "successor" function S.
 For every natural number n, S(n) is a natural number.
Peano's original formulation of the axioms used 1 instead of 0 as the "first" natural number. This choice is arbitrary, as axiom 1 does not endow the constant 0 with any additional properties. However, because 0 is the additive identity in arithmetic, most modern formulations of the Peano axioms start from 0. Axioms 1 and 6 define a unary representation of the natural numbers: the number 1 can be defined as S(0), 2 as S(S(0)) (which is also S(1)), and, in general, any natural number n as the result of nfold application of S to 0, denoted as S^{n}(0). The next two axioms define the properties of this representation.
 For every natural number n, S(n) = 0 is false. That is, there is no natural number whose successor is 0.
 For all natural numbers m and n, if S(m) = S(n), then m = n. That is, S is an injection.
Axioms 1, 6, 7 and 8 imply that the set of natural numbers contains the distinct elements 0, S(0), S(S(0)), and furthermore that {0, S(0), S(S(0)), …} ⊆ N. This shows that the set of natural numbers is infinite. However, to show that N = {0, S(0), S(S(0)), …}, it must be shown that N ⊆ {0, S(0), S(S(0)), …}; i.e., it must be shown that every natural number is included in {0, S(0), S(S(0)), …}. To do this however requires an additional axiom, which is sometimes called the axiom of induction. This axiom provides a method for reasoning about the set of all natural numbers.

If K is a set such that:
 0 is in K, and
 for every natural number n, if n is in K, then S(n) is in K,
then K contains every natural number.
The induction axiom is sometimes stated in the following form:
 If φ is a unary predicate such that:
 φ(0) is true, and
 for every natural number n, if φ(n) is true, then φ(S(n)) is true,
then φ(n) is true for every natural number n.
In Peano's original formulation, the induction axiom is a secondorder axiom. It is now common to replace this secondorder principle with a weaker firstorder induction scheme. There are important differences between the secondorder and firstorder formulations, as discussed in the section Models below.
Arithmetic
The Peano axioms can be augmented with the operations of addition and multiplication and the usual total (linear) ordering on N. The respective functions and relations are constructed in secondorder logic, and are shown to be unique using the Peano axioms.
Addition
Addition is the function + : N × N → N (written in the usual infix notation, mapping two elements of N to another element of N), defined recursively as:
 $\backslash begin\{align\}$
a + 0 &= a ,\\
a + S (b) &= S (a + b).
\end{align}
For example,
 a + 1 = a + S(0) = S(a + 0) = S(a).
The structure (N, +) is a commutative semigroup with identity element 0. (N, +) is also a cancellative magma, and thus embeddable in a group. The smallest group embedding N is the integers.
Multiplication
Given addition, multiplication is the function · : N × N → N defined recursively as:
 $\backslash begin\{align\}$
a \cdot 0 &= 0, \\
a \cdot S (b) &= a + (a \cdot b).
\end{align}
It is easy to see that setting b equal to 0 yields the multiplicative identity:
 a · 1 = a · S(0) = a + (a · 0) = a + 0 = a
Moreover, multiplication distributes over addition:
 a · (b + c) = (a · b) + (a · c).
Thus, (N, +, 0, ·, 1) is a commutative semiring.
Inequalities
The usual total order relation ≤ : N × N can be defined as follows, assuming 0 is a natural number:
 For all a, b ∈ N, a ≤ b if and only if there exists some c ∈ N such that a + c = b.
This relation is stable under addition and multiplication: for $a,\; b,\; c\; \backslash in\; N$, if a ≤ b, then:
 a + c ≤ b + c, and
 a · c ≤ b · c.
Thus, the structure (N, +, ·, 1, 0, ≤) is an ordered semiring; because there is no natural number between 0 and 1, it is a discrete ordered semiring. The axiom of induction is sometimes stated in the following strong form, making use of the ≤ order:
 For any predicate φ, if
 φ(0) is true, and
 for every n, k ∈ N, if k ≤ n implies φ(k) is true, then φ(S(n)) is true,
 then for every n ∈ N, φ(n) is true.
This form of the induction axiom is a simple consequence of the standard formulation, but is often better suited for reasoning about the ≤ order. For example, to show that the naturals are wellordered—every nonempty subset of N has a least element—one can reason as follows. Let a nonempty X ⊆ N be given and assume X has no least element.
 Because 0 is the least element of N, it must be that 0 ∉ X.
 For any n ∈ N, suppose for every k ≤ n, k ∉ X. Then S(n) ∉ X, for otherwise it would be the least element of X.
Thus, by the strong induction principle, for every n ∈ N, n ∉ X. Thus, X ∩ N = ∅, which contradicts X being a nonempty subset of N. Thus X has a least element.
Firstorder theory of arithmetic
Firstorder theories are often better than second order theories for model or proof theoretic analysis. All of the Peano axioms except the ninth axiom (the induction axiom) are statements in firstorder logic. The arithmetical operations of addition and multiplication and the order relation can also be defined using firstorder axioms. The secondorder axiom of induction can be transformed into a weaker firstorder induction schema.
Firstorder axiomatizations of Peano arithmetic have an important limitation, however. In secondorder logic, it is possible to define the addition and multiplication operations from the successor operation, but this cannot be done in the more restrictive setting of firstorder logic. Therefore, the addition and multiplication operations are directly included in the 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) is sufficient for this purpose:^{[7]}
 ∀x_{1}∈N. 0 ≠ S(x_{1})
 ∀x_{1},x_{2}∈N. S(x_{1}) = S(x_{2}) ⇒ x_{1} = x_{2}
 ∀x_{1}∈N. x_{1} + 0 = x_{1}
 ∀x_{1},x_{2}∈N. x_{1} + S(x_{2}) = S(x_{1} + x_{2})
 ∀x_{1}∈N. x_{1} ⋅ 0 = 0
 ∀x_{1},x_{2}∈N. x_{1} ⋅ S(x_{2}) = x_{1} ⋅ x_{2} + x_{1}
In addition to this list of numerical axioms, Peano arithmetic contains the induction schema, which consists of a countably infinite set of axioms. For each formula φ(x,y_{1},...,y_{k}) in the language of Peano arithmetic, the firstorder induction axiom for φ is the sentence
 $\backslash forall\; \backslash bar\{y\}\; (\backslash phi(0,\backslash bar\{y\})\; \backslash land\; \backslash forall\; x\; (\; \backslash phi(x,\backslash bar\{y\})\backslash Rightarrow\backslash phi(S(x),\backslash bar\{y\}))\; \backslash Rightarrow\; \backslash forall\; x\; \backslash phi(x,\backslash bar\{y\}))$
where $\backslash bar\{y\}$ is an abbreviation for y_{1},...,y_{k}. The firstorder induction schema includes every instance of the firstorder induction axiom, that is, it includes the induction axiom for every formula φ.
This schema avoids quantification over sets of natural numbers, which is impossible in firstorder logic. For instance, it is not possible in firstorder logic to say that any set of natural numbers containing 0 and closed under successor is the entire set of natural numbers. What can be expressed is that any definable set of natural numbers has this property. Because it is not possible to quantify over definable subsets explicitly with a single axiom, the induction schema includes one instance of the induction axiom for every definition of a subset of the naturals.
Equivalent axiomatizations
There are many different, but equivalent, axiomatizations of Peano arithmetic. While some axiomatizations, such as the one just described, use a signature that only has symbols for 0 and the successor, addition, and multiplications operations, other axiomatizations use the language of ordered semirings, including an additional order relation symbol. One such axiomatization begins with the following axioms that describe a discrete ordered semiring.^{[8]}
 $\backslash forall\; x,\; y,\; z\; \backslash in\; N$. $(x\; +\; y)\; +\; z\; =\; x\; +\; (y\; +\; z)$, i.e., addition is associative.
 $\backslash forall\; x,\; y\; \backslash in\; N$. $x\; +\; y\; =\; y\; +\; x$, i.e., addition is commutative.
 $\backslash forall\; x,\; y,\; z\; \backslash in\; N$. $(x\; \backslash cdot\; y)\; \backslash cdot\; z\; =\; x\; \backslash cdot\; (y\; \backslash cdot\; z)$, i.e., multiplication is associative.
 $\backslash forall\; x,\; y\; \backslash in\; N$. $x\; \backslash cdot\; y\; =\; y\; \backslash cdot\; x$, i.e., multiplication is commutative.
 $\backslash forall\; x,\; y,\; z\; \backslash in\; N$. $x\; \backslash cdot\; (y\; +\; z)\; =\; (x\; \backslash cdot\; y)\; +\; (x\; \backslash cdot\; z)$, i.e., the distributive law.
 $\backslash forall\; x\; \backslash in\; N$. $x\; +\; 0\; =\; x\; \backslash and\; x\; \backslash cdot\; 0\; =\; 0$, i.e., zero is the identity element for addition.
 $\backslash forall\; x\; \backslash in\; N$. $x\; \backslash cdot\; 1\; =\; x$, i.e., one is the identity element for multiplication.
 $\backslash forall\; x,\; y,\; z\; \backslash in\; N$. $x\; <\; y\; \backslash and\; y\; <\; z\; \backslash Rightarrow\; x\; <\; z$, i.e., the '<' operator is transitive.
 $\backslash forall\; x\; \backslash in\; N$. $\backslash neg\; (x\; <\; x)$, i.e., the '<' operator is irreflexive.
 $\backslash forall\; x,\; y\; \backslash in\; N$. $x\; <\; y\; \backslash or\; x\; =\; y\; \backslash or\; y\; <\; x$.
 $\backslash forall\; x,\; y,\; z\; \backslash in\; N$. $x\; <\; y\; \backslash Rightarrow\; x\; +\; z\; <\; y\; +\; z$.
 $\backslash forall\; x,\; y,\; z\; \backslash in\; N$. $0\; <\; z\; \backslash and\; x\; <\; y\; \backslash Rightarrow\; x\; \backslash cdot\; z\; <\; y\; \backslash cdot\; z$.
 $\backslash forall\; x,\; y\; \backslash in\; N$. $x\; <\; y\; \backslash Rightarrow\; \backslash exists\; z\; \backslash in\; N$. $x\; +\; z\; =\; y$.
 $0\; <\; 1\; \backslash and\; \backslash forall\; x\; \backslash in\; N$. $x\; >\; 0\; \backslash Rightarrow\; x\; \backslash geq\; 1$.
 $\backslash forall\; x\; \backslash in\; N$. $x\; \backslash geq\; 0$.
The theory defined by these axioms is known as PA^{–}; PA is obtained by adding the firstorder induction schema.
An important property of PA^{–} is that any structure M satisfying this theory has an initial segment (ordered by ≤) isomorphic to N. Elements of M \ N are known as nonstandard elements.
Models
A model of the Peano axioms is a triple (N, 0, S), where N is a (necessarily infinite) set, 0 ∈ N and S : N → N satisfies the axioms above. Dedekind proved in his 1888 book, What are numbers and what should they be (German: Was sind und was sollen die Zahlen) that any two models of the Peano axioms (including the secondorder induction axiom) are isomorphic. In particular, given two models (N_{A}, 0_{A}, S_{A}) and (N_{B}, 0_{B}, S_{B}) of the Peano axioms, there is a unique homomorphism f : N_{A} → N_{B} satisfying
 $\backslash begin\{align\}$
f(0_A) &= 0_B \\
f(S_A (n)) &= S_B (f (n))
\end{align}
and it is a bijection. The secondorder Peano axioms are thus categorical; this is not the case with any firstorder reformulation of the Peano axioms, however.
Nonstandard models
Although the usual natural numbers satisfy the axioms of PA, there are other nonstandard models as well; the compactness theorem implies that the existence of nonstandard elements cannot be excluded in firstorder logic. 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 (secondorder) Peano axioms, which have only one model, up to isomorphism. This illustrates one way the firstorder system PA is weaker than the secondorder Peano axioms.
When interpreted as a proof within a firstorder set theory, such as 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 firstorder formalization of set theory.
It is natural to ask whether a countable nonstandard model can be explicitly constructed. 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.^{[9]} This result shows it is difficult to be completely explicit in describing the addition and multiplication operations of a countable nonstandard model of PA. However, 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 ω + ζ·η, which can be visualized as a copy of the natural numbers followed by a dense linear ordering of copies of the integers.
Settheoretic models
The Peano axioms can be derived from set theoretic constructions of the natural numbers and axioms of set theory such as the ZF.^{[10]} The standard construction of the naturals, due to John von Neumann, starts from a definition of 0 as the empty set, ∅, and an operator s on sets defined as:
 s(a) = a ∪ { a }.
The set of natural numbers N is defined as the intersection of all sets closed under s that contain the empty set. Each natural number is equal (as a set) to the set of natural numbers less than it:
 $\backslash begin\{align\}$
0 &= \emptyset \\
1 &= s(0) = s(\emptyset) = \emptyset \cup \{ \emptyset \} = \{ \emptyset \} = \{ 0 \} \\
2 &= s(1) = s(\{ 0 \}) = \{ 0 \} \cup \{ \{ 0 \} \} = \{ 0 , \{ 0 \} \} = \{ 0, 1 \} \\
3 &= ... = \{ 0, 1, 2 \}
\end{align}
and so on. The set N together with 0 and the successor function s : N → N satisfies the Peano axioms.
Peano arithmetic is equiconsistent with several weak systems of set theory.^{[11]} One such system is ZFC with the axiom of infinity replaced by its negation. Another such system consists of general set theory (extensionality, existence of the empty set, and the axiom of adjunction), augmented by an axiom schema stating that a property that holds for the empty set and holds of an adjunction whenever it holds of the adjunct must hold for all sets.
Interpretation in category theory
The Peano axioms can also be understood using category theory. Let C be a category with terminal object 1_{C}, and define the category of pointed unary systems, US_{1}(C) as follows:
 The objects of US_{1}(C) are triples (X, 0_{X}, S_{X}) where X is an object of C, and 0_{X} : 1_{C} → X and S_{X} : X → X are Cmorphisms.
 A morphism φ : (X, 0_{X}, S_{X}) → (Y, 0_{Y}, S_{Y}) is a Cmorphism φ : X → Y with φ 0_{X} = 0_{Y} and φ S_{X} = S_{Y} φ.
Then C is said to satisfy the Dedekind–Peano axioms if US_{1}(C) has an initial object; this initial object is known as a natural number object in C. If (N, 0, S) is this initial object, and (X, 0_{X}, S_{X}) is any other object, then the unique map u : (N, 0, S) → (X, 0_{X}, S_{X}) is such that
 $\backslash begin\{align\}$
u 0 &= 0_X, \\
u (S x) &= S_X (u x).
\end{align}
This is precisely the recursive definition of 0_{X} and S_{X}.
Consistency
When the Peano axioms were first proposed, Bertrand Russell and others agreed that these axioms implicitly defined what we mean by a "natural number". Henri Poincaré was more cautious, saying they only defined natural numbers if they were consistent; if there is a proof that starts from just these axioms and derives a contradiction such as 0 = 1, then the axioms are inconsistent, and don't define anything. In 1900, David Hilbert posed the problem of proving their consistency using only finitistic methods as the second of his twentythree problems.^{[12]} In 1931, Kurt Gödel proved his second incompleteness theorem, which shows that such a consistency proof cannot be formalized within Peano arithmetic itself.^{[13]}
Although it is widely claimed that Gödel's theorem rules out the possibility of a finitistic consistency proof for Peano arithmetic, this depends on exactly what one means by a finitistic proof. Gödel himself pointed out the possibility of giving a finitistic consistency proof of Peano arithmetic or stronger systems by using finitistic methods that are not formalizable in Peano arithmetic, and in 1958 Gödel published a method for proving the consistency of arithmetic using type theory.^{[14]} In 1936, Gerhard Gentzen gave a proof of the consistency of Peano's axioms, using transfinite induction up to an ordinal called ε_{0}.^{[15]} Gentzen explained: "The aim of the present paper is to prove the consistency of elementary number theory or, rather, to reduce the question of consistency to certain fundamental principles". Gentzen's proof is arguably finitistic, since the transfinite ordinal ε_{0} can be encoded in terms of finite objects (for example, as a Turing machine describing a suitable order on the integers, or more abstractly as consisting of the finite trees, suitably linearly ordered). Whether or not Gentzen's proof meets the requirements Hilbert envisioned is unclear: there is no generally accepted definition of exactly what is meant by a finitistic proof, and Hilbert himself never gave a precise definition.
The vast majority of contemporary mathematicians believe that Peano's axioms are consistent, relying either on intuition or the acceptance of a consistency proof such as Gentzen's proof. The small number of mathematicians who advocate ultrafinitism reject Peano's axioms because the axioms require an infinite set of natural numbers.
See also
References
 Martin Davis, 1974. Computability. Notes by Barry Jacobs. Courant Institute of Mathematical Sciences, New York University.
 . Two English translations:
 1963 (1901). . Beman, W. W., ed. and trans. Dover.
 1996. In From Kant to Hilbert: A Source Book in the Foundations of Mathematics, 2 vols, Ewald, William B., ed. Oxford University Press: 787–832.
 Gentzen, G., 1936, Die Widerspruchsfreiheit der reinen Zahlentheorie. Mathematische Annalen 112: 132–213. Reprinted in English translation in his 1969 Collected works, M. E. Szabo, ed. Amsterdam: NorthHolland.
 . See On Formally Undecidable Propositions of Principia Mathematica and Related Systems for details on English translations.
 , 1958, "Über eine bisher noch nicht benüzte Erweiterung des finiten Standpunktes," Dialectica 12: 280–87. Reprinted in English translation in 1990. Gödel's Collected Works, Vol II. Solomon Feferman et al., eds. Oxford University Press.

 Hatcher, William S., 1982. The Logical Foundations of Mathematics. Pergamon. Derives the Peano axioms (called S) from several axiomatic set theories and from category theory.
 Mathematical Problems," Bulletin of the American Mathematical Society 8: 437–79.
 Kaye, Richard, 1991. Models of Peano arithmetic. Oxford University Press. ISBN 019853213X.
 Reprinted (CP 3.25288), (W 4:299309).
 Paul Shields. (1997), "Peirce’s Axiomatization of Arithmetic", in Houser et al., eds., Studies in the Logic of Charles S. Peirce.
 Patrick Suppes, 1972 (1960). Axiomatic Set Theory. Dover. ISBN 0486616304. Derives the Peano axioms from ZFC.
 Alfred Tarski, and Givant, Steven, 1987. A Formalization of Set Theory without Variables. AMS Colloquium Publications, vol. 41.
 Edmund Landau, 1965 Grundlagen Der Analysis. AMS Chelsea Publishing. Derives the basic number systems from the Peano axioms. English/German vocabulary included. ISBN 9780828401418
 Contains translations of the following two papers, with valuable commentary:
 Richard Dedekind, 1890, "Letter to Keferstein." pp. 98–103. On p. 100, he restates and defends his axioms of 1888.
 Giuseppe Peano, 1889. Arithmetices principia, nova methodo exposita (The principles of arithmetic, presented by a new method), pp. 83–97. An excerpt of the treatise where Peano first presented his axioms, and recursively defined arithmetical operations.
This article incorporates material from PA on PlanetMath, which is licensed under the Creative Commons Attribution/ShareAlike License.
External links
 Henri Poincare" by Mauro Murzi. Includes a discussion of Poincaré's critique of the Peano's axioms.
 incompleteness theorems by Karl Podnieks.
 Template:Springer
 Template:Planetmath reference
 MathWorld.
 What are numbers, and what is their meaning?: Dedekind commentary on Dedekind's work, Stanley N. Burris, 2001.hu:Giuseppe Peano#A természetes számok Peanoaxiómái
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.