Peano axioms (nonfiction)

In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano.

Introduction

These axioms have been used nearly unchanged in a number of metamathematical investigations, including research into fundamental questions of whether number theory is consistent and complete.

The need to formalize arithmetic was not well appreciated until the work of Hermann Grassmann, who showed in the 1860s that many facts in arithmetic could be derived from more basic facts about the successor operation and induction. In 1881, Charles Sanders Peirce provided an axiomatization of natural-number arithmetic. In 1888, Richard Dedekind proposed another axiomatization of natural-number arithmetic, and in 1889, Peano published a simplified version of them as a collection of axioms in his book Arithmetices principia, nova methodo exposita ("The principles of arithmetic presented by a new method").

The Peano axioms contain three types of statements. The first axiom asserts the existence of at least one member of the set of natural numbers. The next four are general statements about equality; in modern treatments these are often not taken as part of the Peano axioms, but rather as axioms of the "underlying logic". The next three axioms are first-order statements about natural numbers expressing the fundamental properties of the successor operation. The ninth, final axiom is a second order statement of the principle of mathematical induction over the natural numbers. A weaker first-order system called Peano arithmetic is obtained by explicitly adding the addition and multiplication operation symbols and replacing the second-order induction axiom with a first-order axiom schema.

Formulation

When Peano formulated his axioms, the language of mathematical logic was in its infancy. The system of logical notation he created to present the axioms did not prove to be popular, although it was the genesis of the modern notation for set membership (∈, which comes from Peano's ε) and implication (⊃, which comes from Peano's reversed 'C'.) Peano maintained 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 Gottlob Frege, published in 1879.[4] Peano was unaware of Frege's work and independently recreated his logical apparatus based on the work of Boole and Schröder.

The Peano axioms define the arithmetical properties of natural numbers, usually represented as a set N or {\displaystyle \mathbb {N} .}\mathbb {N} . The non-logical symbols for the axioms consist of a constant symbol 0 and a unary function symbol S.

TO_DO ...

Arithmetic

The Peano axioms can be augmented with the operations of addition and multiplication and the usual total (linear) ordering on N. The respective functions and relations are constructed in set theory or second-order logic, and can be shown to be unique using the Peano axioms.

TO_DO ...

First-order theory of arithmetic

All of the Peano axioms except the ninth axiom (the induction axiom) are statements in first-order logic.[7] The arithmetical operations of addition and multiplication and the order relation can also be defined using first-order axioms. The axiom of induction is in second-order, since it quantifies over predicates (equivalently, sets of natural numbers rather than natural numbers), but it can be transformed into a first-order axiom schema of induction. Such a schema includes one axiom per predicate definable in the first-order language of Peano arithmetic, making it weaker than the second-order axiom.[8] The reason that it is weaker is that the number of predicates in first-order language is countable, whereas the number of sets of natural numbers is uncountable. Thus, there exist sets that cannot be described in first-order language (in fact, most sets have this property).

First-order axiomatizations of Peano arithmetic have another technical limitation. In second-order logic, it is possible to define the addition and multiplication operations from the successor operation, but this cannot be done in the more restrictive setting of first-order logic. Therefore, the addition and multiplication operations are directly included in the signature of Peano arithmetic, and axioms are included that relate the three operations to each other.

TO_DO ...

Equivalent axiomatizations There are many different, but equivalent, axiomatizations of Peano arithmetic. While some axiomatizations, such as the one just described, use a signature that only has symbols for 0 and the successor, addition, and multiplications operations, other axiomatizations use the language of ordered semirings, including an additional order relation symbol.

TO_DO ...

Models

A model of the Peano axioms is a triple (N, 0, S), where N is a (necessarily infinite) set, 0 ∈ N and S: N → N satisfies the axioms above. Dedekind proved in his 1888 book, The Nature and Meaning of Numbers (German: Was sind und was sollen die Zahlen?, i.e., “What are the numbers and what are they good for?”) that any two models of the Peano axioms (including the second-order induction axiom) are isomorphic.

TO_DO ...

Set-theoretic models

Main article: Set-theoretic definition of natural numbers The Peano axioms can be derived from set theoretic constructions of the natural numbers and axioms of set theory such as ZF.

TO_DO ...

Interpretation in category theory

The Peano axioms can also be understood using category theory.

TO_DO ...

Nonstandard models

Although the usual natural numbers satisfy the axioms of PA, there are other models as well (called "non-standard models"); the compactness theorem implies that the existence of nonstandard elements cannot be excluded in first-order logic.[13] The upward Löwenheim–Skolem theorem shows that there are nonstandard models of PA of all infinite cardinalities. This is not the case for the original (second-order) Peano axioms, which have only one model, up to isomorphism.[14] This illustrates one way the first-order system PA is weaker than the second-order Peano axioms.

When interpreted as a proof within a first-order set theory, such as ZFC, Dedekind's categoricity proof for PA shows that each model of set theory has a unique model of the Peano axioms, up to isomorphism, that embeds as an initial segment of all other models of PA contained within that model of set theory. In the standard model of set theory, this smallest model of PA is the standard model of PA; however, in a nonstandard model of set theory, it may be a nonstandard model of PA. This situation cannot be avoided with any first-order formalization of set theory.

It is natural to ask whether a countable nonstandard model can be explicitly constructed. The answer is affirmative as Skolem in 1933 provided an explicit construction of such a nonstandard model. On the other hand, Tennenbaum's theorem, proved in 1959, shows that there is no countable nonstandard model of PA in which either the addition or multiplication operation is computable.[15] This result shows it is difficult to be completely explicit in describing the addition and multiplication operations of a countable nonstandard model of PA. There is only one possible order type of a countable nonstandard model. Letting ω be the order type of the natural numbers, ζ be the order type of the integers, and η be the order type of the rationals, the order type of any countable nonstandard model of PA is ω + ζ·η, which can be visualized as a copy of the natural numbers followed by a dense linear ordering of copies of the integers.

TO_DO ...

Overspill

A cut in a nonstandard model M is a nonempty subset C of M so that C is downward closed (x < y and y ∈ C ⇒ x ∈ C) and C is closed under successor. A proper cut is a cut that is a proper subset of M. Each nonstandard model has many proper cuts, including one that corresponds to the standard natural numbers. However, the induction scheme in Peano arithmetic prevents any proper cut from being definable. The overspill lemma, first proved by Abraham Robinson, formalizes this fact.

TO_DO ...

Consistency Further information: Hilbert's second problem and Consistency When the Peano axioms were first proposed, Bertrand Russell and others agreed that these axioms implicitly defined what we mean by a "natural number".[17] 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.[18] In 1900, David Hilbert posed the problem of proving their consistency using only finitistic methods as the second of his twenty-three problems.[19] In 1931, Kurt Gödel proved his second incompleteness theorem, which shows that such a consistency proof cannot be formalized within Peano arithmetic itself.[20]

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.[21] In 1936, Gerhard Gentzen gave a proof of the consistency of Peano's axioms, using transfinite induction up to an ordinal called ε0.[22] 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, or more abstractly as consisting of the finite trees, suitably linearly ordered). 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. A small number of philosophers and mathematicians, some of whom also advocate ultrafinitism, reject Peano's axioms because accepting the axioms amounts to accepting the infinite collection of natural numbers. In particular, addition (including the successor function) and multiplication are assumed to be total. Curiously, there are self-verifying theories that are similar to PA but have subtraction and division instead of addition and multiplication, which are axiomatized in such a way to avoid proving sentences that correspond to the totality of addition and multiplication, but which are still able to prove all true {\displaystyle \Pi _{1}}\Pi _{1} theorems of PA, and yet can be extended to a consistent theory that proves its own consistency (stated as the non-existence of a Hilbert-style proof of "0=1").

TO_DO ...

See also

• Foundations of mathematics (nonfiction)
• Frege's theorem (nonfiction)
• Goodstein's theorem (nonfiction)
• Neo-logicism (nonfiction)
• Non-standard model of arithmetic (nonfiction)
• Paris–Harrington theorem (nonfiction)
• Presburger arithmetic (nonfiction)
• Robinson arithmetic (nonfiction)
• Second-order arithmetic (nonfiction)
• Typographical Number Theory (nonfiction)

Fiction cross-reference

• Algorithmic Paradigm Treaty Organization - APTO
• Axiom Antics - rogue stand-up mathematical comedy and alleged front for organized transcorporate crime.
• Crimes against mathematical constants
• Gnomon algorithm
• Gnomon Chronicles
• Mathematics

Nonfiction cross-reference

• Completeness - converse of Soundness (nonfiction)
• Mathematical logic (nonfiction)
• Mathematics (nonfiction)
• The principles of arithmetic presented by a new method (nonfiction)

External links

• Peano axioms @ Wikipedia