Peano axioms
Encyclopedia
In mathematical logic
Mathematical logic
Mathematical 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 axiom
Axiom
In 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 number
Natural number
In 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 Italian
Italian people
The 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...

 mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....

 Giuseppe Peano
Giuseppe Peano
Giuseppe 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 metamathematical
Metamathematics
Metamathematics 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 consistency
Consistency proof
In 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 completeness
Completeness
In 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 theory
Number theory
Number 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 arithmetic
Arithmetic
Arithmetic 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 Grassmann
Hermann Grassmann
Hermann 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 induction
Mathematical induction
Mathematical 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 Dedekind
Richard Dedekind
Julius 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-order
First-order logic
First-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 order
Second-order logic
In 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 induction
Mathematical induction
Mathematical 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 schema
Axiom schema
In 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 logic
Mathematical logic
Mathematical 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 Begriffsschrift
Begriffsschrift
Begriffsschrift is a book on logic by Gottlob Frege, published in 1879, and the formal system set out in that book...

 by Gottlob Frege
Gottlob Frege
Friedrich 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 Boole
George Boole
George 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öder
Ernst Schröder
Ernst 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 symbol
Non-logical symbol
In 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:
  1. 0 is a natural number.


The next four axioms describe the equality relation
Relation (mathematics)
In 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...

.
  1. For every natural number x, x = x. That is, equality is reflexive
    Reflexive relation
    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:...

    .
  2. For all natural numbers x and y, if x = y, then y = x. That is, equality is symmetric
    Symmetric relation
    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:...

    .
  3. For all natural numbers x, y and z, if x = y and y = z, then x = z. That is, equality is transitive
    Transitive relation
    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....

    .
  4. 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
    Closure (mathematics)
    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" function
Function (mathematics)
In 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.
  1. 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 identity
Identity element
In 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 unary
Unary numeral system
The 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 Sn(0). The next two axioms define the properties of this representation.
  1. For every natural number n, S(n) = 0 is False. That is, there is no natural number whose successor is 0.
  2. For all natural numbers m and n, if S(m) = S(n), then m = n. That is, S is an injection
    Injective function
    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.



  1. 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:


  1. 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 axiom
Second-order logic
In 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-order
First-order logic
First-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 arithmetic
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...

, which can be expressed without second-order logic.

Arithmetic

The Peano axioms can be augmented with the operations of addition
Addition
Addition 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 multiplication
Multiplication
Multiplication 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) ordering
Total order
In 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 logic
Second-order logic
In 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 × NN (written in the usual infix notation
Infix notation
Infix 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,...

, mapping
Map (mathematics)
In 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 recursively
Recursion
Recursion 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 structure
Structure (mathematical logic)
In 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 semigroup
Semigroup
In 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 cancellative
Cancellation property
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 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...

 magma
Magma (algebra)
In 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 embeddable
Embedding
In mathematics, an embedding is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup....

 in a group
Group (mathematics)
In 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 integer
Integer
The 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, multiplication
Multiplication
Multiplication 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 × NN defined recursively as:
It is easy to see that 1 is the multiplicative identity
Identity element
In 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 semiring
Semiring
In 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 order
Total order
In 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, bN, ab if and only if there exists some cN such that a + c = b.

This relation is stable under addition and multiplication: for , if ab, then:
  • a + cb + c, and
  • a · cb · c.

Thus, the structure (N, +, ·, 1, 0, ≤) is an ordered semiring
Ordered ring
In 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, kN, if kn implies φ(k) is true, then φ(S(n)) is true,
then for every nN, φ(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-order
Well-order
In 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 nonempty
Empty set
In 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...

 subset
Subset
In 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 XN 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 nN, suppose for every kn, kX. Then S(n) ∉ X, for otherwise it would be the least element of X.

Thus, by the strong induction principle, for every nN, nX. Thus, XN = ∅, which contradicts
Contradiction
In 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 model
Model theory
In 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 : NN satisfies the axioms above. Dedekind
Richard Dedekind
Julius 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 isomorphic
Isomorphism
In 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 (NA, 0A, SA) and (NB, 0B, SB) of the Peano axioms, there is a unique homomorphism
Homomorphism
In 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 : NANB satisfying
and it is a bijection. The second-order Peano axioms are thus categorical
Morley's categoricity theorem
In 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-order
First-order logic
First-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 order
Second-order logic
In 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 model
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....

 or proof theoretic
Proof theory
Proof 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 logic
First-order logic
First-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 schema
Axiom schema
In 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 infinite
Countable set
In 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,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 definable
Structure (mathematical logic)
In 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 semirings
Ordered ring
In 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.

  1. . , i.e., addition is associative.
  2. . , i.e., addition is commutative.
  3. . , i.e., multiplication is associative.
  4. . , i.e., multiplication is commutative.
  5. . , i.e., the distributive law.
  6. . , i.e., zero is the identity element for addition
  7. . , i.e., one is the identity element for multiplication.
  8. . , i.e., the '<' operator is transitive
    Transitive relation
    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....

    .
  9. . , i.e., the '<' operator is irreflexive
    Reflexive relation
    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:...

    .
  10. . .
  11. . .
  12. . .
  13. . . .
  14. . .
  15. . .

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 number
Natural number
In 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 model
Non-standard model
In 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 theorem
Compactness theorem
In 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 theorem
Löwenheim–Skolem theorem
In 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 ZFC
Zermelo–Fraenkel set theory
In 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 theorem
Tennenbaum's theorem
Tennenbaum'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 computable
Computable function
Computable 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 theoretic
Set theory
Set 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 number
Natural number
In 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 Neumann
John von Neumann
John 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 closed
Closure (mathematics)
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 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 : NN 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
General set theory
General 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:...

 (extensionality
Extensionality
In 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 set
Empty set
In 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 adjunction
General set theory
General 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 theory
Category theory
Category 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 category
Category (mathematics)
In 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 object
Initial object
In 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...

 1C, and define the category of pointed unary systems, US1(C) as follows:
  • The objects of US1(C) are triples (X, 0X, SX) where X is an object of C, and 0X : 1CX and SX : XX are C-morphisms.
  • A morphism φ : (X, 0X, SX) → (Y, 0Y, SY) is a C-morphism φ : XY with φ 0X = 0Y and φ SX = SY φ.

Then C is said to satisfy the Dedekind–Peano axioms if US1(C) has an initial object; this initial object is known as a natural number object
Natural number object
In 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, 0X, SX) is any other object, then the unique map u : (N, 0, S) → (X, 0X, SX) is such that
This is precisely the recursive definition of 0X and SX.

Consistency

When the Peano axioms were first proposed, Bertrand Russell
Bertrand Russell
Bertrand 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é
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 Hilbert
David Hilbert
David 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 second
Hilbert's second problem
In 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 problems
Hilbert's problems
Hilbert'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ödel
Kurt Gödel
Kurt 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 theory
Type theory
In 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 Gentzen
Gerhard Gentzen
Gerhard 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 induction
Transfinite induction
Transfinite 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 machine
Turing machine
A 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 proof
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...

. The small number of mathematicians who advocate ultrafinitism
Ultrafinitism
In 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
    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
    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
    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
    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
    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
    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
    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
    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
    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

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK