In
mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of forma ...
, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are
axioms for the
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called '' cardinal ...
s presented by the 19th century
Italian mathematician
A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems.
Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change.
History
On ...
Giuseppe Peano. These axioms have been used nearly unchanged in a number of
metamathematical investigations, including research into fundamental questions of whether
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Ma ...
is
consistent and
complete
Complete may refer to:
Logic
* Completeness (logic)
* Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable
Mathematics
* The completeness of the real numbers, which implies t ...
.
The need to formalize
arithmetic
Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers— addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th ...
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
Charles Sanders Peirce ( ; September 10, 1839 – April 19, 1914) was an American philosopher, logician, mathematician and scientist who is sometimes known as "the father of pragmatism".
Educated as a chemist and employed as a scientist for ...
provided an
axiomatization
In mathematics and logic, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems. A theory is a consistent, relatively-self-contained body of knowledge which usually contai ...
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'' ( la, Arithmetices principia, nova methodo exposita).
The nine 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
In mathematics and other formal sciences, first-order or first order most often means either:
* "linear" (a polynomial of degree at most one), as in first-order approximation and other calculus uses, where it is contrasted with "polynomials of hig ...
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 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.
Historical second-order formulation
When Peano formulated his axioms, the language of
mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of forma ...
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
''Begriffsschrift'' (German for, roughly, "concept-script") is a book on logic by Gottlob Frege, published in 1879, and the formal system set out in that book.
''Begriffsschrift'' is usually translated as ''concept writing'' or ''concept nota ...
'' by
Gottlob Frege
Friedrich Ludwig Gottlob Frege (; ; 8 November 1848 – 26 July 1925) was a German philosopher, logician, and mathematician. He was a mathematics professor at the University of Jena, and is understood by many to be the father of analytic p ...
, published in 1879. Peano was unaware of Frege's work and independently recreated his logical apparatus based on the work of
Boole
George Boole (; 2 November 1815 – 8 December 1864) was a largely self-taught English mathematician, philosopher, and logician, most of whose short career was spent as the first professor of mathematics at Queen's College, Cork in Irel ...
and
Schröder.
The Peano axioms define the arithmetical properties of ''
natural numbers'', usually represented as a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
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 often 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
In mathematics and other formal sciences, first-order or first order most often means either:
* "linear" (a polynomial of degree at most one), as in first-order approximation and other calculus uses, where it is contrasted with "polynomials of hig ...
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 we use the second-order induction axiom, it is possible to define
addition,
multiplication
Multiplication (often denoted by the Multiplication sign, cross symbol , by the mid-line #Notation and terminology, dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four Elementary arithmetic, elementary Op ...
, 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
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
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:
:
The
structure
A structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such a ...
is a
commutative monoid
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
Monoid ...
with identity element 0. is also a
cancellative
In mathematics, the notion of cancellative is a generalization of the notion of invertible.
An element ''a'' in a magma has the left cancellation property (or is left-cancellative) if for all ''b'' and ''c'' in ''M'', always implies that .
A ...
magma
Magma () is the molten or semi-molten natural material from which all igneous rocks are formed. Magma is found beneath the surface of the Earth, and evidence of magmatism has also been discovered on other terrestrial planets and some natura ...
, and thus
embeddable in a
group. The smallest group embedding N is the
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s.
Multiplication
Similarly,
multiplication
Multiplication (often denoted by the Multiplication sign, cross symbol , by the mid-line #Notation and terminology, dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four Elementary arithmetic, elementary Op ...
is a function mapping two natural numbers to another one. Given addition, it is defined recursively as:
:
It is easy to see that
(or "1", in the familiar language of
decimal representation) 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
:
.
Therefore, by the induction axiom
is the multiplicative left identity of all natural numbers. Moreover, it can be shown that multiplication is commutative and
distributes over addition:
:
.
Thus,
is a commutative
semiring.
Inequalities
The usual
total order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive ...
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
Predicate or predication may refer to:
* Predicate (grammar), in linguistics
* Predication (philosophy)
* several closely related uses in mathematics and formal logic:
**Predicate (mathematical logic)
**Propositional function
**Finitary relation, o ...
''φ'', 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
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
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'' (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
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...
. In particular, given two models and of the Peano axioms, there is a unique
homomorphism
In algebra, a homomorphism is a morphism, structure-preserving map (mathematics), map between two algebraic structures of the same type (such as two group (mathematics), groups, two ring (mathematics), rings, or two vector spaces). The word ''homo ...
satisfying
:
and it is a
bijection
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
. 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 number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called '' cardinal ...
s and axioms of set theory such as
ZF. The standard construction of the naturals, due to
John von Neumann
John von Neumann (; hu, Neumann János Lajos, ; December 28, 1903 – February 8, 1957) was a Hungarian-American mathematician, physicist, computer scientist, engineer and polymath. He was regarded as having perhaps the widest c ...
, 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
Closed may refer to:
Mathematics
* Closure (mathematics), a set, along with operations, for which applying those operations on members always results in a member of the set
* Closed set, a set which contains all its limit points
* Closed interval, ...
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
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, ca ...
. Let ''C'' be a
category with
terminal object 1
''C'', and define the category of
pointed unary systems, US
1(''C'') as follows:
* The objects of US
1(''C'') are triples where ''X'' is an object of ''C'', and and are ''C''-morphisms.
* A morphism ''φ'' : (''X'', 0
''X'', ''S''
''X'') → (''Y'', 0
''Y'', ''S''
''Y'') is a ''C''-morphism with and .
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 is this initial object, and is any other object, then the unique map is such that
:
This is precisely the recursive definition of 0
''X'' and ''S''
''X''.
Consistency
When the Peano axioms were first proposed,
Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British mathematician, philosopher, logician, and public intellectual. He had a considerable influence on mathematics, logic, set theory, linguistics, a ...
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
The second (symbol: s) is the unit of time in the International System of Units (SI), historically defined as of a day – this factor derived from the division of the day first into 24 hours, then to 60 minutes and finally to 60 seconds ea ...
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 mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a founda ...
. In 1936,
Gerhard Gentzen gave
a proof of the consistency of Peano's axioms, using
transfinite induction
Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Its correctness is a theorem of ZFC.
Induction by cases
Let P(\alpha) be a property defined for ...
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
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer alg ...
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
Self-verifying theories are consistent first-order systems of arithmetic, much weaker than Peano arithmetic, that are capable of proving their own consistency. Dan Willard was the first to investigate their properties, and he has described a fami ...
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
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").
Peano arithmetic as first-order theory
All of the Peano axioms except 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 axiom of induction above is
second-order, since it
quantifies over predicates (equivalently, sets of natural numbers rather than natural numbers). As an alternative one can consider 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. 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
A signature (; from la, signare, "to sign") is a Handwriting, handwritten (and often Stylization, stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and ...
of Peano arithmetic, and axioms are included that relate the three operations to each other.
The following list of axioms (along with the usual axioms of equality), which contains six of the seven axioms of
Robinson arithmetic
In mathematics, Robinson arithmetic is a finitely axiomatized fragment of first-order Peano arithmetic (PA), first set out by R. M. Robinson in 1950. It is usually denoted Q. Q is almost PA without the axiom schema of mathematical induction. Q i ...
, is sufficient for this purpose:
*
*
*
*
*
*
In addition to this list of numerical axioms, Peano arithmetic contains the induction schema, which consists of a
recursively enumerable and even decidable set of
axioms. For each formula in the language of Peano arithmetic, the first-order induction axiom for ''φ'' is the sentence
:
where
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 ''φ''.
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. One such axiomatization begins with the following axioms that describe a discrete ordered semiring.
#
, i.e., addition is
associative.
#
, i.e., addition is
commutative.
#
, i.e., multiplication is associative.
#
, i.e., multiplication is commutative.
#
, i.e., multiplication
distributes over addition.
#
, i.e., zero is an
identity
Identity may refer to:
* Identity document
* Identity (philosophy)
* Identity (social science)
* Identity (mathematics)
Arts and entertainment Film and television
* ''Identity'' (1987 film), an Iranian film
* ''Identity'' (2003 film), an ...
for addition, and an
absorbing element for multiplication (actually superfluous).
#
, i.e., one is an
identity
Identity may refer to:
* Identity document
* Identity (philosophy)
* Identity (social science)
* Identity (mathematics)
Arts and entertainment Film and television
* ''Identity'' (1987 film), an Iranian film
* ''Identity'' (2003 film), an ...
for multiplication.
#
, i.e., the '<' operator is
transitive.
#
, i.e., the '<' operator is
irreflexive
In mathematics, a binary relation ''R'' on a set ''X'' is reflexive if it relates every element of ''X'' to itself.
An example of a reflexive relation is the relation " is equal to" on the set of real numbers, since every real number is equal ...
.
#
, i.e., the ordering satisfies
trichotomy.
#
, i.e. the ordering is preserved under addition of the same element.
#
, i.e. the ordering is preserved under multiplication by the same positive element.
#
, i.e. given any two distinct elements, the larger is the smaller plus another element.
#
, i.e. zero and one are distinct and there is no element between them. In other words, 0 is
covered
Cover or covers may refer to:
Packaging
* Another name for a lid
* Cover (philately), generic term for envelope or package
* Album cover, the front of the packaging
* Book cover or magazine cover
** Book design
** Back cover copy, part of copy ...
by 1, which suggests that natural numbers are discrete.
#
, i.e. zero is the minimum element.
The theory defined by these axioms is known as PA
−; the theory PA is obtained by adding the first-order induction schema. An important property of PA
− is that any structure
satisfying this theory has an initial segment (ordered by
) isomorphic to
. Elements in that segment are called standard elements, while other elements are called nonstandard elements.
Undecidability and incompleteness
According to
Gödel's incompleteness theorems
Gödel's incompleteness theorems are two theorems of mathematical logic that are concerned with the limits of in formal axiomatic theories. These results, published by Kurt Gödel in 1931, are important both in mathematical logic and in the phil ...
, the theory of PA (if consistent) is incomplete. Consequently, there are sentences of
first-order logic (FOL) that are true in the standard model of PA but are not a consequence of the FOL axiomatization. Essential incompleteness already arises for theories with weaker axioms, such as
Robinson arithmetic
In mathematics, Robinson arithmetic is a finitely axiomatized fragment of first-order Peano arithmetic (PA), first set out by R. M. Robinson in 1950. It is usually denoted Q. Q is almost PA without the axiom schema of mathematical induction. Q i ...
.
Closely related to the above incompleteness result (via
Gödel's completeness theorem for FOL) it follows that there is no
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
for deciding whether a given FOL sentence is a consequence of a first-order axiomatization of Peano arithmetic or not. Hence, PA is an example of an
undecidable theory. Undecidability arises already for the existential sentences of PA, due to the negative answer to
Hilbert's tenth problem
Hilbert's tenth problem is the tenth on the list of mathematical problems that the German mathematician David Hilbert posed in 1900. It is the challenge to provide a general algorithm which, for any given Diophantine equation (a polynomial equ ...
, whose proof implies that all
computably enumerable sets are
diophantine sets, and thus definable by existentially quantified formulas (with free variables) of PA. Formulas of PA with higher
quantifier rank (more quantifier alternations) than existential formulas are more expressive, and define sets in the higher levels of the
arithmetical hierarchy.
Nonstandard models
Although the usual
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called '' cardinal ...
s 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. 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
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
, 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
Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is clos ...
. 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
In mathematics, especially in set theory, two ordered sets and are said to have the same order type if they are order isomorphic, that is, if there exists a bijection (each element pairs with exactly one in the other set) f\colon X \to Y suc ...
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.
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.
See also
*
Foundations of mathematics
*
Frege's theorem
*
Goodstein's theorem
*
Neo-logicism
*
Non-standard model of arithmetic
*
Paris–Harrington theorem
In mathematical logic, the Paris–Harrington theorem states that a certain combinatorial principle in Ramsey theory, namely the strengthened finite Ramsey theorem, is true, but not provable in Peano arithmetic. This has been described by some (su ...
*
Presburger arithmetic
*
Robinson arithmetic
In mathematics, Robinson arithmetic is a finitely axiomatized fragment of first-order Peano arithmetic (PA), first set out by R. M. Robinson in 1950. It is usually denoted Q. Q is almost PA without the axiom schema of mathematical induction. Q i ...
*
Second-order arithmetic
*
Typographical Number Theory
Notes
References
Citations
Sources
*
*
** Two English translations:
***
***
*
*
*
*
*
*
*
* Derives the Peano axioms (called S) from several
axiomatic set theories and from
category theory
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, ca ...
.
*
*
*
*
*
*
*
*
*
*
* Derives the Peano axioms from
ZFC
*
*
** Contains translations of the following two papers, with valuable commentary:
***
***
*
*
Further reading
*
*
*
*
External links
* Includes a discussion of Poincaré's critique of the Peano's axioms.
*
*
*
* Commentary on Dedekind's work.
{{PlanetMath attribution, urlname=pa, title=PA
1889 introductions
Mathematical axioms
Formal theories of arithmetic
Logic in computer science
Mathematical logic
hu:Giuseppe Peano#A természetes számok Peano-axiómái