In
mathematical logicMathematical logic is a subfield of mathematics with close connections to computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, the
Peano axioms, also known as the
Dedekind–Peano axioms or the
Peano postulates, are a set of
axiomIn traditional logic, an axiom or postulate is a proposition that is not proved or demonstrated but considered to be either self-evident, or subject to necessary decision...
s for the
natural numberIn mathematics, there are two conventions for the set of natural numbers: it is either the set of positive integers {, , , ...} according to the traditional definition or the set of non-negative integers {, 1, 2, ...} according to...
s presented by the 19th century
ItalianThe Italian people are an ethnic group, in the sense of sharing a common Italian culture, descent, and speaking the Italian language as a mother tongue...
mathematicianA mathematician is a person whose primary area of study and/or research is the field of mathematics. Mathematicians are concerned with particular problems related to logic, space, transformations, numbers and more general ideas which encompass these concepts...
Giuseppe PeanoGiuseppe Peano was an Italian mathematician, whose work was of exceptional philosophical value. The author of over 200 books and papers, he was a founder of mathematical logic and set theory, to which he contributed much notation. The standard axiomatization of the natural numbers is named in his...
. These axioms have been used nearly unchanged in a number of
metamathematicalMetamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories...
investigations, including research into fundamental questions of
consistencyIn logic, a consistent theory is one that does not contain a contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent if it has a model; this is the sense used in traditional Aristotelian logic,...
and
completenessIn general, an object is complete if nothing needs to be added to it. This notion is made more specific in various fields.-Logical completeness:...
of
number theoryNumber theory is the branch of pure mathematics concerned with the properties of numbers in general, and integers in particular, as well as the wider classes of problems that arise from their study....
.
The need for formalism in arithmetic was not well appreciated until the work of
Hermann GrassmannHermann Günther Grassmann was a German polymath, renowned in his day as a linguist and now admired as a mathematician. He was also a physicist, neohumanist, general scholar, and publisher...
, who showed in the 1860s that many facts in arithmetic could be derived from more basic facts about the successor operation and
inductionMathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite...
. In 1888,
Richard DedekindJulius Wilhelm Richard Dedekind was a German mathematician who did important work in abstract algebra , algebraic number theory and the foundations of the real numbers.-Life:...
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
equalityEquality, or more formally the identity relation, is the binary relation on a set X defined by .The identity relation is the paradigmatic example of the more general concept of an equivalence relation on a set: those binary relations which are reflexive, symmetric, and transitive. The relation of...
; in modern treatments these are often considered axioms of pure logic. The next four axioms are
first-orderFirst-order logic is a formal logic used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, and predicate logic...
statements about natural numbers expressing the fundamental properties of the successor operation. The ninth, final axiom is a
second orderIn logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory....
statement of the principle of
mathematical inductionMathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite...
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 logicMathematical logic is a subfield of mathematics with close connections to computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
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
implicationIn logic and mathematics, logical implication is a logical relation that holds between a set T of formulae and a formula B when every model of T is also a model of B. In symbols,# ,# #...
(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
BegriffsschriftBegriffsschrift is the title of a book on logic by Gottlob Frege, published in 1879, and is also the name of the formal system set out in that book....
by
Gottlob FregeFriedrich Ludwig Gottlob Frege was a German mathematician who became a logician and philosopher. He was one of the founders of modern logic, and made major contributions to the foundations of mathematics. As a philosopher, he is generally considered to be the father of analytic philosophy, for his...
, published in 1879. Peano was unaware of Frege's work and independently recreated his logical apparatus based on the work of
BooleGeorge Boole was anEnglish mathematician and philosopher.As the inventor of Boolean logic, which is the basis of modern digital computer logic, Boole is regarded in hindsight as one of the founders of the field of computer science. Boole said,.....
and
SchröderErnst Schröder was a German mathematician mainly known for his work on algebraic logic. He is a major figure in the history of mathematical logic , by virtue of summarizing and extending the work of George Boole, Augustus De Morgan, Hugh MacColl, and especially Charles Peirce...
.
The Peano axioms define the properties of
natural numbers, usually represented as a set
N or The signature for the axioms includes a constant symbol 0 and a unary function symbol
S.
The first four axioms describe the
equalityEquality, or more formally the identity relation, is the binary relation on a set X defined by .The identity relation is the paradigmatic example of the more general concept of an equivalence relation on a set: those binary relations which are reflexive, symmetric, and transitive. The relation of...
relationIn mathematics , a relation is a property that assigns truth values to combinations of k individuals. Typically, the property describes a possible connection between the components of a k-tuple...
.
- For every natural number x, x = x. That is, equality is reflexive
In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation R on S where xRx holds true for every x in S.-Related terms:...
.
- For all natural numbers x and y, if x = y, then y = x. That is, equality is symmetric
In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a.In mathematical notation, this is:...
.
- For all natural numbers x, y and z, if x = y and y = z, then x = z. That is, equality is transitive
In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
.
- 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
In mathematics, a set is said to be closed under some operation if performance of that operation on members of the set always produces a member of the set...
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"
functionIn mathematics, a function is a relation between a given set of elements and another set of elements , which associates each element in the domain with exactly one element in the codomain...
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 identityIn mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...
in
arithmeticArithmetic or arithmetics is the oldest and most elementary branch of mathematics, used by almost everyone, for tasks ranging from simple day-to-day counting to advanced science and business calculations, such as addition, subtraction, multiplication and division...
, most modern formulations of the Peano axioms start from 0. Axioms 5 and 6 define a
unaryThe unary numeral system is the bijective base-1 numeral system. It is the simplest numeral system to represent natural numbers: in order to represent a number N, an arbitrarily chosen symbol representing 1 is repeated N times. For example, using the symbol | , the number 6 is represented as ||||||...
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
Sn(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
In mathematics, an injective function is a function that associates distinct arguments with distinct values; in other words, every unique argument produces a unique result...
.
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 orderIn logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory....
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 arithmeticIn mathematics, Robinson arithmetic, or Q, is a finitely axiomatized fragment of Peano arithmetic , first set out in Robinson . Q is essentially PA without the axiom schema of induction...
, which can be expressed without second-order logic.
Arithmetic
The Peano axioms can be augmented with the operations of
additionAddition is the mathematical process of combining quantities. It is signified by the plus sign . For example, in the picture on the right, there are 3 + 2 apples—meaning three apples and two other apples—which is the same as five apples. Therefore, 3 + 2 = 5...
and
multiplicationMultiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....
and the usual
total (linear) orderingIn mathematics and set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
on
N. The respective functions and relations are constructed in
second-order logicIn logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory....
, and are shown to be unique using the Peano axioms.
Addition is the function + :
N ×
N →
N (written in the usual
infix notationInfix notation is the common arithmetic and logical formula notation, in which operators are written infix-style between the operands they act on . It is not as simple to parse by computers as prefix notation or postfix notation Infix notation is the common arithmetic and logical formula notation,...
), defined
recursivelyRecursion, in mathematics and computer science, is a method of defining functions in which the function being defined is applied within its own definition. The term is also used more generally to describe a process of repeating objects in a self-similar way...
as:
For example,
- a + 1 = a + S(0) = S(a + 0) = S(a).
The structure (
N, +) is a commutative
semigroupIn mathematics, a semigroup is an algebraic structure consisting of a nonempty set S together with an associative binary operation. In other words, a semigroup is an associative magma. The terminology is derived from the anterior notion of a group...
with identity element 0. (
N, +) is also a
cancellativeIn mathematics, the notion of cancellative is a generalization of the notion of invertible.An element a in a magma has the left cancellation property if for all b and c in M, a * b = a * c always implies b = c.An element a in a magma has the right cancellation...
magmaIn abstract algebra, a magma is a basic kind of algebraic structure. Specifically, a magma consists of a set M equipped with a single binary operation M × M → M...
, and thus
embeddableIn mathematics, an embedding is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup....
in a
groupIn mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
. The smallest group embedding
N is the
integerThe integers are natural numbers including 0 and their negatives . They are numbers that can be written without a fractional or decimal component, and fall within the set {.....
s.
Given addition,
multiplicationMultiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....
is the function · :
N ×
N →
N defined recursively as:
It is easy to see that 1 is the multiplicative
identityIn mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...
:
- 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
semiringIn abstract algebra, a semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse...
.
The usual
total orderIn mathematics and set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
relation ≤ :
N ×
N can be defined as follows:
- for , if and only if there exists such that .
This relation is stable under addition and multiplication: for , if
a ≤
b, then:
- a + c ≤ b + c, and
- a · c ≤ b · c.
Thus, the structure (
N, +, ·, 1, 0, ≤) is an
ordered semiringIn abstract algebra, an ordered ring is a commutative ring with a total order ≤ such that for all a, b, and c in R:* if a ≤ b then a + c ≤ b + c.* if 0 ≤ a and 0 ≤ b then 0 ≤ ab....
; 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-orderIn mathematics, a well-order relation on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering.Equivalently, a well-ordering is a well-founded total order....
ed—every
nonemptyIn mathematics, and more specifically set theory, the empty set is the unique set having no members; its size is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
subsetIn mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. Notice that A and B may coincide...
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
contradictIn classical logic, a contradiction consists of a logical incompatibility between two or more propositions. It occurs when the propositions, taken together, yield two conclusions which form the logical inversions of each other...
s
X being a nonempty subset of
N.Thus
X has a least element.
Models
A
modelIn mathematics, model theory is the study of mathematical structures such as groups, fields, graphs, or even universes of set theory, using tools from mathematical logic. A structure that gives meaning to the sentences of a formal language is called a model for the language...
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.
DedekindJulius Wilhelm Richard Dedekind was a German mathematician who did important work in abstract algebra , algebraic number theory and the foundations of the real numbers.-Life:...
proved in his 1888 book,
What are numbers and what should they be that any two models of the Peano axioms are
isomorphicIn abstract algebra, an isomorphism is a bijective map f such that both f and its inverse f −1 are homomorphisms, i.e., structure-preserving mappings....
: given two models (
NA, 0
A,
SA) and (
NB, 0
B,
SB) of the Peano axioms, the
homomorphismIn abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures . The word homomorphism comes from the Greek language: ὁμός meaning "same" and μορφή meaning "shape".- Definition :The definition of homomorphism depends on the type of algebraic structure under...
f :
NA →
NB defined as
is a bijection. The Peano axioms are thus
categoricalIn model theory, a branch of mathematical logic, a theory is κ-categorical if it has exactly one model of cardinality κ up to isomorphism....
; this is not the case with any first-order reformulation of the Peano axioms, however.
First-order theory of arithmetic
First-orderFirst-order logic is a formal logic used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, and predicate logic...
theories are often better than
second orderIn logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory....
theories for
modelIn mathematics, model theory is the study of mathematical structures such as groups, fields, graphs, or even universes of set theory, using tools from mathematical logic. A structure that gives meaning to the sentences of a formal language is called a model for the language...
or
proof theoreticProof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as plain lists, boxed lists, or trees, which are constructed...
analysis. All but the ninth axiom (the induction axiom) are statements in
first-order logicFirst-order logic is a formal logic used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, and predicate 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 schemaIn mathematical logic, an axiom schema generalizes the notion of axiom.An axiom schema is a formula in the language of an axiomatic system, in which one or more schematic variables appear. These variables, which are metalinguistic constructs, stand for any term or subformula of the system, which...
; the first eight of Peano's axioms together with the first-order induction schema
form a first-order axiomatization of
arithmeticArithmetic or arithmetics is the oldest and most elementary branch of mathematics, used by almost everyone, for tasks ranging from simple day-to-day counting to advanced science and business calculations, such as addition, subtraction, multiplication and division...
called
Peano arithmetic (
PA).
The induction schema consists of a
countably infiniteIn mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable...
set of axioms. For each formula φ(
x,
y1,...,
yk) in the language of Peano arithmetic, the
first-order induction axiom for φ is the sentence
where is an abbreviation for
y1,...,
yk. 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
definableIn universal algebra and in model theory, a structure consists of a set along with a collection of finitary functions and relations which are defined on it....
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 semiringIn abstract algebra, an ordered ring is a commutative ring with a total order ≤ such that for all a, b, and c in R:* if a ≤ b then a + c ≤ b + c.* if 0 ≤ a and 0 ≤ b then 0 ≤ ab....
, 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.
- ∀x, y, z ∈ N. (x + y) + z = x + (y + z), i.e., addition is associative.
- ∀x, y ∈ N. x + y = y + x, i.e., addition is commutative.
- ∀x, y, z ∈ N. (x · y) · z = x · (y · z), i.e., multiplication is associative.
- ∀x, y ∈ N. x · y = y · x, i.e., multiplication is commutative.
- ∀x, y, z ∈ N. x · (y + z) = (x · y) + (x · z), i.e., the distributive law.
- ∀x ∈ N. x + 0 = x ∧ x · 0 = 0, i.e., zero is the identity element for addition
- ∀x ∈ N. x · 1 = x, i.e., one is the identity element for multiplication.
- ∀x, y, z ∈ N. x < y ∧ y < z ⊃ x < z, i.e., the '<' operator is transitive
In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
.
- ∀x ∈ N. ¬ (x < x), i.e., the '<' operator is not reflexive
In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation R on S where xRx holds true for every x in S.-Related terms:...
.
- ∀x, y ∈ N. x < y ∨ x = y ∨ x > y.
- ∀x, y, z ∈ N. x < y ⊃ x + z < y + z.
- ∀x, y, z ∈ N. 0 < z ∧ x < y ⊃ x · z < y · z.
- ∀x, y ∈ N. x < y ⊃ ∃z ∈ N. x + z = y.
- 0 < 1 ∧ ∀x ∈ N. x > 0 ⊃ x ≥ 1.
- ∀x ∈ N. x ≥ 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 numberIn mathematics, there are two conventions for the set of natural numbers: it is either the set of positive integers {, , , ...} according to the traditional definition or the set of non-negative integers {, 1, 2, ...} according to...
s satisfy the axioms of PA, there are other
non-standard modelIn model theory, a discipline within mathematical logic, a non-standard model is a model of a theory that is not isomorphic to the intended model . If the intended model is infinite and the language is first-order, then the Löwenheim-Skolem theorems guarantee the existence of non-standard models...
s as well; the
compactness theoremIn mathematical logic, the compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model...
implies that the existence of nonstandard elements cannot be excluded in first-order logic. The upward
Löwenheim–Skolem theoremIn mathematical logic, the Löwenheim–Skolem theorem states that if a countable first-order theory has an infinite model, then for every infinite cardinal number κ it has a model of size κ...
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
ZFCZermelo–Fraenkel set theory with the axiom of choice, commonly abbreviated ZFC, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics...
, 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 TennenbaumTennenbaum's theorem, named for Stanley Tennenbaum who presented the theorem in 1959, is a result in mathematical logic that states that no countable nonstandard model of Peano arithmetic can be recursive.-Recursive structures for PA:...
, proved in 1959, shows that there is no countable nonstandard model of PA in which either the addition or multiplication operation is
computableComputable functions are the basic objects of study in computability theory. The set of computable functions is equivalent to the set of Turing-computable functions and partial recursive functions. Computable functions are the formalized analogue of the intuitive notion of algorithm...
. 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 theoreticThe modern study of set theory was initiated by Cantor and Dedekind in the 1870s. After the discovery of paradoxes in informal set theory, numerous axiom systems were proposed in the early twentieth century, of which the Zermelo–Fraenkel axioms, with the axiom of choice, are the best-known.The...
constructions of the
natural numberIn mathematics, there are two conventions for the set of natural numbers: it is either the set of positive integers {, , , ...} according to the traditional definition or the set of non-negative integers {, 1, 2, ...} according to...
s and axioms of set theory such as the ZF. The standard construction of the naturals, due to
John von NeumannJohn von Neumann was a Hungarian American mathematician who made major contributions to a vast range of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, continuous geometry, economics and game theory, computer science, numerical analysis, hydrodynamics John...
, 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
closedIn mathematics, a set is said to be closed under some operation if performance of that operation on members of the set always produces a member of the set...
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
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 theoryGeneral set theory is George Boolos's name for a fragment of the canonical axiomatic set theory Z. GST is sufficient for all mathematics not requiring infinite sets, and is the weakest known set theory whose theorems include the Peano axioms....
(
extensionalityIn logic, extensionality, or extensional equality refers to principles that judge objects to be equal if they have the same external properties...
, existence of the
empty setIn mathematics, and more specifically set theory, the empty set is the unique set having no members; its size is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
, and the
axiom of adjunctionGeneral set theory is George Boolos's name for a fragment of the canonical axiomatic set theory Z. GST is sufficient for all mathematics not requiring infinite sets, and is the weakest known set theory whose theorems include the Peano axioms....
), 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 theoryIn mathematics, category theory deals in an abstract way with mathematical structures and relationships between them: it abstracts from sets and functions to objects linked in diagrams by morphisms or arrows....
. Let
C be a
categoryIn mathematics, a category is an algebraic structure consisting of a collection of "objects", linked together by a collection of "arrows" that have two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. Objects and arrows may...
with
initial objectIn category theory, an abstract branch of mathematics, an initial object of a category C is an object I in C such that for every object X in C, there exists precisely one morphism I → X...
1
C, and define the category of
pointed unary systems, US
1(
C) as follows:
- The objects of US1(C) are triples (X, 0X, SX) where X is an object of C, and 0X : 1C → X and SX : X → X are C-morphisms.
- A morphism φ : (X, 0X, SX) → (Y, 0Y, SY) is a C-morphism φ : X → Y with φ 0X = 0Y and φ SX = SY φ.
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 objectIn category theory, a natural number object is an object endowed with a recursive structure similar to natural numbers. More precisely, in a category E with a terminal object 1 , an NNO N is given by:...
in
C. If (
N, 0,
S) is this initial object, and (
X, 0
X,
SX) is any other object, then the unique map
u : (
N, 0,
S) → (
X, 0
X,
SX) is such that
This is precisely the recursive definition of 0
X and
SX.
Consistency
When the Peano axioms were first proposed,
Bertrand RussellBertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was an English philosopher, logician, mathematician, historian, and social critic. Although he spent the majority of his life in England, he was born in Wales, where he also died.Russell led the British "revolt against idealism" in the...
and others agreed that these axioms implicitly defined what we mean by a "natural number".
Henri PoincaréJules Henri Poincaré was a French mathematician and theoretical physicist, and a philosopher of science...
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 HilbertDavid Hilbert was a German mathematician, recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. He discovered and developed a broad range of fundamental ideas in many areas, including invariant theory and the axiomatization of geometry...
posed the problem of proving their consistency using only finitistic methods as the
secondIn mathematics, Hilbert's second problem was posed by David Hilbert in 1900 as one of his 23 problems. It asks for a proof that arithmetic is consistent – free of any internal contradictions....
of his
twenty-three problemsHilbert's problems are a list of twenty-three problems in mathematics published by German mathematician David Hilbert during 1900. The problems were all unsolved at the time, and several of them were very influential for 20th century mathematics...
. In 1931,
Kurt GödelKurt Gödel was an Austrian-American logician, mathematician and philosopher. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the 20th century, a time when many, such as Bertrand Russell, A. N...
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 theoryIn mathematics, logic and computer science, type theory is any of several formal systems that can serve as alternatives to naive set theory, or the study of such formalisms in general...
. In 1936,
Gerhard GentzenGerhard Karl Erich Gentzen was a German mathematician and logician....
gave a proof of the consistency of Peano's axioms, using
transfinite inductionTransfinite induction is an extension of mathematical induction to well-ordered sets, for instance to sets of ordinals or cardinals.- 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 machineA Turing machine is a theoretical device that manipulates symbols contained on a strip of tape. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside of a computer. The Turing...
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 proofGentzen's consistency proof is a result of proof theory in mathematical logic. It "reduces" the consistency of a simplified part of mathematics, not to something that could be proved , but to clarified logical principles.-Gentzen's theorem:In 1936 Gerhard Gentzen proved the consistency of...
. The small number of mathematicians who advocate
ultrafinitismIn the philosophy of mathematics, ultrafinitism, or ultraintuitionism, is a form of finitism.Like other strict finitists, ultrafinitists deny the existence of the infinite set N of natural numbers, on the grounds that it can never be completed....
reject Peano's axioms because the axioms require an infinite set of natural numbers.
See also
- Foundational status of arithmetic
- Gentzen's consistency proof
Gentzen's consistency proof is a result of proof theory in mathematical logic. It "reduces" the consistency of a simplified part of mathematics, not to something that could be proved , but to clarified logical principles.-Gentzen's theorem:In 1936 Gerhard Gentzen proved the consistency of...
- Goodstein's theorem
In mathematical logic, Goodstein's theorem is a statement about thenatural numbers, made by Reuben Goodstein, which states that every Goodstein sequence eventually terminates at 0. Kirby & Paris showed that it is unprovable in Peano arithmetic...
- Paris–Harrington theorem
In mathematical logic, the Paris–Harrington theorem states that a certain combinatorial principle in Ramsey theory is true, but not provable in Peano arithmetic...
- Presburger arithmetic
Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929. The signature of Presburger arithmetic contains only the addition operation and equality, omitting the multiplication operation entirely...
- Robinson arithmetic
In mathematics, Robinson arithmetic, or Q, is a finitely axiomatized fragment of Peano arithmetic , first set out in Robinson . Q is essentially PA without the axiom schema of induction...
- Second-order arithmetic
In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets. It is an alternative to axiomatic set theory as a foundation for much, but not all, of mathematics. It was introduced by...
- Non-standard arithmetic
In mathematical logic, a nonstandard model of arithmetic is a model of Peano arithmetic that contains nonstandard numbers. The standard model of arithmetic consists of the set of standard natural numbers {0, 1, 2, …}. The elements of any model of Peano arithmetic are linearly ordered and possess...
- Set-theoretic definition of natural numbers
-The contemporary standard:In standard set theory the natural numbersare defined recursively by 0 = {} and n+1 = n ∪ {n}. Then n = {0,1,...,n−1} for each natural number n...
External links
----