In
mathematical logicMathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical 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 proven or demonstrated but considered either to be self-evident or to define and delimit the realm of analysis. In other words, an axiom is a logical statement that is assumed to be true...
s for the
natural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s presented by the 19th century
ItalianThe Italian people are an ethnic group that share a common Italian culture, ancestry and speak the Italian language as a mother tongue. Within Italy, Italians are defined by citizenship, regardless of ancestry or country of residence , and are distinguished from people...
mathematicianA mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
Giuseppe PeanoGiuseppe Peano was an Italian mathematician, whose work was of 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 the Peano axioms in...
. 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 and only if it has a model, i.e. there exists an interpretation under which all...
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:In logic, semantic completeness is the converse of soundness for formal systems...
of
number theoryNumber theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
.
The need for formalism 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. It involves the study of quantity, especially as the result of combining numbers...
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 also 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...
. In 1881, Charles Sanders Peirce provided an axiomatization of natural-number arithmetic. 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 axiom asserts the existence of at least one member of the set "number". The next four are general statements about
equality; in modern treatments these are often considered axioms of the "underlying logic". The next three axioms are
first-orderFirst-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, 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...
over the natural numbers. A weaker first-order system called
Peano arithmetic is obtained by explicitly adding the addition and multiplication operation symbols and replacing the second-order induction axiom with a first-order
axiom 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 axioms
When Peano formulated his axioms, the language of
mathematical logicMathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical 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 (∈, which is from Peano's ε) and implication (⊃, which is 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 a book on logic by Gottlob Frege, published in 1879, and the formal system set out in that book...
by
Gottlob FregeFriedrich Ludwig Gottlob Frege was a German mathematician, logician and philosopher. He is considered to be one of the founders of modern logic, and made major contributions to the foundations of mathematics. He is generally considered to be the father of analytic philosophy, for his writings on...
, published in 1879. Peano was unaware of Frege's work and independently recreated his logical apparatus based on the work of
BooleGeorge Boole was an English mathematician and philosopher.As the inventor of Boolean logic—the basis of modern digital computer logic—Boole is regarded in hindsight as a founder 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 arithmetical properties of
natural numbers, usually represented as a set
N or
The signature (a formal language's
non-logical symbolIn logic, the formal languages used to create expressions consist of symbols which can be broadly divided into constants and variables. The constants of a language can further be divided into logical symbols and non-logical symbols .The non-logical symbols of a language of first-order logic consist...
s) for the axioms includes a constant symbol 0 and a unary function symbol
S.
The constant 0 is assumed to be a natural number:
- 0 is a natural number.
The next four axioms describe the
equality relationIn set theory and logic, a relation is a property that assigns truth values to k-tuples of 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 ~ on S where x~x holds true for every x in S. For example, ~ could be "is equal to".-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 unique member of the same set. For example, the real numbers are closed under subtraction, but the natural numbers are not: 3 and 8 are both natural numbers, but...
under equality.
The remaining axioms define the arithmetical properties of the natural numbers. The naturals are assumed to be closed under a single-valued "successor"
functionIn mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
S.
- 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 1 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 arithmetic, most modern formulations of the Peano axioms start from 0. Axioms 1 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)) (which is also
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 is False. 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 preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...
.
Axioms 1, 6, 7 and 8 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. To show that every natural number is included in this set requires an additional axiom, which is sometimes called the
axiom of induction. This axiom provides a method for reasoning about the set of 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 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.
In Peano's original formulation, the induction axiom is a
second-order axiomIn 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....
. It is now common to replace this second-order principle with a weaker
first-orderFirst-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
induction scheme. There are important differences between the second-order and first-order formulations, as discussed in the section Models below. Without the axiom of induction, the remaining Peano axioms give a theory equivalent to
Robinson arithmeticIn mathematics, Robinson arithmetic, or Q, is a finitely axiomatized fragment of Peano arithmetic , first set out in R. M. Robinson . Q is essentially PA without the axiom schema of induction. Since Q is weaker than PA, it is incomplete...
, which can be expressed without second-order logic.
Arithmetic
The Peano axioms can be augmented with the operations of
additionAddition is a mathematical operation that represents combining collections of objects together into a larger collection. 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....
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 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
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,...
,
mappingIn most of mathematics and in some related technical fields, the term mapping, usually shortened to map, is either a synonym for function, or denotes a particular kind of function which is important in that branch, or denotes something conceptually similar to a function.In graph theory, a map is a...
elements of
N to other elements of
N), defined
recursivelyRecursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
as:
For example,
- a + 1 = a + S(0) = S(a + 0) = S(a).
The
structureIn universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations which are defined on it....
(
N, +) is a commutative
semigroupIn mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation. A semigroup generalizes a monoid in that there might not exist an identity element...
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 \times M \rightarrow 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 formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s.
Multiplication
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...
.
Inequalities
The usual
total orderIn 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, assuming 0 is a natural number:
- For all a, b ∈ N, a ≤ b if and only if there exists some c ∈ N such that a + c = b.
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 R 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 strict 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 strict total order...
ed—every
nonemptyIn mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality 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. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
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
contradictsIn 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, usually opposite inversions of each other...
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 using tools from mathematical logic....
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 (including the second-order induction axiom) are
isomorphicIn abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations. If there exists an isomorphism between two structures, the two structures are said to be isomorphic. In a certain sense, isomorphic structures are...
. In particular, given two models (
N_{A}, 0
_{A},
S_{A}) and (
N_{B}, 0
_{B},
S_{B}) of the Peano axioms, there is a unique
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 :
N_{A} →
N_{B} satisfying
and it is a bijection. The second-order 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 logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, 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 using tools from mathematical logic....
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 of the Peano axiom except the ninth axiom (the induction axiom) are statements in
first-order logicFirst-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, 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...
.
First-order axiomatizations of Peano arithmetic have an important limitation, however. In second-order logic, it is possible to define the addition and multiplication operations from the successor operation, but this cannot be done in the more restrictive setting of first-order logic. Therefore, the addition and multiplication operations are directly included in the signature of Peano arithmetic, and axioms are included that relate the three operations to each other.
The following list of axioms (along with the usual axioms of equality) is sufficient for this purpose:
In addition to this list of numerical axioms, Peano arithmetic contains the induction schema, which 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. The term was originated by Georg Cantor...
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
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 φ.
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 operations 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, addition, and multiplications operations, other axiomatizations use the language of
ordered semiringsIn abstract algebra, an ordered ring is a commutative ring R 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 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., the distributive law.
- . , i.e., zero is the identity element for addition
- . , i.e., one is the identity element for multiplication.
- . , 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....
.
- . , i.e., the '<' operator is irreflexive
In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation ~ on S where x~x holds true for every x in S. For example, ~ could be "is equal to".-Related terms:...
.
- . .
- . .
- . .
- . . .
- . .
- . .
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, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
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, named for Leopold Löwenheim and Thoralf Skolem, 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
ZFCIn mathematics, Zermelo–Fraenkel set theory with the axiom of choice, named after mathematicians Ernst Zermelo and Abraham Fraenkel and commonly abbreviated ZFC, is one of several axiomatic systems that were proposed in the early twentieth century to formulate a theory of sets without the paradoxes...
, 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.
Tennenbaum's theoremTennenbaum'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. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
. This result shows it is difficult to be completely explicit in describing the addition and multiplication operations of a countable nonstandard model of PA. However, there is only one possible order type of a countable nonstandard model. Letting ω be the order type of the natural numbers, ζ be the order type of the integers, and η be the order type of the rationals, the order type of any countable nonstandard model of PA is ω + ζ·η, which can be visualized as a copy of the natural numbers followed by a dense linear ordering of copies of the integers.
Set-theoretic models
The Peano axioms can be derived from
set theoreticSet theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
constructions of the
natural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
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 and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...
, 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 unique member of the same set. For example, the real numbers are closed under subtraction, but the natural numbers are not: 3 and 8 are both natural numbers, but...
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 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.-Ontology:...
(
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 elements; its size or cardinality 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 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.-Ontology:...
), 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 theoryCategory theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
. Let
C be a
categoryIn mathematics, a category is an algebraic structure that comprises "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the category of sets, whose...
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 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 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},
S_{X}) is any other object, then the unique map
u : (
N, 0,
S) → (
X, 0
_{X},
S_{X}) is such that
This is precisely the recursive definition of 0
_{X} and
S_{X}.
Consistency
When the Peano axioms were first proposed,
Bertrand RussellBertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...
and others agreed that these axioms implicitly defined what we mean by a "natural number".
Henri PoincaréJules Henri Poincaré was a French mathematician, theoretical physicist, engineer, 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. He is recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many areas, including invariant theory and the axiomatization of...
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 form a list of twenty-three problems in mathematics published by German mathematician David Hilbert in 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 Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...
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. He had his major contributions in the foundations of mathematics, proof theory, especially on natural deduction and sequent calculus...
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 ordinal numbers or cardinal numbers.- Transfinite induction :Let P be a property defined for all ordinals α...
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 on a strip of tape according to a table of rules. 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 a...
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 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, also known as ultraintuitionism, strict-finitism, actualism, and strong-finitism is a form of finitism. There are various philosophies of mathematics which are called ultrafinitism...
reject Peano's axioms because the axioms require an infinite set of natural numbers.
See also
- Foundations of mathematics
Foundations of mathematics is a term sometimes used for certain fields of mathematics, such as mathematical logic, axiomatic set theory, proof theory, model theory, type theory and recursion theory...
- 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 the natural numbers, made by Reuben Goodstein, which states that every Goodstein sequence eventually terminates at 0. 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 R. M. Robinson . Q is essentially PA without the axiom schema of induction. Since Q is weaker than PA, it is incomplete...
- 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 David Hilbert and Paul Bernays in their...
- Non-standard model of arithmetic
- Set-theoretic definition of natural numbers
Several ways have been proposed to define the natural numbers using set theory.- The contemporary standard :In standard, Zermelo-Fraenkel set theory the natural numbers...
- Frege's theorem
Frege's theorem states that the Peano axioms of arithmetic can be derived in second-order logic from Hume's principle. It was first proven, informally, by Gottlob Frege in his Die Grundlagen der Arithmetik , published in 1884, and proven more formally in his Grundgesetze der Arithmetik , published...
External links