User:Kaustuv/ip/Peano axioms

From Wikipedia, the free encyclopedia

You have new messages (last change).
 This page is a user's work in progress page, not an article, and may be incomplete and/or unreliable. The current version of this article is located at Peano axioms.

In mathematics, the Peano axioms (or Peano postulates) are a set of nine second-order axioms for the theory of natural numbers. Four of the nine axioms define equality, four more define the natural numbers in a unary representation, and the last axiom defines the principle of mathematical induction on the natural numbers. The first eight axioms are first-order statements that can be used for arithmetic reasoning; this fragment is thus known as Peano Arithmetic (PA). The Peano axioms have been used in several technical results in mathematical logic, such as Gödel's completeness theorem, but they are also useful in metamathematical and philosophical reasoning.

The axioms were proposed by the Italian mathematician Giuseppe Peano (1858–1932) in his text The principles of arithmetic presented by a new method (Latin: Arithmetices principia, nova methodo exposita), published in 1889. He prefaced his axiomatization with a brief treatment of the logical apparatus to be employed, but he did not discuss fundamental logical principles.

Contents

[edit] Peano's axioms

Peano created a logical notation to use in presenting his axioms. Although this notation is not in contemporary use, it is very similar to modern notation. Peano uses the symbol ε for set membership and a reversed C for logical implication (which became ⊃).

The axioms are based on the successor operation, written Sa or S(a), which adds 1 to its argument. Thus S(1) = 2, S(S(1)) = S(2) = 3, and in general S(a) = a + 1. The axioms do not use the addition symbol; they outline certain properties of the successor operation which are sufficent to recreate addition in terms of the successor function.

Peano's nine axioms, rephrased in contemporary notation, are:

  1. 1 is a natural number.
  2. Every natural number is equal to itself (equality is reflexive).
  3. For all natural numbers a and b, a=b if and only if b=a (equality is symmetric).
  4. For all natural numbers a, b, and c, if a=b and b=c then a=c (equality is transitive).
  5. If a = b and b is a natural number then a is a natural number.
  6. If a is a natural number then Sa is a natural number.
  7. If a and b are natural numbers then a=b if and only if Sa =Sb.
  8. If a is a natural number then Sa is not equal to 1.
  9. For every set K, if 1 is in K and for every natural number x in K, Sx is also in K, then every natural number is in K. (It makes no difference here whether all elements of K are natural numbers.)

Axioms 2, 3, 4, and 5 are now considered basic properties of equality and taken for granted in most contexts. Thus it is axioms 1, 6, 7, 8, and 9 which describe the structure of the natural numbers.

Axioms 6, 7, and 8 determine the properties of the successor operation. Axiom 6 states that every natural number has a successor, axiom 7 states that the successor operation is an injection from the natural numbers to themselves, and axiom 8 states that 1 is not the successor of any natural number. These axioms imply that the set of natural numbers is infinite, because no two elements of the chain

1\mapsto S(1)\mapsto S(S(1))\mapsto S(S(S(1)))\mapsto\dotsb

can be the same. Axioms 1 through 8 are not enough to prove that this chain contains all of the natural numbers, however.

Axiom 9 is the induction axiom; it implies that any set of natural numbers containing 1 and closed under the successor operation contains every natural number. It thus implies that the chain above contains all the natural numbers, because the chain contains 1 and whenever a natural number x is in the chain then so is Sx. Because this axiom has a quantifier over all sets, it is a second-order statement. This single induction axiom can be recast as a weaker first-order axiom schema, yielding the first-order theory of Peano arithmetic discussed below.

[edit] Existence and uniqueness

Any infinite set X with an injection f from X to X can be used to define a model of Peano's axioms. This model will consist of a set N of elements, which stand for the natural numbers; a particular one of these elements that stands for 1; and a function from N to N that stands for S. To create this model from the infinite set X, first choose any element of X to stand for 1. Then define the symbol S to stand for the function f. Finally, let the set N of "natural numbers" be the intersection of all subsets of X that contain 1 and are closed under f. This set N will satisfy all of Peano's axioms.

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; in modern terminology, the second-order theory of the Peano axioms is called categorical. The proof uses the induction axiom in a crucial way. Suppose that two models of the Peano axioms, (NA, 1A, SA) and (NB, 1B, SB), are given. Define a function f from NA to NB as follows. First define f(1A) = 1B. Then, by recursion, define f(SAx) to be SBf(x). The set of x in NA for which f is defined includes 1A and is closed under SA, so by the induction axiom f is defined for all elements of NA. Also, the range of f includes 1B and is closed under SB, so the range is all of NB by the induction axiom. It can be shown that f is a bijection and, by definition, f(1A) = 1B and f(SAx) = SBf(x). Thus f is an isomorphism from NA to NB.

[edit] Historical placement of Peano's axioms

During the period when he published his axioms for arithmetic, Peano was both influenced by and influencing the work of other mathematicians. In particular, he acknowledges that he makes great use of Grassmann (1861) and Dedekind (1888).

Peano's paper employs a logical symbolism and mainains 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 by in 1879. Peano was unaware of Frege's work, however, and so independently recreated the logical apparatus he needed based on his knowledge of work by Boole and Schröder (Van Heijenoort 1967, p. 83).

[edit] Modern variations on the Peano axioms

Although Peano's axioms, as stated above, are adequate for many purposes, there are several variations on the Peano axioms common in contemporary texts.

One common variation is to begin the natural numbers with 0 rather than 1. This causes only cosmetic changes to the theory, and is convenient if the arithmetical operations of addition and multiplication will be defined. Both the convention of starting with 1 and the convention of starting with 0 are common in contemporary presentations of Peano's axioms. Presentations of Peano arithmetic, which includes the addition and multiplication operations, typically begin with 0.

A second common variation is to replace the axioms above with the axioms of a discrete ordered ring, in a language including addition and multiplication operations, and then add an axiom of induction to these to obtain a theory equivalent to the one presented above. This is discussed in more detail in the section on Peano arithmetic.

[edit] Binary operations and ordering

Peano's axioms can be augmented by definitions of addition and multiplication over the natural numbers N, and by the usual ordering of N. It is convenient to start with 0 instead of 1.

To define the addition operation + recursively in terms of successor and 0, let a + 0 = a and a + Sb = S(a + b) for all a and b. Then (N, +) can be shown to be a commutative semigroup with identity element 0; it is called the 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.

Let 1 stand for S0. It follows from the definition above that for any natural number b,

b + 1 = b + S0 = S(b + 0) = Sb.

This shows that b + 1 is simply the successor Sb of b.

Given successor, addition, and 0, the multiplication operation · is recursively defined by the axioms a \cdot 0 = 0 and a \cdot Sb = (a \cdot 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 \cdot (b+c) = (a \cdot b) + (a \cdot c).

Thus (N, +, ·, 0, 1) is a commutative semiring.

It is possible to define the usual total order ≤ on N as follows. For any two natural numbers a and b, put 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 a·c ≤ b·c. Thus the set N together with the arithmetic operations and the order ≤ is an ordered semiring. Because there is no natural number between 0 and 1, it is a discrete ordered semiring.

A fundamental order property of N is that it is a well-ordered set; every nonempty subset of N has a least element. This follows from the induction axiom. If X is a set of natural numbers with no least element then 0 cannot be in X, and if no y ≤ x is in X then Sx cannot be in X (because then Sx would be the least element of X). Thus, by induction, no natural number is in X if there is no least natural number in X.

[edit] Peano arithmetic

Peano Arithmetic (PA) is a reformulation of the second-order the Peano axioms as a first-order theory. The motivation for this reformulation is that first-order theories are more amenable to analysis in model theory and proof theory. The source of difficulty with Peano's axioms is the second-order induction axiom.

There are many different, but equivalent, formulations of the axioms for Peano arithmetic. One common formulation, described here, begins by defining a first-order theory PA− whose models are the discrete ordered semirings. Then an induction schema is added to PA− to obtain PA. The predicate "is a natural number" is not required in PA (and PA−) because the universe of discourse of PA is just the natural numbers N.

Different authors may give different but equivalent lists of axioms for Peano arithmetic. The axioms of PA− given by (Kaye 1991) are:

  1. \forall x \forall y \forall z\, ((x+y)+z = x+(y+z) )
  2. \forall x \forall y\, (x+y=y+x)
  3. \forall x \forall y \forall z\, ((x\cdot y ) \cdot z = x \cdot (y \cdot z))
  4. \forall x \forall y\, (x\cdot y = y \cdot x)
  5. \forall x \forall y \forall z\, (x \cdot (y + z) = x \cdot y + x \cdot z)
  6. \forall x \, ((x + 0 = x) \land (x \cdot 0 = 0))
  7. \forall x \, (x \cdot 1 = x)
  8. \forall x \forall y \forall z\, ((x < y \land y < z) \Rightarrow x < z)
  9. \forall x \, \lnot (x < x)
  10. \forall x \forall y\, ( x < y \lor x = y \lor x > y)
  11. \forall x \forall y \forall z\, (x < y \Rightarrow x + z < y + z)
  12. \forall x \forall y \forall z\, (0 < z \land x < y \Rightarrow x \cdot z < y \cdot z)
  13. \forall x \forall y\, ( x < y \Rightarrow \exists z ( x + z = y))
  14. 0 < 1 \land \forall x\, ( x > 0 \Rightarrow x \geq 1)
  15. \forall x \, ( x \geq 0)

While no explicit existential quantifiers appear in the most of the above axioms, implicit quantifiers of that nature follow from the closure of the natural numbers under zero, successor, addition, and multiplication.

An important property of PA− is that any structure M satisfying this theory has an initial segment isomorphic to the natural numbers. Elements of the structure that are not in this initial segment are called nonstandard elements.

To convert PA− to PA, the first-order induction schema is added. This schema represents a countably infinite set of axioms. For each formula φ(x,y1,...,yk) in the language of Peano arithmetic, the first-order induction axiom for φ is the sentence

\forall \bar{y} (\phi(0,\bar{y}) \land \forall x ( \phi(x,\bar{y})\Rightarrow\phi(x+1,\bar{y})) \Rightarrow \forall x \phi(x,\bar{y}))

where \bar{y} is an abbreviation for y1,...,yk. The first-order induction schema represents every instance of the first-order induction axiom, that is, it includes the induction axiom for every formula φ.

The motivation for the induction schema is that it is not possible to quantify over all sets of natural numbers using first-order logic. Thus it is not possible to express the statement that any set of natural numbers containing 0 and closed under successor is the entire set of natural numbers. What can be expressed in first-order logic is that any definable set of natural numbers has this property. But it is not possible to quantify over definable subsets explicitly with a single axiom; instead, one induction axiom is added for each formula φ that might be used to define a set of natural numbers. In this way, all definable sets are covered by the schema.

Although the 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. Moreover, when Dedekind's proof that the second-order Peano axioms have a unique model is viewed as a proof in a first-order axiomatization of set theory such as Zermelo–Fraenkel set theory, the proof only shows that each model of set theory has a unique model of the Peano axioms, up to isomorphism; nonstandard models of set theory may contain nonstandard models of the second-order Peano axioms.

Thus nonstandard models of PA are an unavoidable consequence of the first-order axiomatization. This is not the case with the second-order Peano axioms, which have only one model up to isomorphism. For this reason, the first-order axioms of PA are weaker than the second-order Peano axioms.

While nonstandard models of PA− can be explicitly constructed, it is known that there is no countable nonstandard model of PA in which either the addition or multiplication operation is computable.

Church numerals are a model of the Peano axioms derived using the lambda calculus.

[edit] Construction of the natural numbers in set theory

Main article: Set-theoretic definition of natural numbers

A standard construction due to John von Neumann is used to create a canonical model of Peano's axioms, starting with 0, in set theory. In the context of set theory, the successor function S is defined for every set a with the rule S(a) = a ∪ {a}. A set A is defined to be an inductive set if it is closed under this successor function, which means that whenever an element a is in A then Sa is also in A.

The canonical model of Peano's axioms is defined in set theory by interpreting 0 as the empty set, letting S be the successor function just defined, and defining N to be the intersection of all inductive sets containing the empty set. The axiom of infinity guarantees the existence of an inductive set containing the empty set, and thus the set N is well-defined.

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

In this construction of the natural numbers, each natural number is equal (as a set) 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. The structure of the successor function is thus

0\mapsto1\mapsto2\mapsto3\mapsto\dotsb

or, equivalently,

\{\}\mapsto\{\{\}\}\mapsto\{\{\},\{\{\}\}\}\mapsto\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\} \mapsto\dotsb

This is not the only possible construction of a model of Peano's axioms. For instance, if we assume the construction of the set N = {0, 1, 2,...} and successor function S above, we could also define N = {5, 6, 7,...}, let the symbol 0 be interpreted as the set 5, and use f to interpret the successor function restricted to X. This gives another model of Peano's axioms:

5\mapsto6\mapsto7\mapsto8\mapsto\dotsb

Texts that derive Peano arithmetic from the axioms for ZF set theory include Suppes (1960) and Hatcher (1982).

On systems of axiomatic set theory equivalent to Peano arithmetic, see Tarski and Givant (1987: 7.6). The simplest such system consists of general set theory (extensionality, existence of null set, and the axiom of adjunction), augmented by the following axiom schema. Let φx be a monadic predicate expressible in the language of first order set theory. Let φx be satisfied by the null set, and by the sets x, y, and the adjunction of x and y. Then the axiom schema asserts that φx is satisfied by all sets in the universe of discourse.

[edit] Categorical interpretation

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

  • The objects of US1 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 US1, HomUS1((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 US1, and so it is unique up to a unique isomorphism. This means that for any other object (X, x, f) in US1, 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 generalized to arbitrary categories. Let C be a category with (unique) terminal object 1, and let US1(C) be the category of pointed unary systems in C; i.e. US1(C) is the following category:

  • The objects of US1(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 US1(C), HomUS1(C)((X, x, f), (Y, y, g)) = {φ : φ is in HomC(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 US1(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] Consistency of Peano's axioms

Main article: Hilbert's second problem

When the Peano's 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 ε0. 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). 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.

[edit] See also

[edit] 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, Cambridge, Mass: Harvard University Press. ISBN 0-674-32449-8 (pbk.).  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.

[edit] External links

This article incorporates material from PA on PlanetMath, which is licensed under the GFDL.

Retrieved from "http://en.wikipedia.org../../../k/a/u/User%7EKaustuv_ip_Peano_axioms_6a31.html"