Peano axioms

In mathematics, the Peano axioms (or Peano postulates) are a set of first-order axioms proposed by Giuseppe Peano which determine the theory of Peano arithmetic (also known as first-order arithmetic). This theory constitutes a fundamental formalism for arithmetic, and the Peano axioms form a basis for the formalisation of stronger theories, such as second-order arithmetic.

Using the Peano axioms, one can construct many of the most important number systems and structures of modern mathematics. Peano arithmetic raises a number of metamathematical and philosophical issues, primarily involving questions of consistency and completeness.

Contents

1 The axioms 2 Existence and uniqueness 3 Binary operations and ordering 4 Categorical interpretation 5 Metamathematical discussion 6 External links and references

The axioms

Informally, the Peano axioms may be stated as follows:

• There is a natural number 0.
• Every natural number a has a successor, denoted by S(a).
• There is no natural number whose successor is 0.
• Distinct natural numbers have distinct successors: if a ≠ b, then S(a) ≠ S(b).
• If a property is possessed by 0 and also by the successor of every natural number which possesses it, then it is possessed by all natural numbers. (This axiom ensures that the proof technique of mathematical induction is valid.)

More formally, we define a Dedekind-Peano structure to be an ordered triple (X, x, f), satisfying the following properties:

• X is a set, x is an element of X, and f is a map from X to itself.
• x is not in the range of f.
• f is injective.
• If A is a subset of X satisfying:
  • x is in A, and
  • If a is in A, then f(a) is in A

then A = X.

The Peano axioms can be summed up by the following diagram:

<math>x\mapsto f(x)\mapsto f(f(x))\mapsto f(f(f(x)))\mapsto\dotsb<math>

where each of the iterates f(x), f( f(x) ), f( f( f(x) ) ), ... of x under f are distinct.

Existence and uniqueness

A standard construction in set theory shows the existence of a Dedekind-Peano structure. First, we define the successor function; for any set a, the successor of a is S(a) := a ∪ {a}. A set A is an inductive set if it is closed under the successor function, i.e. whenever a is in A, S(a) is also in A. We now define:

• 0 := {}
• N := the intersection of all inductive sets containing 0
• S := the successor function restricted to N

The set N is the set of natural numbers; it is sometimes denoted by the Greek letter ω, especially in the context of studying ordinal numbers.

The axiom of infinity guarantees the existence of an inductive set, so the set N is well-defined. The natural number system (N, 0, S) can be shown to satisfy the Peano axioms. Each natural number is then equal to the set of natural numbers less than it, so that

• 0 := {}
• 1 := S(0) = {0}
• 2 := S(1) = {0,1} = {0, {0}}
• 3 := S(2) = {0,1,2} = {0, {0}, {0, {0}}}

and so on. This construction is due to John von Neumann.

This is not the only possible construction of a Dedekind-Peano structure. For instance, if we assume the construction of the set N = {0, 1, 2,...} and successor function S above, we could also define X := {5, 6, 7,...}, x := 5, and f := successor function restricted to X. Then this is also a Dedekind-Peano structure.

<math>5\mapsto6\mapsto7\mapsto8\mapsto\dotsb<math>

The lambda calculus gives another construction of the natural numbers that satisfies the Peano axioms.

Two Dedekind-Peano structures (X, x, f) and (Y, y, g) are said to be isomorphic if there is a bijection φ : X → Y such that φ(x) = y and φf = gφ. It can be shown that any two Dedekind-Peano structures are isomorphic; in this sense, there is a "unique" Dedekind-Peano structure satisfying the Peano axioms. (See the categorical discussion below.)

Binary operations and ordering

Addition, multiplication and the usual ordering can all be defined for the natural numbers N entirely in terms of the Peano axioms.

One recursively defines an addition by setting a + 0 = a and a + S(b) = S(a + b) for all a, b. This turns the natural numbers (N, +) into a commutative monoid with identity element 0, the so-called free monoid with one generator. This monoid satisfies the cancellation property and can therefore be embedded in a group. The smallest group containing the natural numbers is the integers.

Since S(0) := 1, we have S(b) = S(b + 0) = b + S(0) = b + 1; i.e. the successor of b is simply b + 1.

Analogously, given that addition has been defined, a multiplication * can be defined via a * 0 = 0 and a * (b + 1) = (a * b) + a. This turns (N, *) into a commutative monoid with identity element 1; addition and multiplication are compatible which is expressed in the distribution law: a * (b + c) = (a * b) + (a * c).

For the remainder of the article, we write ab to indicate the product a * b.

Furthermore, one defines a total order on the natural numbers by writing a ≤ b if and only if there exists another natural number c with a + c = b. This order is compatible with the arithmetical operations in the following sense: if a, b and c are natural numbers and a ≤ b, then a + c ≤ b + c and ac ≤ bc. An important property of the set of natural numbers N is that it is well-ordered: every non-empty set of natural numbers has a least element. This property is also shared by every natural number n.

Categorical interpretation

The Peano axioms may be interpreted in the general context of category theory. Let US₁ be the category of pointed unary systems; i.e. US₁ is the following category:

• The objects of US₁ are all ordered triples (X, x, f), where X is a set, x is an element of X, and f is a set map from X to itself.
• For each (X, x, f), (Y, y, g) in US₁, Hom_US1((X, x, f), (Y, y, g)) = {set maps φ : X → Y | φ(x) = y and φf = gφ}
• Composition of morphisms is the usual composition of set mappings.

The natural number system (N, 0, S) constructed above is an object in this category; it is called the natural unary system. It can be shown that the natural unary system is an initial object in US₁, and so it is unique up to a unique isomorphism. This means that for any other object (X, x, f) in US₁, there is a unique morphism φ : (N, 0, S) → (X, x, f). This means that for any set X, any element x of X, and any set map f from X to itself, there is a unique set map φ : N → X such that φ(0) = x and φ(a + 1) = f(φ(a)) for all a in N. This is precisely the definition of simple recursion.

This concept can be generalised to arbitrary categories. Let C be a category with (unique) terminal object 1, and let US₁(C) be the category of pointed unary systems in C; i.e. US₁(C) is the following category:

• The objects of US₁(C) are all ordered triples (X, x, f), where X is an object of C, and x : 1 → X and f : X → X are morphisms in C.
• For each (X, x, f), (Y, y, g) in US₁(C), Hom_US1(C)((X, x, f), (Y, y, g)) = {φ : φ is in Hom_C(X, Y), φx = y, and φf = gφ}
• Composition of morphisms is the composition of morphisms in C.

Then C is said to satisfy the Dedekind-Peano axiom if there exists an initial object in US₁(C). This initial object is called a natural number object in C. The simple recursion theorem is simply an expression of the fact that the natural number system (N, 0, S) is a natural number object in the category Set.

Metamathematical discussion

These axioms are given here in a second-order predicate calculus form. See first-order predicate calculus for a way to rephrase these axioms to be first-order.

Dedekind proved, in his 1888 book Was sind und was sollen die Zahlen (http://www.thoralf.uwaterloo.ca/htdocs/scav/dedek/dedek.html), that any model of the second order Peano axioms is isomorphic to the natural numbers. On the other hand, the last axiom listed above, the mathematical induction axiom, is not itself expressible in the first order language of arithmetic.

If one replaces the last axiom with the schema:

If <math>P(0)<math> is true; and for all <math>x<math>, <math>P(x)<math> implies <math>P(x + 1)<math>; then <math>P(x)<math> is true for all <math>x<math>.

for each first order property <math>P(x)<math> (an infinite number of axioms) then although natural numbers satisfy these axioms, there are other, nonstandard models of arbitrarily large cardinality - by the compactness theorem the existence of infinite natural numbers cannot be excluded in any axiomatization; by an "upward Löwenheim-Skolem theorem", there exist models of all cardinalities.

When the axioms were first proposed, people such as Bertrand Russell agreed 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 a proof can exist that starts from just these axioms, and derives a contradiction such as P AND (NOT P), then the axioms are inconsistent, and don't really define anything. David Hilbert posed a problem of proving consistency using only finite logic as one of the problems on his famous list. The motivation was to eliminate infinity, by justifying it with this proof, and show that it brings nothing new.

But in 1931, Kurt Gödel in his celebrated second incompleteness theorem showed such a proof cannot exist. It is even impossible to prove consistency of Peano arithmetic while assuming the axioms themselves. Furthermore, we can never prove that any axiom system is consistent within the system itself, if it is at least as strong as Peano's axioms. In 1936, Gerhard Gentzen proved the consistency of Peano's axioms, using transfinite induction.

All mathematicians assume that Peano arithmetic is consistent, although this relies on intuition only. However, early forms of naïve set theory also intuitively looked consistent, before the inconsistencies were discovered. This has been a source of confusion for a number of people, especially nonmathematicians.

The point is that we do have to rely on our intuition, and that it brings something new. Roger Penrose has argued that this intuition is what differentiates men from machines, but his arguments are dubious. The modern set theory often considers axioms postulating existence of large cardinals - none of them can be proved within set theory, nor is it possible to prove consistency of these axioms. But mathematicians generally do not exclude the possibility that some of these axiom systems are inconsistent. The intuition here is much less clear than in the case of natural numbers. Some people argue that even Peano arithmetic could be inconsistent - since intuition is not really a reliable source of truth. This argument can be extended and make us doubt even finite logic itself - these questions go back to Kant and his famous Critique of Pure Reason.

Founding a mathematical system upon axioms, such as the above Peano axioms for natural numbers or axiomatic set theory or Euclidean geometry is sometimes labeled the axiomatic method or axiomatics. In axiomatic set theory, if one chooses to accept the axiom of choice, axiomatics allows such results as the Banach-Tarski paradox. This states that a ball can be dissected into five parts and re-assembled by Euclidean transformations into two balls of size equal to the original. A simpler approach to a mathematical system is found in Generating arithmetic.

External links and references

• Gentzen's proof (http://dns.uncor.edu/info/raggio/03obra/logfm/logica/gentz50.htm)
• Poincare's comments (http://www.utm.edu/research/iep/p/poincare.htm)
• Lucas's comments (http://www.leaderu.com/truth/2truth08.html)
• First-order arithmetic (http://www.ltn.lv/~podnieks/gt3.html), a chapter of a book on the incompleteness theorems by Karl Podnieks.

es:Axiomas de Peanofr:Axiomes de Peano it:Assiomi di Peano ja:ペアノの公理zh:皮亚诺公理 ko:페아노의 공리