Peano Axioms The Axioms Existence And Uniqueness Binary

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.

1 The axioms

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

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

2 Existence and uniqueness

A standard construction in set theory shows the existence of a Peano system. 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:

The set N is the set of natural numbers; it is sometimes denoted by the greek letter ω, especially in the context of studying ordinal numberSet theory Ordinal numbers or ordinals for short, are numbers used to denote the position in an ordered sequence: first, second, third, fourth, etc. See How to name numbers''. In mathematics, ordinal numbers are an extension of the natural numbers to accos.

The axiom of infinitySet theory In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of infinity is one of the axioms of Zermelo-Fraenkel set theory. In the formal language of the Zermelo-Fraenkel axioms, the axiom reads: 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

and so on. This construction is due to John von NeumannA separate article covers Saint John Neumann, the American priest. John von Neumann (Neumann Janos) ( December 28, 1903 February 8, 1957) was a Hungarian- American mathematician who made important contributions in quantum physics, set theory, computer sci.

This is not the only possible construction of a Peano system. 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 Peano system.

The lambda calculusThe lambda calculus is a formal system designed to investigate function definition, function application, and recursion. It was introduced by Alonzo Church and Stephen Cole Kleene in the 1930s; Church used the lambda calculus in 1936 to give a negative an gives another construction of the natural numbers that satisfies the Peano axioms.

Two Peano systems (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 Peano systems are isomorphic; in this sense, there is a "unique" system satisfying the Peano axioms. (See the categorical discussion below.)

3 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 additionAddition of natural numbers is the most basic arithmetic operation. Here we will define it from Peano's axioms (see natural number) and prove some simple properties. The set of natural numbers will be denoted by N zero is taken to be a natural number. 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 monoidIn abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element. In other words, it is a unital semigroup. Definition A monoid is a magma (M, ), i. a set M with binary op with identity elementIn mathematics, an identity element (or neutral element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them. The term identity element is often shortened to ident 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.

4 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_US₁((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_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.

5 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 is true; and for all , implies ; then is true for all .

for each first order property (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 naive 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.

6 External links and references

Gentzen's proof
Poincare's comments
Lucas's comments
First-order arithmetic, a chapter of a book on the incompleteness theorems by Karl Podnieks.

<Hide>

Home > Peano axioms