In
mathematical logic, the
Peano axioms, also known as the
Dedekind–Peano axioms or the
Peano
postulates, are a set of
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
consistency and
completeness of
number
theory.
The need for formalism in 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 1888,
Richard Dedekind proposed a collection of
axioms about the numbers, and in 1889 Peano published a more
precisely formulated version of them as a collection of axioms in
his book,
The principles of arithmetic presented by a new
method ( ).
The Peano axioms contain three types of statements. The first four
statements are general statements about
equality; in modern treatments these
are often considered axioms of pure logic. The next four 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 replacing this
second-order induction axiom with a first-order axiom schema.
The axioms
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 (symbol: ∈, from Peano's ε) and
implication (symbol: ⊃, 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. 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 properties of
natural numbers,
usually represented as a
set
N or \mathbb{N}. The
signature for the axioms
includes a constant symbol 0 and a unary function symbol
S.
The first four axioms describe the
equality relation.
- For every natural number x, x = x.
That is, equality is reflexive.
- For all natural numbers x and y, if
x = y, then y = x. That is,
equality is symmetric.
- For all natural numbers x, y and z,
if x = y and y = z, then
x = z. That is, equality is transitive.
- For all a and b, if a is a natural
number and a = b, then b is also a
natural number. That is, the natural numbers are closed under equality.
The remaining axioms define the properties of the natural numbers.
The constant 0 is assumed to be a natural number, and the naturals
are assumed to be closed under a "successor"
function S.
- 0 is a natural number.
- For every natural number n, S(n) is
a natural number.
Peano's original formulation of the axioms used 1 instead of 0 as
the "first" natural number. This choice is arbitrary, as axiom 5
does not endow the constant 0 with any additional properties.
However, because 0 is the
additive
identity in
arithmetic, most modern
formulations of the Peano axioms start from 0. Axioms 5 and 6
define a
unary representation
of the natural numbers: the number 1 is
S(0), 2 is
S(
S(0)) (=
S(1)), and, in general, any
natural number
n is
S^{n}(0).
The next two axioms define the properties of this
representation.
- For every natural number n,
S(n) ≠ 0.
- That is, there is no natural number whose successor
is 0.
- For all natural numbers m and n, if
S(m) = S(n), then m =
n.
- That is, S is an injection.
These two axioms together imply that the set of natural numbers is
infinite, because it contains at least the infinite subset { 0,
S(0),
S(
S(0)), … }, each element of
which differs from the rest. The final axiom, sometimes called the
axiom of induction, is a method of reasoning about all
natural numbers.
- If K is a set such that:
- 0 is in K, and
- for every natural number n, if n is in
K, then S(n) is in K,
then K contains every natural number.
The induction axiom is sometimes stated in the following
second order form:
- If φ is a unary predicate such that:
- * φ(0) is true, and
- * for every natural number n, if φ(n) is
true, then φ(S(n)) is true,
- then φ(n) is true for every natural number
n.
The two formulations are NOT equivalent; cf. the section on
nonstandard models below.
Without the axiom of induction, this axiom set would be equivalent
to
Robinson arithmetic, which
can be expressed without second-order logic.
Arithmetic
The Peano axioms can be augmented with the operations of
addition and
multiplication and the usual
total ordering on
N. The respective
functions and relations are constructed in
second-order logic, and are shown to be
unique using the Peano axioms.
Addition is the function + :
N ×
N →
N (written in the usual
infix notation), defined
recursively as:
- \begin{align}
a + 0 &= a ,\\a + S (b) &= S (a + b).\end{align}For
example,
- a + 1 = a + S(0) =
S(a + 0) = S(a).
The structure (
N, +) is a
commutative semigroup
with identity element 0. (
N, +) is also a
cancellative magma, and thus
embeddable in a
group. The smallest group embedding
N is the
integers.
Given addition,
multiplication is the
function · :
N ×
N →
N defined
recursively as:
- \begin{align}
a \cdot 0 &= 0, \\a \cdot S (b) &= a + (a \cdot
b).\end{align}It is easy to see that 1 is the multiplicative
identity:
- a · 1 = a · S(0) = a +
(a · 0) = a + 0 = a
Moreover, multiplication
distributes
over addition:
- a · (b + c) = (a ·
b) + (a · c).
Thus, (
N, +, 0, ·, 1) is a commutative
semiring.
The usual
total order relation ≤ :
N ×
N can be defined as follows:
- for a, b \in N , a \le b if and only if there exists c \in N
such that a + c = b .
This relation is stable under addition and multiplication: for a,
b, c \in N , if
a ≤
b, then:
- a + c ≤ b + c, and
- a · c ≤ b · c.
Thus, the structure (
N, +, ·, 1, 0, ≤) 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
strong form, making use of the ≤ order:
- For any predicate φ,
if
- * φ(0) is true, and
- * for every n, k ∈ N, if k
≤ n implies φ(k) is true, then
φ(S(n)) is true,
- then for every n ∈ N, φ(n) is
true.
This form of the induction axiom is a simple 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
X ⊆
N be given and assume
X has
no least element.
- Because 0 is the least element of N, it must be that 0
∉ X.
- For any n ∈ N, suppose for every k ≤
n, k ∉ X. Then S(n) ∉
X, for otherwise it would be the least element of
X.
Thus, by the strong induction principle, for every
n ∈
N,
n ∉
X. Thus,
X ∩
N
= ∅, 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
(
N, 0,
S), where
N an infinite set, 0 ∈
N and
S :
N →
N satisfies the
axioms above.
Dedekind proved in
his 1888 book,
What are numbers and what should they be (
) that any two models of the Peano axioms are
isomorphic: given two models
(
N_{A}, 0
_{A},
S_{A}) and
(
N_{B}, 0
_{B},
S_{B}) of the Peano axioms, the
homomorphism f :
N_{A} →
N_{B}
defined as
- \begin{align}
f(0_A) &= 0_B \\f(S_A (n)) &= S_B (f (n))\end{align}is a
bijection. The Peano axioms are
thus
categorical; this
is not the case with any first-order reformulation of the Peano
axioms, however.
First-order theory of arithmetic
First-order theories are often
better than
second order theories
for
model or
proof theoretic analysis. All but the ninth
axiom (the induction axiom) are statements in
first-order logic. The arithmetical
operations of addition and multiplication and the order relation
can also be defined using first-order axioms. The second-order
axiom of induction can be transformed into a weaker
first-order induction schema; the first eight of Peano's
axioms together with the first-order induction schemaform a
first-order axiomatization of
arithmetic
called
Peano arithmetic
(
PA).
The induction schema consists of a
countably infinite set of
axioms. For each formula
φ(
x,
y_{1},...,
y_{k})
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
y_{1},...,
y_{k}. The
first-order induction schema includes every instance of the
first-order induction axiom, that is, it includes the induction
axiom for every formula φ.
This schema avoids quantification over sets of natural numbers,
which is impossible in first-order logic. For instance, it is not
possible in first-order logic to say that any set of natural
numbers containing 0 and closed under successor is the entire set
of natural numbers. What can be expressed is that any
definable set of natural
numbers has this property. Because it is not possible to quantify
over definable subsets explicitly with a single axiom, the
induction schema includes one instance of the induction axiom for
every definition of a subset of the naturals.
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 operation, other axiomatizations use the language of
ordered semiring, including addition
and multiplication function symbols and an order relation symbol.
One such axiomatization begins with the following axioms that
describe a discrete ordered semiring.
- \forall x, y, z \in N. (x + y) + z = x + (y + z), i.e.,
addition is associative.
- \forall x, y \in N. x + y = y + x, i.e., addition is commutative.
- \forall x, y, z \in N. (x \cdot y) \cdot z = x \cdot (y \cdot
z), i.e., multiplication is associative.
- \forall x, y \in N. x \cdot y = y \cdot x, i.e., multiplication
is commutative.
- \forall x, y, z \in N. x \cdot (y + z) = (x \cdot y) + (x \cdot
z), i.e., the distributive
law.
- \forall x \in N. x + 0 = x \and x \cdot 0 = 0, i.e., zero is
the identity element for addition
- \forall x \in N. x \cdot 1 = x, i.e., one is the identity
element for multiplication.
- \forall x, y, z \in N. x y \and y z \supset x z, i.e., the
'<' operator is transitive.
- \forall x \in N. \neg (x x), i.e., the '<' operator is not
reflexive.
- \forall x, y \in N. x y \or x = y \or x > y.
- \forall x, y, z \in N. x y \supset x + z y + z.
- \forall x, y, z \in N. 0 z \and x y \supset x \cdot z y \cdot
z.
- \forall x, y \in N. x y \supset \exists z \in N. x + z =
y.
- 0 1 \and \forall x \in N. x > 0 \supset x \geq 1.
- \forall x \in N. x \geq 0.
The theory defined by these axioms is known as
PA^{–}; PA is obtained by adding the
first-order induction schema. An important property of
PA
^{–} is that any structure
M satisfying this
theory has an initial segment (ordered by ≤) isomorphic to
N. Elements of
M \
N are known as
nonstandard elements.
Nonstandard models
Although the usual
natural numbers
satisfy the axioms of PA, there are other
non-standard 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. This is not the case for the original
(second-order) Peano axioms, which have only one model, up to
isomorphism. 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. It is possible to explicitly describe the
order type of any countable nonstandard model: it is always ω + (ω*
+ ω)η, which can be visualized as a copy of the natural numbers
followed by a dense linear ordering of copies of the integers.
However,
a theorem by Stanley
Tennenbaum, proved in 1959, shows that there is no countable
nonstandard model of PA in which either the addition or
multiplication operation is
computable. This result shows it is
difficult to be completely explicit in describing the addition and
multiplication operations of a countable nonstandard model of
PA.
Set-theoretic models
The Peano axioms can be derived from
set
theoretic constructions of the
natural numbers and axioms of set theory such
as the
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:
- s(a) = a ∪ { a }.
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:
- \begin{align}
0 &= \emptyset \\1 &= s(0) = \emptyset \cup \{ \emptyset \}
= \{ \emptyset \} = \{ 0 \} \\2 &= \{ 0, 1 \} \\3 &= \{ 0,
1, 2 \}\end{align}and so on. The set
N together
with 0 and the successor function
s :
N →
N 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
A model of the Peano axioms can also be constructed using
category theory. Let
C be a
category with
initial object 1
_{C}, and
define the category of
pointed unary systems,
US
_{1}(
C) as follows:
- The objects of US_{1}(C) are triples
(X, 0_{X},
S_{X}) where X is an object of
C, and 0_{X} : 1_{C} →
X and S_{X} : X →
X are C-morphisms.
- A morphism φ : (X, 0_{X},
S_{X}) → (Y,
0_{Y}, S_{Y}) is a
C-morphism φ : X → Y with φ
0_{X} = 0_{Y} and φ
S_{X} = S_{Y}
φ.
Then
C is said to satisfy the Dedekind–Peano axioms if
US
_{1}(
C) has an initial object; this initial
object is known as a
natural
number object in
C. If (
N, 0,
S) is
this initial object, and (
X, 0
_{X},
S_{X}) is any other object, then the
unique map
u : (
N, 0,
S) → (
X,
0
_{X},
S_{X}) is such
that
- \begin{align}
u 0 &= 0_X, \\u (S x) &= S_X (u x).\end{align}This is
precisely the recursive definition of 0
_{X} and
S_{X}.
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".
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.
See also
Footnotes
- Grassmann 1861
- Dedekind 1888
- Peano 1889
- Van Heijenoort 1967, p. 2
- Van Heijenoort 1967, p. 83
- In Peano's original presentation, the axiom labeled 5 here was
numbered 1, and the axioms numbered 1 through 4 here were numbered
2 through 5, respectively.
- Kaye 1991, pp. 16–18
- Because the system presented in this section is a definitional extension of the axiom
system presented above with the more restricted signature, both are
referred to simply as Peano arithmetic (PA) in the literature.
- Kaye 1991, sec. 11.3
- Suppes 1960; Hatcher 1982
- Tarski & Givant 1987, sec. 7.6
- Hilbert 1900
- Godel 1931
- Godel 1958
- Gentzen 1936
References
- Martin Davis, 1974.
Computability. Notes by Barry Jacobs. Courant Institute of Mathematical
Sciences, New York University.
- 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.
- Gentzen, G., 1936, Die
Widerspruchsfreiheit der reinen Zahlentheorie.
Mathematische Annalen 112: 132–213. Reprinted in English
translation in his 1969 Collected works, M. E. Szabo, ed.
Amsterdam: North-Holland.
- K. Gödel ,1931, Über formal unentscheidbare
Sätze der Principia Mathematica und verwandter Systeme, I.
Monatshefte für Mathematik und Physik 38: 173–98. See
On Formally Undecidable Propositions of Principia Mathematica and
Related Systems for details on English translations.
- --------, 1958, "Über eine bisher noch nicht benüzte
Erweiterung des finiten Standpunktes," Dialectica 12:
280–87. Reprinted in English translation in 1990. Gödel's
Collected Works, Vol II. Solomon Feferman et al., eds. Oxford
University Press.
- Hermann Grassmann, 1861.
Lehrbuch der Arithmetik (A tutorial in arithmetic).
Berlin.
- Hatcher, William S., 1982. The Logical Foundations of
Mathematics. Pergamon. Derives the Peano axioms (called
S) from several axiomatic set theories and from
category theory.
- David Hilbert,1901, "Mathematische
Probleme". Archiv der Mathematik und Physik 3(1): 44–63,
213–37. English translation by Maby Winton, 1902, " Mathematical Problems," Bulletin of the American
Mathematical Society 8: 437–79.
- Kaye, Richard, 1991. Models of Peano arithmetic.
Oxford University Press. ISBN 0-19-853213-X.
- Patrick Suppes, 1972 (1960).
Axiomatic Set Theory. Dover. ISBN 0486616304. Derives the
Peano axioms from ZFC.
- Alfred Tarski, and Givant, Steven,
1987. A Formalization of Set Theory without Variables. AMS
Colloquium Publications, vol. 41.
- Edmund Landau, 1965 Grundlagen
Der Analysis. AMS Chelsea Publishing. Derives the basic number
systems from the Peano axioms. English/German vocabulary included.
ISBN 978-0828401418
- Contains translations of the following two papers, with
valuable commentary:
- Richard Dedekind, 1890, "Letter
to Keferstein." pp. 98–103. On p. 100, he restates and defends his
axioms of 1888.
- Giuseppe Peano, 1889.
Arithmetices principia, nova methodo exposita (The
principles of arithmetic, presented by a new method), pp. 83–97. An
excerpt of the treatise where Peano first presented his axioms, and
recursively defined arithmetical operations.
External links