In mathematical logic, the Peano axioms (;"Peano". Random House Webster's Unabridged Dictionary. ), 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. 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 axiomatization of arithmetic provided by Peano axioms is commonly called Peano arithmetic.
The importance of formalizing 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 The principles of arithmetic presented by a new method ().
Peano’s axioms can be divided into groups according to their subject matter. 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, which makes this formulation close to second-order arithmetic. A weaker first-order system is obtained by explicitly adding the addition and multiplication operation symbols and replacing the second-order induction axiom with a first-order axiom schema. The term Peano arithmetic is sometimes used for specifically naming this restricted system.
Historical second-order 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 ε). 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. 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 The non-logical symbols for the axioms consist of a constant symbol 0 and a unary function symbol S.
The first axiom states that the constant 0 is a natural number:
Peano's original formulation of the axioms used 1 instead of 0 as the "first" natural number, while the axioms in Formulario mathematico include zero.
The next four axioms describe the equality relation. Since they are logically valid in first-order logic with equality, they are not considered to be part of "the Peano axioms" in modern treatments.
The remaining axioms define the arithmetical properties of the natural numbers. The naturals are assumed to be closed under a single-valued "successor" function S.
Axioms 1, 6, 7, 8 define a unary representation of the intuitive notion of natural numbers: the number 1 can be defined as S(0), 2 as S(S(0)), etc. However, considering the notion of natural numbers as being defined by these axioms, axioms 1, 6, 7, 8 do not imply that the successor function generates all the natural numbers different from 0.
The intuitive notion that each natural number can be obtained by applying successor sufficiently many times to zero requires an additional axiom, which is sometimes called the axiom of induction.
The induction axiom is sometimes stated in the following form:
In Peano's original formulation, the induction axiom is a second-order axiom. It is now common to replace this second-order principle with a weaker first-order induction scheme. There are important differences between the second-order and first-order formulations, as discussed in the section below.
Defining arithmetic operations and relations
If the second-order induction axiom is used, it is possible to define addition, multiplication, and total (linear) ordering on N directly using the axioms. However, and addition and multiplication are often added as axioms. 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.
Addition
Addition is a function that maps two natural numbers (two elements of N) to another one. It is defined recursively as:
For example:
To prove commutativity of addition, first prove and , each by induction on . Using both results, then prove by induction on . The structure is a commutative monoid with identity element 0. is also a cancellative magma, and thus embeddable in a group. The smallest group embedding N is the integers.
Multiplication
Similarly, multiplication is a function mapping two natural numbers to another one. Given addition, it is defined recursively as:
It is easy to see that is the multiplicative right identity:
To show that is also the multiplicative left identity requires the induction axiom due to the way multiplication is defined:
is the left identity of 0: . If is the left identity of (that is ), then is also the left identity of : , using commutativity of addition.
Therefore, by the induction axiom is the multiplicative left identity of all natural numbers. Moreover, it can be shownFor formal proofs, see e.g. :File:Inductive proofs of properties of add, mult from recursive definitions.pdf. that multiplication is commutative and distributes over addition:
.
Thus, is a commutative semiring.
Inequalities
The usual total order relation ≤ on natural numbers can be defined as follows, assuming 0 is a natural number:
For all , if and only if there exists some such that .
This relation is stable under addition and multiplication: for , if , then:
a + c ≤ b + c, and a · c ≤ b · c.
Thus, the structure is an ordered semiring; because there is no natural number between 0 and 1, it is a discrete ordered semiring.
The axiom of induction is sometimes stated in the following form that uses a stronger hypothesis, making use of the order relation "≤":
For any predicate φ, if φ(0) is true, and for every , if φ(k) is true for every such that , then φ(S(n)) is true, then for every , φ(n) is true.
This form of the induction axiom, called strong induction, is a consequence of the standard formulation, but is often better suited for reasoning about the ≤ order. For example, to show that the naturals are well-ordered—every nonempty subset of N has a least element—one can reason as follows. Let a nonempty be given and assume X has no least element.
Because 0 is the least element of N, it must be that . For any , suppose for every , . Then , for otherwise it would be the least element of X.
Thus, by the strong induction principle, for every , . Thus, , which contradicts X being a nonempty subset of N. Thus X has a least element.
Models
A model of the Peano axioms is a triple , where N is a (necessarily infinite) set, and satisfies the axioms above. Dedekind proved in his 1888 book, The Nature and Meaning of Numbers (, 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. In particular, given two models and of the Peano axioms, there is a unique homomorphism satisfying
and it is a bijection. This means that the second-order Peano axioms are categorical. (This is not the case with any first-order reformulation of the Peano axioms, below.)
Set-theoretic models
The Peano axioms can be derived from set theoretic constructions of the natural numbers and axioms of set theory such as ZF., The standard construction of the naturals, due to John von Neumann, starts from a definition of 0 as the empty set, ∅, and an operator s on sets defined as:
The set of natural numbers N is defined as the intersection of all sets closed under s that contain the empty set. Each natural number is equal (as a set) to the set of natural numbers less than it:
and so on. The set N together with 0 and the successor function satisfies the Peano axioms.
Peano arithmetic is equiconsistent with several weak systems of set theory. 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 the empty 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.
Interpretation in category theory
The Peano axioms can also be understood using category theory. Let C be a category with terminal object 1C, and define the category of pointed unary systems, US1(C) as follows:
The objects of US1(C) are triples where X is an object of C, and and are C-morphisms. A morphism φ : (X, 0X, SX) → (Y, 0Y, SY) is a C-morphism with and .
Then C is said to satisfy the Dedekind–Peano axioms if US1(C) has an initial object; this initial object is known as a natural number object in C. If is this initial object, and is any other object, then the unique map is such that
This is precisely the recursive definition of 0X and SX.
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".An illustration of 'interpretation' is Russell's own definition of 'cardinal number'. The uninterpreted system in this case is Peano's axioms for the number system, whose three primitive ideas and five axioms, Peano believed, were sufficient to enable one to derive all the properties of the system of natural numbers. Actually, Russell maintains, Peano's axioms define any progression of the form of which the series of the natural numbers is one instance. 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 do not define anything.So Poincaré turned to see whether logicism could generate arithmetic, more precisely, the arithmetic of ordinals. Couturat, said Poincaré, had accepted the Peano axioms as a definition of a number. But this will not do. The axioms cannot be shown to be free of contradiction by finding examples of them, and any attempt to show that they were contradiction-free by examining the totality of their implications would require the very principle of mathematical induction Couturat believed they implied. For (in a further passage dropped from S&M) either one assumed the principle in order to prove it, which would only prove that if it is true it is not self-contradictory, which says nothing; or one used the principle in another form than the one stated, in which case one must show that the number of steps in one's reasoning was an integer according to the new definition, but this could not be done (1905c, 834). 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, if Peano arithmetic is consistent.