Peano Axioms

#REDIRECT Peano axioms

Peano axioms

In mathematics, the Peano axioms (or Peano postulates) are a set of first-order logic axioms proposed by Giuseppe Peano which determine the theory of Peano arithmetic (also known as first-order arithmetic). This theory constitutes a fundamental formalism for arithmetic, and the Peano axioms form a basis for the formalisation of stronger theories, such as second-order arithmetic. Using the Peano axioms, one can construct many of the most important number systems and structures of modern mathematics. Peano arithmetic raises a number of metamathematics and philosophy of mathematics issues, primarily involving questions of consistency proof and G�del's completeness theorem. ==The axioms== Informally, the Peano axioms may be stated as follows: *There is a natural number 0. *Every natural number ''a'' has a successor, denoted by ''S''(''a''). *There is no natural number whose successor is 0. *Distinct natural numbers have distinct successors: if ''a'' ≠ ''b'', then ''S''(''a'') ≠ ''S''(''b''). *If a property is possessed by 0 and also by the successor of every natural number which possesses it, then it is possessed by all natural numbers. (This axiom ensures that the proof technique of mathematical induction is valid.) More formally, we define a Dedekind-Peano structure to be an ordered triple (''X'', ''x'', ''f''), satisfying the following properties: *''X'' is a set, ''x'' is an element of ''X'', and ''f'' is a map from ''X'' to itself. *''x'' is not in the range of ''f''. *''f'' is injective. *If ''A'' is a subset of ''X'' satisfying: **''x'' is in ''A'', and **If ''a'' is in ''A'', then ''f''(''a'') is in ''A'' :then ''A'' = ''X''. The Peano axioms can be summed up by the following diagram: :

x\mapsto f(x)\mapsto f(f(x))\mapsto f(f(f(x)))\mapsto\dotsb

where each of the iterations ''f''(''x''), ''f''( ''f''(''x'') ), ''f''( ''f''( ''f''(''x'') ) ), ... of ''x'' under ''f'' are distinct. ==Existence and uniqueness== A standard construction in set theory shows the existence of a Dedekind-Peano structure. First, we define the ''successor function''; for any set ''a'', the ''successor'' of ''a'' is ''S''(''a'') := ''a'' ∪ {''a''}. A set ''A'' is an ''inductive set'' if it is closed under the successor function, i.e. whenever ''a'' is in ''A'', ''S''(''a'') is also in ''A''. We now define: *0 := empty set *N := the intersection of all inductive sets containing 0 *''S'' := the successor function restricted to N The set N is the set of natural numbers; it is sometimes denoted by the Greek letter ω, especially in the context of studying ordinal numbers. The axiom of infinity guarantees the existence of an inductive set, so the set N is well-defined. The ''natural number system'' (N, 0, ''S'') can be shown to satisfy the Peano axioms. Each natural number is then equal 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. This construction is due to John von Neumann. This is not the only possible construction of a Dedekind-Peano structure. For instance, if we assume the construction of the set N = {0, 1, 2,...} and successor function ''S'' above, we could also define ''X'' := {5, 6, 7,...}, ''x'' := 5, and ''f'' := successor function restricted to ''X''. Then this is also a Dedekind-Peano structure. :

5\mapsto6\mapsto7\mapsto8\mapsto\dotsb

The lambda calculus gives another construction of the natural numbers that satisfies the Peano axioms. Two Dedekind-Peano structures (''X'', ''x'', ''f'') and (''Y'', ''y'', ''g'') are said to be ''isomorphic'' if there is a bijection φ : ''X'' → ''Y'' such that φ(''x'') = ''y'' and φ''f'' = ''g''φ. It can be shown that any two Dedekind-Peano structures are isomorphic; in this sense, there is a "unique" Dedekind-Peano structure satisfying the Peano axioms. (See the categorical discussion below.) ==Binary operations and ordering== Addition, multiplication and the usual ordering can all be defined for the natural numbers N entirely in terms of the Peano axioms. One recursively defines an Addition in N by setting ''a'' + 0 = ''a'' and ''a'' + ''S''(''b'') = ''S''(''a'' + ''b'') for all ''a'', ''b''. This turns the natural numbers (N, +) into a commutative monoid with identity element 0, the so-called free object with one generator. This monoid satisfies the cancellation property and can therefore be embedded in a group (mathematics). The smallest group containing the natural numbers is the integer. Since ''S''(0) := 1, we have ''S''(''b'') = ''S''(''b'' + 0) = ''b'' + ''S''(0) = ''b'' + 1; i.e. the successor of ''b'' is simply ''b'' + 1. Analogously, given that addition has been defined, a multiplication * can be defined via ''a'' * 0 = 0 and ''a'' * (''b'' + 1) = (''a'' * ''b'') + ''a''. This turns (N, *) into a commutative monoid with identity element 1; addition and multiplication are compatible which is expressed in the distributivity: ''a'' * (''b'' + ''c'') = (''a'' * ''b'') + (''a'' * ''c''). For the remainder of the article, we write ''ab'' to indicate the product ''a'' * ''b''. Furthermore, one defines a total order on the natural numbers by writing ''a'' ≤ ''b'' if and only if there exists another natural number ''c'' with ''a'' + ''c'' = ''b''. This order is compatible with the arithmetical operations in the following sense: if ''a'', ''b'' and ''c'' are natural numbers and ''a'' ≤ ''b'', then ''a'' + ''c'' ≤ ''b'' + ''c'' and ''ac'' ≤ ''bc''. An important property of the set of natural numbers N is that it is well-order: every non-empty set of natural numbers has a least element. This property is also shared by every natural number ''n''. ==Categorical interpretation== The Peano axioms may be interpreted in the general context of category theory. Let US₁ be the category (mathematics) of pointed unary systems; i.e. US₁ is the following category: *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_US₁((''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''). This means 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 recursion. This concept can be generalised to arbitrary categories. Let ''C'' be a category with (unique) initial object 1, and let US₁(''C'') be the category of pointed unary systems in ''C''; i.e. US₁(''C'') is the following category: *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_US₁(''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 Category of sets. ==Metamathematical discussion== These axioms are given here in a second-order predicate calculus form. See first-order predicate calculus for a way to rephrase these axioms to be first-order. Dedekind proved, in his 1888 book [http://www.thoralf.uwaterloo.ca/htdocs/scav/dedek/dedek.html Was sind und was sollen die Zahlen], that any model of the second order Peano axioms is isomorphic to the natural numbers. On the other hand, the last axiom listed above, the mathematical induction axiom, is not itself expressible in the first order language of arithmetic. If one replaces the last axiom with the schema: :If

P(0)

is true; and for all

x

P(x)

implies

P(x + 1)

; then

P(x)

is true for all

x

. for each first order property

P(x)

(an infinite number of axioms) then although natural numbers satisfy these axioms, there are other, nonstandard models of arbitrarily large cardinality - by the compactness theorem the existence of infinite natural numbers cannot be excluded in any axiomatization; by an "upward L�wenheim-Skolem theorem", there exist models of all cardinalities. When the axioms were first proposed, people such as Bertrand Russell agreed 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 a proof can exist that starts from just these axioms, and derives a contradiction such as P AND (NOT P), then the axioms are inconsistent, and don't really define anything. David Hilbert posed a problem of proving consistency using only finite logic as one of the problems on Hilbert's problems. The motivation was to eliminate infinity, by justifying it with this proof, and show that it brings nothing new. But in 1931, Kurt G�del in his celebrated G�del's incompleteness theorem showed such a proof cannot exist. It is even impossible to prove consistency of Peano arithmetic while assuming the axioms themselves. Furthermore, we can never prove that any axiom system is consistent within the system itself, if it is at least as strong as Peano's axioms. In 1936, Gerhard Gentzen proved the consistency of Peano's axioms, using transfinite induction. All mathematicians assume that Peano arithmetic is consistent, although this relies on intuition only. However, early forms of na�ve set theory also intuitively looked consistent, before the inconsistencies were discovered. This has been a source of confusion for a number of people, especially nonmathematicians. The point is that we do have to rely on our intuition, and that it brings something new. Roger Penrose has argued that this intuition is what differentiates men from machines, but his arguments are dubious. The modern set theory often considers axioms postulating existence of large cardinals - none of them can be proved within set theory, nor is it possible to prove consistency of these axioms. But mathematicians generally do not exclude the possibility that some of these axiom systems are inconsistent. The intuition here is much less clear than in the case of natural numbers. Some people argue that even Peano arithmetic could be inconsistent - since intuition is not really a reliable source of truth. This argument can be extended and make us doubt even finite logic itself - these questions go back to Immanuel Kant and his famous ''Critique of Pure Reason''. Founding a mathematical system upon axioms, such as the above Peano axioms for natural numbers or axiomatic set theory or Euclidean geometry is sometimes labeled the axiomatic method or axiomatics. In axiomatic set theory, if one chooses to accept the axiom of choice, axiomatics allows such results as the Banach-Tarski paradox. This states that a ball can be dissected into five parts and re-assembled by Euclidean transformations into two balls of size equal to the original. A simpler approach to a mathematical system is found in Generating arithmetic. ==External links and references== * [http://dns.uncor.edu/info/raggio/03obra/logfm/logica/gentz50.htm Gentzen's proof] * [http://www.utm.edu/research/iep/p/poincare.htm Poincare's comments] * [http://www.leaderu.com/truth/2truth08.html Lucas's comments] * [http://www.ltn.lv/~podnieks/gt3.html First-order arithmetic], a chapter of a book on the incompleteness theorems by Karl Podnieks. Arithmetic

Peano axioms

Please add new topics to the end of the page. ==Older posts== I deleted this: :This was a proof using logic alone, but of course infinite. It gives an algorithm for simplifying a :possible proof of contradiction by a series of simple transformations, until it becomes very short. :To see that it becomes very short we need transfinite induction. Gentzen's proof has been :humorously called "assuming the dubious to prove the obvious". since (a) it was not a proof using 'infinite logic' but a straightforward mathematical proof; (b) the procedure makes the proofs longer, not shorter; (c) whoever called the proof that doesn't understand it. ----- Someone was getting confused about Peano's axioms vs. first order Peano Arithmetic. I(different I than the above: this I's a PhD student who's area is models of PA) changed

Although natural numbers satisfy these axioms, there are other, nonstandard models of arbitrary large cardinality - by Compactness theorem the existence of infinite natural numbers cannot be excluded in any axiomatization.

Dedekind proved, in his 1888 book [http://www.thoralf.uwaterloo.ca/htdocs/scav/dedek/dedek.html Was sind und was sollen die Zahlen], that any model of the second order Peano axioms is isomorphic to the natural numbers. On the other hand, the last axiom listed above, the mathematical induction axiom, is not itself expressible in the first order language of arithmetic. If one replaces the last axiom with the schema:
#If P(0) is true and for all n P(x) implies P(x+1)
for each first order property P(x) (an infinite number of axioms) then although natural numbers satisfy these axioms, there are other, nonstandard models of arbitrary large cardinality - by the Compactness theorem the existence of infinite natural numbers cannot be excluded in any axiomatization; by the Lowenheim-Skolem theorem there exist models of all cardinalities.

:Thanks for the clear-up and help! User:Revolver 07:04, 30 Sep 2004 (UTC) ---- Presumably "For all n, P(x) implies P(x+1)" really means: ::"For all ''x'', P(''x'') implies P(''x'' + 1)." User:Michael Hardy 00:07, 25 Oct 2003 (UTC) ==Peano system== Why is the name Peano system used in the article? The criteria are due to Dedekind. ---- User:Chalst 11:30, 29 Sep 2004 (UTC) :This is the term that I seem to remember hearing/reading most often. You can certainly check the literature and see if you find Dedekind system to be more standard. Whether the criteria are due to Dedekind is worth noting for historical reasons but not really related to current standard usage — we all know how many things in math '''aren't''' named after the proper person. User:Revolver 07:04, 30 Sep 2004 (UTC) ::No doubt you are right, I think that the structure is normally given an ad hoc name such as "numerical structure"; I don't think there is a standard name for it, but I think the name Peano system is doubly unfortunate, because, besides the historical point, one usually uses the term "structure" to talk about these things and not system. ::FWIW, Google tells me that "Peano system" is not much used, 180 hits, the most common being for a Perl ORB on freshmeat, and most of the relevant links referrring to Peano'x axioms and not the number structure. ---- User:Chalst 12:14, 30 Sep 2004 (UTC) :::I can do a check of several set theory books over the next week or so, just as an initial look. I'm not sure how to interpret the google quote you give (180 hits) without comparison to an alternative (how many hits does "___" get?) User:Revolver 08:25, 1 Oct 2004 (UTC) :::"Numerical structure" got about 1600 hits, but the very FIRST hit is some religious numerology babble, so I take these google hit-numbers with a few grains of salt. User:Revolver 08:31, 1 Oct 2004 (UTC) ::`Meaning' of 180 hits: the structure is obviously very fundamental, so 180 hits is low, especially since Wikipedia has quite a few syndicates. By comparison "Hopf algebra" gets 12700 hits, despite being an obviously less fundamental concept. I think there is no standard way of talking about this structure; given this, it looks to me that we should call the structure something non-misleading. Dedekind structure, gets only one relevant hit, but it is for exactly this item, and it is what I would call it. ---- User:Chalst 12:09, 1 Oct 2004 (UTC) :::It may be more "fundamental" in the foundational sense, but my guess is that more people study Hopf algebras than Dedekind structures. There does seem to be no standard terminology. I googled "Peano structure" and found at least half a dozen relevant hits. I admit I have no real knowledge on the history of the situation. Since both "Dedekind" and "Peano" seem to be in use, why not use "Dedekind-Peano structure" (which I have seen), and make some comments about other terminology? Note: I have also seen "Dedekind-Peano axioms" for "Peano axioms". User:Revolver 01:30, 3 Oct 2004 (UTC) ::I'd guess the structure of positive integers sees as much study and more application than Hopf Algebras; however everytime you see a Hopf algebra applied you will see the fact advertised using the standard name. I have no objection to Dedekind-Peano structure. I think the name Dedekind-Peano axioms is generally used for second-order Peano arithmetic, but saying "second-order Peano axioms" I think is more suggestive. Should we add a terminology section? ---- User:Chalst 09:27, 3 Oct 2004 (UTC) == first order? == The article claims that "Peano axioms (or Peano postulates) are a set of first-order axioms" can someone please tell how is it possible to postulate: "if a property is possessed by 0 and also by the successor of every natural number which possesses it, then it is possessed by all natural numbers." in a first order logic? i think you will have two use second order for that claim.(it seems to quantify over properties(definition of second order logic)) :(post moved to bottom of page) :As an axiom, induction is second-order. However it can be formulated in a first-order manner by adding not a single axiom, but an axiom schema with infinitely many instances. Since the schema defines a(primitive) recursive set, from the point of view of proof theory, it is acceptable. ---- User:Chalst 07:46, 26 Jan 2005 (UTC) ::I see, for example we can get around induction by using no-cycles claim, (no size 1 cycle, no size 2 cycle..etc up to infinity).Still, In this case the text of the artcile should be changed to this particular(infinitary) axiomatization, because as it stands it is confusing as to why is it first-order.--User:Hq3473 08:02, 26 Jan 2005 (UTC) :If I'm not mistakened, forbidding cycles is both too weak and can't be captured by a first-order axiomatisation. I agree the text needs (much) improvement, but I guess the issue won't be clear until we give an actual axiomatisation in a Hilbert-style proof theory - then we can talk about this point properly. I'll put it on my overburdened to do list ---- User:Chalst 10:22, 26 Jan 2005 (UTC) ::i see, cycles will not rule out higher orders. Any way, can you maybe give me link or a refernce to riogorous first order peano axiomatization? i want to see how is the deduction overcome.--User:Hq3473 21:44, 26 Jan 2005 (UTC)

See other meanings of words starting from letter:

P

PA | PB | PC | PD | PE | PF | PG | PH | PI | PJ | PK | PL | PM | PN | PO | PR | PS | PT | PU | PW | PX | PY | PZ |

Words begining with Peano_axioms:

Peano_Axioms
Peano_axioms
Peano_axioms