PEANO AXIOMS

(Redirected from Peano arithmetic)
In mathematics, the 'Peano axioms' (or 'Peano postulates') are a set of second-order axioms proposed by Giuseppe Peano which determine the theory of the natural numbers. These 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; this first order theory is called 'Peano arithmetic' ('PA'). The theory of Peano arithmetic is much weaker than that of the second-order Peano axioms.
Peano first presented his axioms in a Latin text ''Arithmetices principia, nova methodo exposita'' ("The principles of arithmetic, presented by a new method"), published in 1889 (Peano 1889). Peano gave nine axioms, of which four axioms specify the behavior of the equality relation and the other five specify the arithmetic terms for one and successor. It is the latter five rules that are usually intended when one discusses the Peano axioms. Peano preceded his axioms for arithmetic with a brief treatment of the logical apparatus to be employed, but he did not fundamentally discuss the underlying logical principles.
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.

Contents

Peano's axioms

Existence and uniqueness

Historical placement

Modern variations

Binary operations and ordering

Peano Arithmetic

Construction of the natural numbers in set theory

Categorical interpretation

Consistency

See also

References

External links

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 S''a'' 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 sufficient to recreate addition in terms of the successor function.
Peano's nine axioms, rephrased in contemporary notation, are:
# 1 is a natural number.
# Every natural number is equal to itself (equality is reflexive).
# For all natural numbers ''a'' and ''b'', ''a'' = ''b'' if and only if ''b'' = ''a'' (equality is symmetric).
# For all natural numbers ''a'', ''b'', and ''c'', if ''a'' = ''b'' and ''b'' = ''c'' then ''a'' = ''c'' (equality is transitive).
# If ''a'' = ''b'' and ''b'' is a natural number then ''a'' is a natural number.
# If ''a'' is a natural number then S''a'' is a natural number.
# If ''a'' and ''b'' are natural numbers then ''a'' = ''b'' if and only if S''a'' = S''b''.
# If ''a'' is a natural number then S''a'' is not equal to 1.
# For every set ''K'', if ''1'' is in ''K'', and S''x'' is in ''K'' for every natural number ''x'' 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
:$1mapsto\; S(1)mapsto\; S(S(1))mapsto\; S(S(S(1)))mapstodotsb$
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 S''x''. Because this axiom has a quantifier over all sets, it is a second-order statement.

Existence and uniqueness

Any infinite set ''X'' with a non-surjective 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'' that is not in the range of ''f'' 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, (''N''_A, 1_A, S_A) and (''N''_B, 1_B, S_B), are given. Define a function ''f'' from ''N''_A to ''N''_B as follows. First define ''f''(1_A) = 1_B. Then, by recursion, define ''f''(S_A''x'') to be S_Bf(''x''). The set of ''x'' in ''N''_A for which ''f'' is defined includes 1_A and is closed under S_A, so by the induction axiom ''f'' is defined for all elements of ''N''_A. Also, the range of ''f'' includes 1_B and is closed under S_B, so the range is all of ''N''_B by the induction axiom. It can be shown that ''f'' is a bijection and, by definition, ''f''(1_A) = 1_B and ''f''(S_A''x'') = S_B''f''(''x''). Thus ''f'' is an isomorphism from ''N''_A to ''N''_B.

Historical placement

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 maintains a clear distinction between mathematical and logical symbols, which was not yet common in mathematics. Such a separation had first been introduced in the Begriffsschrift by Gotlob Frege, published 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).

Modern variations

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.

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'. These definitions require set theory or second-order logic in order to construct the desired function, after which the axioms of Peano arithmetic prove that it is unique. 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 S''b'' 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 S''x'' cannot be in ''X'' (because then S''x'' 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''.

Peano Arithmetic

Peano Arithmetic (PA) is a reformulation of the second-order 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. In order to avoid problems with defining the addition and multiplication operations from the successor operation within the theory, discussed above, it is common to add these functions and their defining axioms directly to the basic first-order axiomatization.
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:
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
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'',''y''₁,...,''y''_''k'') in the language of Peano arithmetic, the 'first-order induction axiom' for φ is the sentence
:
where is an abbreviation for ''y''₁,...,''y''_''k''. 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 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 (Kaye 1991 sec. 11.3). This shows that it is difficult to be completely explicit in describing the addition and multiplication operations on a countable nonstandard model of PA.
Church numerals are a model of the Peano axioms derived using the lambda calculus.

Construction of the natural numbers in set theory

Main articles: 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 S''a'' 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
:$0mapsto1mapsto2mapsto3mapstodotsb$
or, equivalently,
:$\{\}mapsto\{\{\}\}mapsto\{\{\},\{\{\}\}\}mapsto\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}$
mapstodotsb
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:
:$5mapsto6mapsto7mapsto8mapstodotsb$
Texts that derive Peano arithmetic from the axioms for ZF set theory include Suppes (1960) and Hatcher (1982).
Peano arithmetic can be seen to be equiconsistent with several weak systems of set theory (see Tarski and Givant 1987 sec. 7.6). 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

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

Consistency

Main articles: 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 ε₀. 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

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

★ From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931, Jean van Heijenoort, ed., , , Harvard University Press, 1967, 1976 3rd printing with corrections, 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.

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.

★

★

★ What are numbers, and what is their meaning?: Dedekind commentary on Dedekind's work, Stanley N. Burris, 2001.
----