Peano axioms

From Free net encyclopedia

In mathematics, the Peano axioms (or Peano postulates) are a set of second-order axioms proposed by Giuseppe Peano which determine the theory of arithmetic. The axioms are usually encountered in a first-order form, where the crucial second-order induction axiom is replaced by an infinite first-order induction schema, and Peano Arithmetic (PA) is by convention the name of the widely used system of first-order arithmetic given using this first-order form. However, Peano arithmetic is essentially weaker than the second order axiom system, since there are nonstandard models of Peano arithmetic, and the only model for the Peano axioms (considered as second-order statements) is the usual system of natural numbers (up to isomorphism).

Peano first gave his axioms in a Latin text Arithmetices principia, nova methodo exposita published in 1889 (Peano 1889), where Peano gave nine axioms, four axioms specifying the behaviour of the equality relation and five rules involving the specifically arithmetic terms for zero and successor. It is the latter five rules that are usually intended when one discusses the Peano axioms. Peano took logical principles to be given.

Peano arithmetic constitutes a fundamental formalism for arithmetic, and the Peano axioms can be used to 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.

1 The axioms
2 Binary operations and ordering
3 Peano arithmetic
4 Existence and uniqueness
5 Categorical interpretation
6 Metamathematical discussion
7 See also
8 References
9 External links

[edit]

The axioms

Informally, the Peano axioms may be stated as follows:

0 is a natural number.
Every natural number a has a successor, denoted by Sa or <math>a'</math>.
No natural number has 0 as its successor.
Distinct natural numbers have distinct successors: a = b if and only if Sa = Sb.
If a property holds for 0, and holds for the successor of every natural number for which it holds, then the property holds for all natural numbers. This axiom of induction legitimizes the proof method known as mathematical induction (induction over the naturals).

Letting the first natural number be 1 merely requires replacing 0 with 1 in the above axioms, to no substantive effect. However, starting with 1 does change the recursive definitions of addition and multiplication given below.

More formally and following Dedekind (1888), define a Dedekind-Peano structure as 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 following diagram sums up the Peano axioms:

<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.

[edit]

Binary operations and ordering

The above axioms can be augmented by definitions of addition and multiplication over the natural numbers N, and by the usual ordering of N.

To define addition '+' recursively in terms of successor and 0, let a+0 = a and a+Sb = S(a+b) for all a, b. This turns ⟨N,+⟩ into a commutative monoid with identity element 0, the so-called free monoid with one generator. This monoid satisfies the cancellation property and is therefore embeddable in a group. The smallest group containing the natural numbers is the integers.

Given this definition of addition and S0 := 1, we can define successor in term of addition as follows: Sb = S(b+0) = b+S0 = b+1; i.e. the successor of b is simply b+1.

Given successor, addition, and 0, define multiplication '*' by the recursive axioms a*0 = 0 and a*Sb = (a*b) + a. Hence ⟨N,*⟩ is also a commutative monoid with identity element 1. Moreover, addition and multiplication are compatible by virtue of the distribution law:

a*(b+c) = (a*b) + (a*c).

Henceforth, ab shall denote the product a*b.

Define the usual total order on N, ≤, as follows. For any two natural numbers a and b, a ≤ b if and only if there exists a natural number c such that a+c = b. This order is compatible with addition and multiplication 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 N is that it also constitutes a well-ordered set; every nonempty subset of N has a least element. This property is also shared by every member of N.

[edit]

Peano arithmetic

Peano Arithmetic (PA) reformulates the Peano axioms as a first order theory with two binary operations, addition and multiplication, recursively defined as in the preceding section, and denoted by infix '+' and juxtaposition, respectively. The conceptual change is that the Axiom schema of Induction is replaced by a schema permitting induction only over arithmetical formulae φ, whose symbols are just 0, S, '+', juxtaposition, and quantified variables ranging over the natural numbers. The new Axiom schema of Induction represents a countably infinite set of axioms.

The axioms of PA are:

<math>\exists! z \forall x[Sx \neq z]</math>. This z is called 0 by convention.
<math>\forall x,y[(Sx = Sy) \rightarrow x=y]</math>
<math>(\varphi(0) \wedge \forall x[\varphi(x)\rightarrow\varphi(Sx)]) \rightarrow \forall x[\varphi(x)]</math>, for any formula <math>\phi</math> in the language of PA.
<math> \forall x[x+0=x]</math>
<math>\forall x,y[x+Sy = S(x+y)]</math>
<math>\forall x[0x=0]</math>
<math>\forall x,y[xSy = xy + x]</math>.

PA does not require the predicate "is a natural number" because the universe of discourse of PA is just the natural numbers N. While only one explicit existential quantifier appears in the above axioms, three tacit quantifiers of that nature follow from the closure of the natural numbers under successor, addition, and multiplication.

[edit]

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.)

[edit]

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). That is, 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_US₁(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.

[edit]

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, 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 P(0) is true; and for all x, P(x) implies P(x + 1); then P(x) is true for all x.

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.

But in 1931, Kurt Gödel in his celebrated second incompleteness theorem showed such a proof cannot be given in any subsystem of Peano arithmetic. 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. Although it is widely believed that Gödel's theorem rules out the possibility of a finitistic consistency proof for Peano arithmetic, this is not clear, and 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. In 1936, Gerhard Gentzen gave a proof of the consistency of Peano's axioms, using transfinite induction up to an ordinal called ε₀. As Gentzen has explained it himself: "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 this really counts as the "finitistic proof" that Hilbert wanted is unclear: the main problem with deciding this question is that there is no generally accepted definition of exactly what is meant by a finitistic proof, and Hilbert himself never gave a precise definition.

Most mathematicians assume that Peano arithmetic is consistent, although this relies on either intuition or on accepting Gentzen's proof. However, early forms of naïve set theory also intuitively looked consistent, before the inconsistencies were discovered.

Founding a mathematical system upon axioms, such as the Peano axioms for natural numbers or axiomatic set theory or Euclidean geometry is sometimes labeled the axiomatic method or axiomatics.

[edit]

References

R. Dedekind, 1888. Was sind und was sollen die Zahlen? (What are and what should the numbers be?). Braunschweig.
G. Peano, 1889. Arithmetices principia, nova methodo exposita (The principles of arithmetic, presented by a new method). Bocca, Torino. Translation appears pp. 83-97 (van Heijenoort 1967).
J. van Heijenoort, 1967. From Frege to Gödel: A sourcebook in mathematical logic. Harvard University Press.

[edit]