Peano axioms

In formal mathematics, the Peano axioms, also known as the Dedekind-Peano axioms or the Peano postulates, are a set of axioms for the theory of arithmetic with natural numbers, named after the 19th century Italian mathematician Giuseppe Peano. 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. 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: Árithmetices principa, nova methodo exposita). They have been used nearly unchanged in a number of metamathematical investigations, including fundamental questions of consistency and completeness of number theory.

The Peano axioms contain three types of statements. The first four statements are general statements about equality, and are usually omitted in modern presentations of the axioms. The next four axioms are first-order statements about natural numbers and form a core sometimes known as Peano arithmetic. The ninth and final axiom is a second order statement of the principle of mathematical induction over the natural numbers.

The axioms

When Peano formulated the axioms, the language of mathematical logic was in its infancy; he created a logical notation to present his axioms which didn't prove to be popular, though it was the genesis of the modern notations for set membership (∈ from Peano's ε) and implication (⊃ 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 introducted in the Begriffsschrift by Gotlob Frege, published in 1879. Peano was unaware of Frege's work and independently recreated his logical apparatus based on the work of Boole and Schröder.

The Peano axioms define the properties of a set N (natural numbers), starting with an equality relation on elements of that set specified in the first four axioms.

1. For every x ∈ N, x = x, i.e., equality is reflexive.
2. For every x, y ∈ N, if x = y, then y = x, i.e., equality is symmetric.
3. For every x, y, z ∈ N, if x = y and y = z, then x = z, i.e., equality is transitive.
4. If a ∈ N, and a = b, then b ∈ N.

The remaining axioms define the properties of the natural numbers. The set N is assumed to have a constant 0 and a function S : N → N called the successor function, specified as the following axioms:

5. 0 ∈ N.
6. For every n ∈ N, S(n) ∈ N.

Peano's original formulation of the axioms started with 1 instead of 0; however, most modern presentations of these axioms start from 0 because it is the additive identity. The successor function defines a unary representation of all natural numbers: the number 1 is S(0), 2 is S(S(0)) (= S(1)), and, in general, any natural number n is Sⁿ(0). The next two axioms define the properties of this encoding.

7. For every n ∈ N, S(n) ≠ 0. That is, there is no natural number whose successor is 0.
8. For every m, n ∈ N, if S(m) = S(n), then m = n. That is, S is an injection.

These two axioms together imply that the set N is infinite, because it contains at least the infinite subset { 0, S(0), S(S(0)), … }, no two elements of which are equal. The final axiom, sometimes called the axiom of induction, is a method of reasoning about sets of natural numbers. It is the only second order axiom.

9. If K is a set such that:
   • 0 ∈ K, and
   • for every n ∈ N, if n ∈ K, then S(n) ∈ K,
   then N ⊆ K.

The induction axiom is sometimes stated in the following form:

If φ is a unary predicate such that:

• φ(0) is true, and
• for every n ∈ N, if φ(n) is true, then φ(S(n)) is true,

then for every n ∈ N, φ(n) is true.

The two formulations are equivalent—the set K is just the characteristic set { n : φ(n) }—but the latter formulation is often better suited for logical reasoning.

Arithmetic

The Peano axioms can be augmented with the operations of addition and multiplication and the usual total ordering on N. The respective functions and relations are constructed in second-order logic, and are shown to be unique using the Peano axioms.

Addition is a function + : N × N → N (written in the usual infix notation), defined recursively as:

${\begin{aligned}a+0&=a\\b+(S(b))&=S(a+b)\end{aligned}}$

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.

Given addition, multiplication is a function · : N × N → N defined recursively as:

${\begin{aligned}a\cdot 0&=0\\a\cdot (S(b))&=a+(a\cdot b)\end{aligned}}$

It is easy to see that 1 is 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.

The usual total order relation ≤ : N × N can be defined as follows:

for a, b ∈ N, a ≤ b if there exists a c ∈ N such that a + c = b.

This relation is stable under addition and multiplication: for a, b, c ∈ 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 much better suited for reasoning about the ≤ order. For example, to show that the naturals are well-ordered—every nonempty subset of N has a least element—we reason as follows. Let 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 axiom, for every n ∈ N, n ∉ X. Thus, X ∩ N = ∅, which contradicts X ⊆ N, so X has a least element.

Models

Any triple (N, 0, S), with N an infinite set, 0 ∈ N and S : N → N an injection, forms a model of the Peano axioms; that is, it satisfies all the Peano axioms. 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 are isomorphic: given two models (N_A, 0_A, S_A) and (N_B, 0_B, S_B) of the Peano axioms, the homomorphism f : N_A → N_B defined as

${\begin{aligned}f(0_{A})&=0_{B}\\f(S_{A}(n))&=S_{B}(f(n))\end{aligned}}$

is a bijection. Thus, the Peano axioms are ω-categorical; this is not the case with any first-order reformulation of the Peano axioms, however.

First-order logic

First-order theories are often better than second order theories for model or proof theoretic analysis. All but the ninth axiom of induction are statements in first-order logic. The binary operations and the order relation can also be specified as first-order axioms. The axiom of induction can be transformed into a first-order axiom schema by adding an instance of the axiom for every countably infinite set. Together, they form a first-order axiomatization of arithmetic that is sometimes called Peano arithmetic (PA).

Different authors have given different (but equivalent) lists of axioms for Peano arithmetic; the following is due to Kaye.

1. ∀x, y, z ∈ N. (x + y) + z = x + (y + z), i.e., addition is associative.
2. ∀x, y ∈ N. x + y = y + x, i.e., addition is commutative.
3. ∀x, y, z ∈ N. (x · y) · z = x · (y · z), i.e., multiplication is associative
4. ∀x, y ∈ N. x · y = y · x, i.e., multiplication is commutative.
5. ∀x, y, z ∈ N. x · (y + z) = (x · y) + (x · z), i.e., the distributive law.
6. ∀x ∈ N. x + 0 = x ∧ x · 0 = 0.
7. ∀x ∈ N. x · 1 = x.
8. ∀x, y, z ∈ N. x < y ∧ y < z ⊃ x < xz.
9. ∀x ∈ N. ¬ (x < x).
10. ∀x, y ∈ N. x < y ∨ x = y ∨ x > y..
11. ∀x, y, z ∈ N. x < y ⊃ x + z < y + z.
12. ∀x, y, z ∈ N. 0 < z ∧ x < y ⊃ x · z < y · z.
13. ∀x, y ∈ N. x < y ⊃ ∃z ∈ N. x + z = y.
14. 0 < 1 ∧ ∀x ∈ N. x > 0 ⊃ x ≥ 1..
15. ∀x ∈ N. x ≥ 0.

This list of axioms defines PA^–, which is PA sans the induction schemata. While no explicit existential quantifiers appear in most of the above axioms, implicit quantifiers of that nature follow from the closure of the natural numbers over zero and the operations of addition and multiplication. 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.

To get from PA^– to PA, we add the following induction schema: for every predicate φ(x, y₁, …, y_k) in the language, add the following induction axiom

∀y₁, …, y_k. (φ(0, y₁, …, y_k) ∧ ∀x ∈ N. φ(x, y₁, …, y_k) ⊃ φ(x + 1, y₁, …, y_k)) ⊃ ∀x ∈ N. φ(x, y₁, …, y_k)

This schema avoids quantification over sets of natural numbers, which is impossible in first-order logic. For instance, it is not possible in first-order 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. It is not possible to quantify over definable subsets explicitly with a single axiom, but the induction schema adds one instance of the induction axiom for every definition of a subset of the naturals.

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 first-order logic. The upward Löwenheim-Skolem theorem shows that there are nonstandard models of PA of all infinite cardinalities. Dedekind's categoricality proof for PA for a first-order axiomatization of set theory, such as Zermelo–Fraenkel set theory, shows that each model of set theory has a unique model of the Peano axioms, up to isomorphism; however, nonstandard models of set theory may contain nonstandard models of PA. This is not the case for the original (second-order) Peano axioms, which certainly are ω-categoical. Thus, the first-order PA is weaker than the second-order Peano axioms.

While nonstandard models of PA^– can be constructed in set theory, Stanley Tennenbaum proved in 1959 that there is no countable nonstandard model of PA in which either the addition or multiplication operation is computable. This shows that it is difficult to be completely explicit in describing the addition and multiplication operations on a countable nonstandard model of PA.

Set-theoretic models

Main article: Set-theoretic definition of natural numbers

The Peano axioms can be derived from set theoretic constructions of the natural numbers and axioms of set theory such as the ZF. The standard construction of the naturals, due to John von Neumann, starts from a definition of 0 as the 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:

${\begin{aligned}0&=\emptyset \\1&=s(0)=\emptyset \cup \{\emptyset \}=\{\emptyset \}=\{0\}\\2&=\{0,1\}\\3&=\{0,1,2\}\end{aligned}}$

and so on. The set N together with 0 and the successor function s : N → N satisfies the Peano axioms. The induction axiom is proven using the axiom of infinity of set theory.

Peano arithmetic can be seen to be equiconsistent with several weak systems of set theory. 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 null 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.

Categorical interpretation

Let C be a category with initial object 1_C, and define the category of pointed unary systems, US₁(C) as follows:

• The objects of US₁(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 C-morphisms.
• A morphism φ : (X, 0_X, S_X) → (Y, 0_Y, S_Y) is a C-morphism φ : X → Y with φ 0_X = 0_Y and φ S_X = S_Y φ.

Then C is said to satisfy the Dedekind-Peano axioms if US₁(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

${\begin{aligned}u0&=0_{X}\\u(Sx)&=S_{X}(ux)\end{aligned}}$

This is just the recursive definition of 0_X and S_X.

Consistency

Main article: Hilbert's second problem

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 twenty-three problems. In 1931, Kurt Gödel proved his second incompleteness theorem, which shows that such a consistency proof cannot be formalized within Peano arithmetic itself.

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. In 1936, Gerhard Gentzen gave a proof of the consistency of Peano's axioms, using transfinite induction up to an ordinal called ε₀. 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 ε₀ can be encoded in terms of finite objects (for example, as a Turing machine describing a suitable order on the integers). 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

• Foundational status of arithmetic
• Gentzen's consistency proof
• General set theory
• Paris-Harrington theorem
• Pressburger arithmetic
• Robinson arithmetic
• Second-order arithmetic
• Set-theoretic definition of natural numbers

References

• Martin Davis (1974) Computability: Notes by Barry Jacobs, The Courant Institute of Mathemaatical Sciences NYU, New York.
• R. Dedekind, 1888. Was sind und was sollen die Zahlen? (What are and what should the numbers be?). Braunschweig. Two English translations:
  • 1963 (1901). Essays on the Theory of Numbers. 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.
• H. Grassmann, Lehrbuch der Arithmetik (A tutorial in arithmetics), Berlin 1861.
• William S. Hatcher, 1982. The Logical Foundations of Mathematics. Pergamon. A text on mathematical logic that carefully discusses the Peano axioms (called S), then derives them from several axiomatic systems of set theory.
• Jean van Heijenoort, ed. (1967, 1976 3rd printing with corrections). From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931 (3rd ed.). Cambridge, Mass: Harvard University Press. ISBN 0-674-32449-8 (pbk.). {{cite book}}: |author= has generic name (help); Check date values in: |year= (help); Cite has empty unknown parameter: |coauthors= (help) Contains the following two papers, each preceded with valuable commentary.
  • Richard Dedekind, Letter to Keferstein (1890) (van Heijenoort p. 98-103), in particular page 100 where he defines and defends his axioms of 1888.
  • G. Peano, Arithmetices principia, nova methodo exposita (The principles of arithmetic, presented by a new method), van Heijenoort p. 83-97, an excerpt of his treatise wherein Peano presents his axioms, and his definitions of e.g. multiplication and division.
• Richard Kaye (1991). Models of Peano arithmetic. Oxford University Press. ISBN 0-19-853213-X
• Patrick Suppes, 1972 (1960). Axiomatic Set Theory. Dover.
• Alfred Tarski, and Givant, Steven, 1987. A Formalization of Set Theory without Variables. AMS Colloquium Publications, vol. 41.

External links

• Internet Encyclopedia of Philosophy: "Henri Poincare"--by Mauro Murzi. Includes a discussion of Poincaré's critique of the Peano's axioms.
• Lucas's comments
• First-order arithmetic, a chapter of a book on the incompleteness theorems by Karl Podnieks.
• "Peano arithmetic". PlanetMath.
• Weisstein, Eric W. "Peano's Axioms". MathWorld.
• What are numbers, and what is their meaning?: Dedekind commentary on Dedekind's work, Stanley N. Burris, 2001.

---

PA at PlanetMath.