In mathematics, the Peano axioms (or Peano postulates) are a set of second-order axioms proposed by Giuseppe Peano which determine the theory of the natural numbers. These axioms are usually encountered in a first-order form, where the crucial second-order induction axiom is replaced by an infinite first-order induction schema; this first order theory is called Peano arithmetic (PA). The theory of Peano arithmetic is much weaker than that of the second-order Peano axioms. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... In mathematical logic, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. ... An axiom is a sentence or proposition that is not proved or demonstrated and is considered as obvious or as an initial necessary consensus for a theory building or acceptation. ... Giuseppe Peano Giuseppe Peano (August 27, 1858 – April 20, 1932) was an Italian mathematician and philosopher best known for his contributions to set theory. ... In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ... First-order logic (FOL) is a universal language in symbolic science, and is in use everyday by mathematicians, philosophers, linguists, computer scientists and practitioners of artificial intelligence. ... Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. ...

Peano first presented his axioms in a Latin text Arithmetices principia, nova methodo exposita ("The principles of arithmetic, presented by a new method"), published in 1889 (Peano 1889). Peano gave nine axioms, of which four axioms specify the behavior of the equality relation and the other five specify the arithmetic terms for one and successor. It is the latter five rules that are usually intended when one discusses the Peano axioms. Peano preceded his axioms for arithmetic with a brief treatment of the logical apparatus to be employed, but he did not fundamentally discuss the underlying logical principles.

Peano arithmetic constitutes a fundamental formalism for arithmetic, and the Peano axioms can be used to construct many of the most important number systems and structures of modern mathematics. Peano arithmetic raises a number of metamathematical and philosophical issues, primarily involving questions of consistency and completeness. Arithmetic tables for children, Lausanne, 1835 Arithmetic or arithmetics (from the Greek word αριθμός = number) is the oldest and most elementary branch of mathematics, used by almost everyone, for tasks ranging from simple daily counting to advanced science and business calculations. ... In mathematics, a number system is a set of numbers, or number-like objects, together with one or more operations, such as addition or multiplication. ... In general, metamathematics or meta-mathematics is reflection about mathematics seen as an entity/object in human consciousness and culture. ... // Philosophy of mathematics is the branch of philosophy that studies the philosophical assumptions, foundations, and implications of mathematics. ... In mathematical logic, a formal system is consistent if it does not contain a contradiction, or, more precisely, for no proposition φ are both φ and ¬φ provable. ... Gödels completeness theorem is an important theorem in mathematical logic which was first proved by Kurt Gödel in 1929. ...

Peano's axioms

Peano created a logical notation to use in presenting his axioms. Although this notation is not in contemporary use, it is very similar to modern notation. Peano uses the symbol ε for set membership and a reversed C for logical implication (which became ⊃).

The axioms are based on the successor operation, written Sa or S(a), which adds 1 to its argument. Thus S(1) = 2, S(S(1)) = S(2) = 3, and in general S(a) = a + 1. The axioms do not use the addition symbol; they outline certain properties of the successor operation which are sufficient to recreate addition in terms of the successor function.

Peano's nine axioms, rephrased in contemporary notation, are:

1. 1 is a natural number.
2. Every natural number is equal to itself (equality is reflexive).
3. For all natural numbers a and b, a = b if and only if b = a (equality is symmetric).
4. For all natural numbers a, b, and c, if a = b and b = c then a = c (equality is transitive).
5. If a = b and b is a natural number then a is a natural number.
6. If a is a natural number then Sa is a natural number.
7. If a and b are natural numbers then a = b if and only if Sa = Sb.
8. If a is a natural number then Sa is not equal to 1.
9. For every set K, if 1 is in K, and Sx is in K for every natural number x in K, then every natural number is in K. (It makes no difference here whether all elements of K are natural numbers.)

Axioms 2, 3, 4, and 5 are now considered basic properties of equality and taken for granted in most contexts. Thus it is axioms 1, 6, 7, 8, and 9 which describe the structure of the natural numbers. In set theory, a binary relation can have, among other properties, reflexivity or irreflexivity. ... 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 mathematics, a binary relation R over a set X is transitive if it holds for all a, b, and c in X, that if a is related to b and b is related to c, then a is related to c. ... In mathematics, two mathematical objects are considered equal if they are precisely the same in every way. ...

Axioms 6, 7, and 8 determine the properties of the successor operation. Axiom 6 states that every natural number has a successor, axiom 7 states that the successor operation is an injection from the natural numbers to themselves, and axiom 8 states that 1 is not the successor of any natural number. These axioms imply that the set of natural numbers is infinite, because no two elements of the chain An injective function. ...

can be the same. Axioms 1 through 8 are not enough to prove that this chain contains all of the natural numbers, however.

Axiom 9 is the induction axiom; it implies that any set of natural numbers containing 1 and closed under the successor operation contains every natural number. It thus implies that the chain above contains all the natural numbers, because the chain contains 1 and whenever a natural number x is in the chain then so is Sx. Because this axiom has a quantifier over all sets, it is a second-order statement. In mathematical logic, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. ...

Existence and uniqueness

Any infinite set X with a non-surjective injection f from X to X can be used to define a model of Peano's axioms. This model will consist of a set N of elements, which stand for the natural numbers; a particular one of these elements that stands for 1; and a function from N to N that stands for S. To create this model from the infinite set X, first choose any element of X that is not in the range of f to stand for 1. Then define the symbol S to stand for the function f. Finally, let the set N of "natural numbers" be the intersection of all subsets of X that contain 1 and are closed under f. This set N will satisfy all of Peano's axioms. A surjective function. ... An injective function. ... In the mathematical discipline of model theory, a structure for a language (referred to as an -structure, and commonly written as a Gothic capital) is an ordered pair whose first member is the domain of discourse or universe set (taken to be a set with possibly relations and functions defined...

Dedekind proved in his 1888 book Was sind und was sollen die Zahlen that any model of the second-order Peano axioms is isomorphic to the natural numbers; in modern terminology, the second-order theory of the Peano axioms is called categorical. The proof uses the induction axiom in a crucial way. Suppose that two models of the Peano axioms, (N_A, 1_A, S_A) and (N_B, 1_B, S_B), are given. Define a function f from N_A to N_B as follows. First define f(1_A) = 1_B. Then, by recursion, define f(S_Ax) to be S_Bf(x). The set of x in N_A for which f is defined includes 1_A and is closed under S_A, so by the induction axiom f is defined for all elements of N_A. Also, the range of f includes 1_B and is closed under S_B, so the range is all of N_B by the induction axiom. It can be shown that f is a bijection and, by definition, f(1_A) = 1_B and f(S_Ax) = S_Bf(x). Thus f is an isomorphism from N_A to N_B. In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of mapping between objects, devised by Eilhard Mitscherlich, which shows a relation between two properties or operations. ... In model theory, Morleys categoricity theorem is a theorem of Michael D. Morley which states that if a first-order theory is complete in a countable language, then if it is categorical in some uncountable cardinality, it is categorical in all uncountable cardinalities. ... In mathematics, a bijection, bijective function, or one-to-one correspondence is a function that is both injective (one-to-one) and surjective (onto), and therefore bijections are also called one_to_one and onto. ...

Historical placement

During the period when he published his axioms for arithmetic, Peano was both influenced by and influencing the work of other mathematicians. In particular, he acknowledges that he makes great use of Grassmann (1861) and Dedekind (1888). Hermann Günther Grassmann (April 15, 1809, Stettin – September 26, 1877, Stettin) was a German polymath, renowned in his day as a linguist and now admired as a mathematician. ... Richard Dedekind Julius Wilhelm Richard Dedekind (October 6, 1831 – February 12, 1916) was a German mathematician who did important work in abstract algebra and the foundations of the real numbers. ...

Peano's paper employs a logical symbolism and maintains a clear distinction between mathematical and logical symbols, which was not yet common in mathematics. Such a separation had first been introduced in the Begriffsschrift by Gotlob Frege, published in 1879. Peano was unaware of Frege's work, however, and so independently recreated the logical apparatus he needed based on his knowledge of work by Boole and Schröder (Van Heijenoort 1967, p. 83). Begriffsschrift is the title of a short book on logic by Gottlob Frege, published in 1879, and is also the name of the formal system set out in that book. ... Friedrich Ludwig Gottlob Frege (8 November 1848, Wismar – 26 July 1925, Bad Kleinen) (IPA: ) was a German mathematician who became a logician and philosopher. ... George Boole [], (November 2, 1815 – December 8, 1864) was a British mathematician and philosopher. ... Ernst Schröder Ernst Schröder (25 November 1841 Mannheim, Germany - 16 June 1902 Karlsruhe Germany) was a German mathematician mainly known for his work on algebraic logic. ...

Modern variations

Although Peano's axioms, as stated above, are adequate for many purposes, there are several variations on the Peano axioms common in contemporary texts.

One common variation is to begin the natural numbers with 0 rather than 1. This causes only cosmetic changes to the theory, and is convenient if the arithmetical operations of addition and multiplication will be defined. Both the convention of starting with 1 and the convention of starting with 0 are common in contemporary presentations of Peano's axioms. Presentations of Peano arithmetic, which includes the addition and multiplication operations, typically begin with 0.

A second common variation is to replace the axioms above with the axioms of a discrete ordered ring, in a language including addition and multiplication operations, and then add an axiom of induction to these to obtain a theory equivalent to the one presented above. This is discussed in more detail in the section on Peano arithmetic.

Binary operations and ordering

Peano's axioms can be augmented by definitions of addition and multiplication over the natural numbers N, and by the usual ordering of N. These definitions require set theory or second-order logic in order to construct the desired function, after which the axioms of Peano arithmetic prove that it is unique. It is convenient to start with 0 instead of 1.

To define the addition operation + recursively in terms of successor and 0, let a + 0 = a and a + Sb = S(a + b) for all a and b. Then (N, +) can be shown to be a commutative semigroup with identity element 0; it is called the free monoid with one generator. This monoid satisfies the cancellation property and is therefore embeddable in a group; the smallest group containing the natural numbers is the integers. Addition of natural numbers is the most basic arithmetic operation. ... In mathematics, especially abstract algebra, a binary operation * on a set S is commutative if x * y = y * x for all x and y in S. Otherwise * is noncommutative. ... In mathematics, a semigroup is an algebraic structure consisting of a set S closed under an associative binary operation. ... In mathematics, an identity element (or neutral element) is a special type of element of a set with respect to a binary operation on that set. ... The idea of a free object in mathematics is one of the basics of abstract algebra. ... In mathematics, an element a in a magma (M,*) has the left cancellation property (or is left-cancellative) if for all b and c in M, a * b = a * c always implies b = c. ... This picture illustrates how the hours on a clock form a group under modular addition. ... The integers are commonly denoted by the above symbol. ...

Let 1 stand for S0. It follows from the definition above that for any natural number b,

b + 1 = b + S0 = S(b + 0) = Sb.

This shows that b + 1 is simply the successor Sb of b.

Given successor, addition, and 0, the multiplication operation · is recursively defined by the axioms and . Hence (N, ·) is also a commutative monoid with identity element 1. Moreover, addition and multiplication are compatible by virtue of the distribution law: In mathematics, especially abstract algebra, a binary operation * on a set S is commutative if x * y = y * x for all x and y in S. Otherwise * is noncommutative. ... In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element. ... In mathematics, an identity element (or neutral element) is a special type of element of a set with respect to a binary operation on that set. ... In mathematics, and in particular in abstract algebra, distributivity is a property of binary operations that generalises the distributive law from elementary algebra. ...

.

Thus (N, +, ·, 0, 1) is a commutative semiring. In abstract algebra, a semiring is an algebraic structure, similar to a ring, but without additive inverses. ...

It is possible to define the usual total order ≤ on N as follows. For any two natural numbers a and b, put a ≤ b if and only if there exists a natural number c such that a+c = b. This order is compatible with addition and multiplication in the following sense: if a, b and c are natural numbers and a ≤ b, then a+c ≤ b+c and a·c ≤ b·c. Thus the set N together with the arithmetic operations and the order ≤ is an ordered semiring. Because there is no natural number between 0 and 1, it is a discrete ordered semiring. In mathematics, a total order, linear order or simple order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ... Definitions In abstract algebra, an ordered ring is a commutative ring with a a total order such that if and , then if and , then . ...

A fundamental order property of N is that it is a well-ordered set; every nonempty subset of N has a least element. This follows from the induction axiom. If X is a set of natural numbers with no least element then 0 cannot be in X, and if no y ≤ x is in X then Sx cannot be in X (because then Sx would be the least element of X). Thus, by induction, no natural number is in X if there is no least natural number in X. In mathematics, a well-order (or well-ordering) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. ... The empty set is the set containing no elements. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, the terms, subset, superset and proper (or strict) subset or superset are used to describe the relation, called inclusion, of one set being contained inside another set. ...

Peano arithmetic

Peano arithmetic (PA) is a reformulation of the second-order Peano axioms as a first-order theory. The motivation for this reformulation is that first-order theories are more amenable to analysis in model theory and proof theory. The source of difficulty with Peano's axioms is the second-order induction axiom. In order to avoid problems with defining the addition and multiplication operations from the successor operation within the theory, discussed above, it is common to add these functions and their defining axioms directly to the basic first-order axiomatization. In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the structures that underlie mathematical systems. ... Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. ...

There are many different, but equivalent, formulations of the axioms for Peano arithmetic. One common formulation, described here, begins by defining a first-order theory PA⁻ whose models are the discrete ordered semirings. Then an induction schema is added to PA⁻ to obtain PA. The predicate "is a natural number" is not required in PA (and PA⁻) because the universe of discourse of PA is just the natural numbers N. The term universe of discourse generally refers to the entire set of terms used in a specific discourse, i. ...

Different authors may give different but equivalent lists of axioms for Peano arithmetic. The axioms of PA⁻ given by Kaye (1991) are:

While no explicit existential quantifiers appear in the most of the above axioms, implicit quantifiers of that nature follow from the closure of the natural numbers under zero, successor, addition, and multiplication. In predicate logic, existential quantification is an attempt to formalize the notion that something (a logical predicate) is true for something, or at least one relevant thing. ... In mathematics, the closure C(X) of an object X is defined to be the smallest object that both includes X as a subset and possesses some given property. ...

An important property of PA⁻ is that any structure M satisfying this theory has an initial segment isomorphic to the natural numbers. Elements of the structure that are not in this initial segment are called nonstandard elements.

To convert PA⁻ to PA, the first-order induction schema is added. This schema represents a countably infinite set of axioms. For each formula φ(x,y₁,...,y_k) in the language of Peano arithmetic, the first-order induction axiom for φ is the sentence In mathematics, a countable set is a set with the same cardinality (i. ... For the algebra software named Axiom, see Axiom computer algebra system. ...

where is an abbreviation for y₁,...,y_k. The first-order induction schema represents every instance of the first-order induction axiom, that is, it includes the induction axiom for every formula φ.

The motivation for the induction schema is that it is not possible to quantify over all sets of natural numbers using first-order logic. Thus it is not possible to express the statement that any set of natural numbers containing 0 and closed under successor is the entire set of natural numbers. What can be expressed in first-order logic is that any definable set of natural numbers has this property. But it is not possible to quantify over definable subsets explicitly with a single axiom; instead, one induction axiom is added for each formula φ that might be used to define a set of natural numbers. In this way, all definable sets are covered by the schema. In the mathematical discipline of model theory, a structure for a language (referred to as an -structure, and commonly written as a Gothic capital) is an ordered pair whose first member is the domain of discourse or universe set (taken to be a set with possibly relations and functions defined...

Although the natural numbers satisfy the axioms of PA, there are other, nonstandard models as well; the compactness theorem implies that the existence of nonstandard elements cannot be excluded in first-order logic. The upward Löwenheim-Skolem theorem shows that there are nonstandard models of PA of all infinite cardinalities. Moreover, when Dedekind's proof that the second-order Peano axioms have a unique model is viewed as a proof in a first-order axiomatization of set theory such as Zermelo–Fraenkel set theory, the proof only shows that each model of set theory has a unique model of the Peano axioms, up to isomorphism; nonstandard models of set theory may contain nonstandard models of the second-order Peano axioms. In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ... The compactness theorem is a basic fact in symbolic logic and model theory and asserts that a set (possibly infinite) of first-order sentences is satisfiable, i. ... In mathematical logic, the classic Löwenheim-Skolem theorem states that any infinite model M has a countably infinite submodel N that satisfies exactly the same set of first-order sentences that M satisfies. ... Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... Zermelo–Fraenkel set theory, with the axiom of choice, commonly abbreviated ZFC, is the most common form of axiomatic set theory, and as such is the most common foundation of mathematics. ...

Thus nonstandard models of PA are an unavoidable consequence of the first-order axiomatization. This is not the case with the second-order Peano axioms, which have only one model up to isomorphism. For this reason, the first-order axioms of PA are weaker than the second-order Peano axioms.

While nonstandard models of PA⁻ can be constructed in set theory, Stanley Tennenbaum proved in 1959 that there is no countable nonstandard model of PA in which either the addition or multiplication operation is computable (Kaye 1991 sec. 11.3). This shows that it is difficult to be completely explicit in describing the addition and multiplication operations on a countable nonstandard model of PA. Computable functions (or Turing-computable functions) are the basic objects of study in computability theory. ...

Church numerals are a model of the Peano axioms derived using the lambda calculus. Church encoding is a means of embedding data and operators into the lambda calculus, the most familiar form being the church numerals, a representation of the natural numbers using lambda notation. ... The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...

Construction of the natural numbers in set theory

Main article: Set-theoretic definition of natural numbers

A standard construction due to John von Neumann is used to create a canonical model of Peano's axioms, starting with 0, in set theory. In the context of set theory, the successor function S is defined for every set a with the rule S(a) = a ∪ {a}. A set A is defined to be an inductive set if it is closed under this successor function, which means that whenever an element a is in A then Sa is also in A. Several ways have been proposed to define the natural numbers using set theory. ... John von Neumann (Hungarian Margittai Neumann János Lajos) (born December 28, 1903 in Budapest, Austria-Hungary; died February 8, 1957 in Washington D.C., United States) was a Hungarian-born American mathematician who made contributions to quantum physics, functional analysis, set theory, topology, economics, computer science, numerical analysis, hydrodynamics... In the context of the axiom of infinity, an inductive set is a set with the property that, for every , the successor of is also an element of An example of an inductive set is the set of natural numbers See also Natural number Peano axioms External link Mathworld: Inductive...

The canonical model of Peano's axioms is defined in set theory by interpreting 0 as the empty set, letting S be the successor function just defined, and defining N to be the intersection of all inductive sets containing the empty set. The axiom of infinity guarantees the existence of an inductive set containing the empty set, and thus the set N is well-defined. The empty set is the set containing no elements. ... In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of infinity is one of the axioms of Zermelo-Fraenkel set theory. ...

This set N is defined to be the set of natural numbers; it is sometimes denoted by the Greek letter ω, especially in the context of studying ordinal numbers. In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ... Commonly, ordinal numbers, or ordinals for short, are numbers used to denote the position in an ordered sequence: first, second, third, fourth, etc. ...

In this construction of the natural numbers, each natural number is equal (as a set) to the set of natural numbers less than it, so that

• 0 = {}
• 1 = S(0) = {0}
• 2 = S(1) = {0,1} = {0, {0}}
• 3 = S(2) = {0,1,2} = {0, {0}, {0, {0}}}

and so on. The structure of the successor function is thus

or, equivalently,

This is not the only possible construction of a model of Peano's axioms. For instance, if we assume the construction of the set N = {0, 1, 2,...} and successor function S above, we could also define N = {5, 6, 7,...}, let the symbol 0 be interpreted as the set 5, and use f to interpret the successor function restricted to X. This gives another model of Peano's axioms:

Texts that derive Peano arithmetic from the axioms for ZF set theory include Suppes (1960) and Hatcher (1982). ZF may refer to: The Zermelo-Fraenkel axioms, a system of axioms in mathematical set theory. ...

Peano arithmetic can be seen to be equiconsistent with several weak systems of set theory (see Tarski and Givant 1987 sec. 7.6). One such system is ZFC with the axiom of infinity replaced by its negation. Another such system consists of general set theory (extensionality, existence of null set, and the axiom of adjunction), augmented by an axiom schema stating that a property that holds for the empty set and holds of an adjunction whenever it holds of the adjunct must hold for all sets. General set theory (GST) is the name George Boolos (1998) employed for a three axiom fragment of the canonical axiomatic set theory ZF. // GST consists of a single primitive ontological notion, that of set, and a single ontological assumption, namely that all individuals in the universe of discourse (i. ... In mathematics, this usually refers to some form of the principle, going back to Leibniz, that two mathematical objects are equal if there is no test to distinguish them. ... In measure theory, a null set is a set that is negligible for the purposes of the measure in question. ... General set theory (GST) is the name George Boolos (1998) employed for a three axiom fragment of the canonical axiomatic set theory ZF. // GST consists of a single primitive ontological notion, that of set, and a single ontological assumption, namely that all individuals in the universe of discourse (i. ...

Categorical interpretation

The Peano axioms may be interpreted in the general context of category theory. Let US₁ be the category of pointed unary systems; i.e. US₁ is the following category: In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ... In mathematics, categories allow one to formalize notions involving abstract structure and processes that preserve structure. ...

• The objects of US₁ are all ordered triples (X, x, f), where X is a set, x is an element of X, and f is a set map from X to itself.
• For each (X, x, f), (Y, y, g) in US₁, Hom_US1((X, x, f), (Y, y, g)) = {set maps φ : X → Y | φ(x) = y and φf = gφ}
• Composition of morphisms is the usual composition of set mappings.

The natural number system (N, 0, S) constructed above is an object in this category; it is called the natural unary system. It can be shown that the natural unary system is an initial object in US₁, and so it is unique up to a unique isomorphism. This means that for any other object (X, x, f) in US₁, there is a unique morphism φ : (N, 0, S)  →  (X, x, f). That is, that for any set X, any element x of X, and any set map f from X to itself, there is a unique set map φ : N → X such that φ(0) = x and φ (a + 1) = f(φ(a)) for all a in N. This is precisely the definition of simple recursion. In mathematics, an initial object of a category C is an object I in C such that to every object X in C, there exists precisely one morphism I → X. The dual notion is that of a terminal object: T is terminal, if to every object X in C... A visual form of recursion known as the Droste effect. ...

This concept can be generalized to arbitrary categories. Let C be a category with (unique) terminal object 1, and let US₁(C) be the category of pointed unary systems in C; i.e. US₁(C) is the following category: In mathematics, an initial object of a category C is an object I in C such that to every object X in C, there exists precisely one morphism I → X. The dual notion is that of a terminal object: T is terminal, if to every object X in C...

• The objects of US₁(C) are all ordered triples (X, x, f), where X is an object of C, and x : 1 → X and f : X → X are morphisms in C.
• For each (X, x, f), (Y, y, g) in US₁(C), Hom_US1(C)((X, x, f), (Y, y, g)) = {φ : φ is in Hom_C(X, Y), φx = y, and φf = gφ}
• Composition of morphisms is the composition of morphisms in C.

Then C is said to satisfy the Dedekind-Peano axiom if there exists an initial object in US₁(C). This initial object is called a natural number object in C. The simple recursion theorem is simply an expression of the fact that the natural number system (N, 0, S) is a natural number object in the category Set. In category theory, a natural number object (nno) is an object endowed with a recursive structure similar to natural numbers. ... In mathematics, the category of sets is the category whose objects are all sets and whose morphisms are all functions. ...

Consistency

Main article: Hilbert's second problem

When the Peano's axioms were first proposed, Bertrand Russell and others agreed that these axioms implicitly defined what we mean by a "natural number". Henri Poincaré was more cautious, saying they only defined natural numbers if they were consistent; if there is a proof that starts from just these axioms and derives a contradiction such as 0 = 1, then the axioms are inconsistent, and don't define anything. In 1900, David Hilbert posed the problem of proving their consistency using only finitistic methods as the second of his twenty-three problems. In 1931, Kurt Gödel proved his second incompleteness theorem, which shows that such a consistency proof cannot be formalized within Peano arithmetic itself. In mathematical logic, a formal system is consistent if it does not contain a contradiction, or, more precisely, for no proposition are both and provable. ... Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS, (18 May 1872 – 2 February 1970), was a British philosopher, logician, mathematician, advocate for social reform, and pacifist. ... Jules TuPac Henri Poincaré (April 29, 1854 – July 17, 1912) (IPA: [][1]) was one of Frances greatest mathematicians and theoretical physicists, and a philosopher of science. ... David Hilbert (January 23, 1862, Königsberg, East Prussia – February 14, 1943, Göttingen, Germany) was a German mathematician, recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. ... In mathematical logic, a formal system is consistent if it does not contain a contradiction, or, more precisely, for no proposition are both and provable. ... Hilberts problems are a list of twenty-three problems in mathematics put forth by German mathematician David Hilbert at the Paris conference of the International Congress of Mathematicians in 1900. ... [...]I dont believe in natural science. ... In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proven by Kurt Gödel in 1931. ...

Although it is widely claimed that Gödel's theorem rules out the possibility of a finitistic consistency proof for Peano arithmetic, this depends on exactly what one means by a finitistic proof. Gödel himself pointed out the possibility of giving a finitistic consistency proof of Peano arithmetic or stronger systems by using finitistic methods that are not formalizable in Peano arithmetic, and in 1958 Gödel published a method for proving the consistency of arithmetic using type theory. In 1936, Gerhard Gentzen gave a proof of the consistency of Peano's axioms, using transfinite induction up to an ordinal called ε₀. 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 ε₀ can be encoded in terms of finite objects (for example, as a Turing machine describing a suitable order on the integers). Whether or not Gentzen's proof meets the requirements Hilbert envisioned is unclear: there is no generally accepted definition of exactly what is meant by a finitistic proof, and Hilbert himself never gave a precise definition. At the broadest level, type theory is the branch of mathematics and logic that first creates a hierarchy of types, then assigns each mathematical (and possibly other) entity to a type. ... Gerhard Karl Erich Gentzen (November 24, 1909 – August 4, 1945) was a German mathematician and logician. ... Transfinite induction is the proof technique of mathematical induction when applied to (large) well-ordered sets, for instance to sets of ordinals or cardinals, or even to the class of all ordinals. ... In mathematics, ε0 is the smallest transfinite ordinal number which cannot be reached from ω (the smallest transfinite ordinal) with a finite number of the ordinal operations of addition, multiplication and exponentiation. ... An artistic representation of a Turing Machine . ...

The vast majority of contemporary mathematicians believe that Peano's axioms are consistent, relying either on intuition or the acceptance of a consistency proof such as Gentzen's proof. The small number of mathematicians who advocate ultrafinitism reject Peano's axioms because the axioms require an infinite set of natural numbers. In the philosophy of mathematics, ultrafinitism, or ultraintuitionism, is an extreme version of finitism. ...

See also

• Foundational status of arithmetic
• Gentzen's consistency proof
• General set theory
• Paris-Harrington theorem
• Presburger arithmetic
• Robinson arithmetic
• Second-order arithmetic
• Set-theoretic definition of natural numbers

Foundations of mathematics is a term sometimes used for certain fields of mathematics itself, namely for mathematical logic, axiomatic set theory, proof theory, model theory, and recursion theory. ... This article is in need of attention from an expert on the subject. ... General set theory (GST) is the name George Boolos (1998) employed for a three axiom fragment of the canonical axiomatic set theory ZF. // GST consists of a single primitive ontological notion, that of set, and a single ontological assumption, namely that all individuals in the universe of discourse (i. ... 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 is the first-order theory of the natural numbers with addition. ... In mathematics, Robinson arithmetic, or Q, is a fragment of the theory of the natural numbers, set out in R. M. Robinson (1950). ... In mathematical logic, second order arithmetic is a stronger version of Peano arithmetic that allows quantification over subsets of the integers, rather than just over integers. ... Several ways have been proposed to define the natural numbers using set theory. ...

References

• Martin Davis (1974) Computability: Notes by Barry Jacobs, The Courant Institute of Mathemaatical Sciences NYU, New York.
• R. Dedekind, 1888. Was sind und was sollen die Zahlen? (What are and what should the numbers be?). Braunschweig. Two English translations:
  • 1963 (1901). Essays on the Theory of Numbers. Beman, W. W., ed. and trans. Dover.
  • 1996. In From Kant to Hilbert: A Source Book in the Foundations of Mathematics, 2 vols, Ewald, William B., ed., Oxford University Press: 787–832.
• H. Grassmann, Lehrbuch der Arithmetik (A tutorial in arithmetics), Berlin 1861.
• William S. Hatcher, 1982. The Logical Foundations of Mathematics. Pergamon. A text on mathematical logic that carefully discusses the Peano axioms (called S), then derives them from several axiomatic systems of set theory.
• Jean van Heijenoort, ed. (1967, 1976 3rd printing with corrections). From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931, 3rd, Cambridge, Mass: Harvard University Press. ISBN 0-674-32449-8 (pbk.).  Contains the following two papers, each preceded with valuable commentary.
  • Richard Dedekind, Letter to Keferstein (1890) (van Heijenoort p. 98-103), in particular page 100 where he defines and defends his axioms of 1888.
  • G. Peano, Arithmetices principia, nova methodo exposita (The principles of arithmetic, presented by a new method), van Heijenoort p. 83-97, an excerpt of his treatise wherein Peano presents his axioms, and his definitions of e.g. multiplication and division.
• Richard Kaye (1991). Models of Peano arithmetic. Oxford University Press. ISBN 0-19-853213-X
• Patrick Suppes, 1972 (1960). Axiomatic Set Theory. Dover.
• Alfred Tarski, and Givant, Steven, 1987. A Formalization of Set Theory without Variables. AMS Colloquium Publications, vol. 41.

Martin Davis, (born 1926, New York City) is an American mathematician, known for his work on Hilberts tenth problem. ... Julius Wilhelm Richard Dedekind (October 6, 1831 - February 12, 1916) was a German mathematician and Ernst Eduard Kummers closest follower in arithmetic. ... Oxford University Press (OUP) is a highly-respected publishing house and a department of the University of Oxford in England. ... Hermann Günther Grassmann (April 15, 1809 - September 26, 1877) was a mathematician, physicist, linguist, scholar, and neohumanist. ... Jean van Heijenoort (prounounced highenort) (July 23, 1912, Creil France - March 29, 1986, Mexico City) was a pioneer historian of mathematical logic. ... Richard Dedekind Julius Wilhelm Richard Dedekind (October 6, 1831 – February 12, 1916) was a German mathematician who did important work in abstract algebra and the foundations of the real numbers. ... Giuseppe Peano (August 27, 1858 – April 20, 1932) was an Italian mathematician and philosopher. ... Patrick Colonel Suppes (b. ... // Alfred Tarski (January 14, 1902, Warsaw, Russian-ruled Poland – October 26, 1983, Berkeley, California) was a logician and mathematician who spent four decades as a professor of mathematics at the University of California, Berkeley. ...

External links

• Internet Encyclopedia of Philosophy: "Henri Poincare"--by Mauro Murzi. Includes a discussion of Poincaré's critique of the Peano's axioms.
• Lucas's comments
• First-order arithmetic, a chapter of a book on the incompleteness theorems by Karl Podnieks.
• Peano arithmetic on PlanetMath
• Eric W. Weisstein, Peano's Axioms at MathWorld.
• What are numbers, and what is their meaning?: Dedekind commentary on Dedekind's work, Stanley N. Burris, 2001.

This article incorporates material from PA on PlanetMath, which is licensed under the GFDL. The Internet Encyclopedia of Philosophy is an online encyclopedia on philosophical topics and philosophers founded by James Fieser in 1995. ... In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proved by Kurt Gödel in 1931. ... PlanetMath is a free, collaborative, online mathematics encyclopedia. ... Dr. Eric W. Weisstein Encyclopedist Dr. Eric W. Weisstein (born March 18, 1969, in Bloomington, Indiana) is a noted encyclopedist in several technical areas of science and mathematics. ... MathWorld is an online mathematics reference work, sponsored by Wolfram Research Inc. ... PlanetMath is a free, collaborative, online mathematics encyclopedia. ...