Peano Axioms

Please download to get full document.

View again

of 31
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report



Views: 13 | Pages: 31

Extension: PDF | Download: 0

Related documents
Peano Axioms
  CHAPTER 1: THE PEANO AXIOMS MATH 378, CSUSM. SPRING 2009. AITKEN 1.  Introduction We begin our exploration of number systems with the most basic numbersystem: the natural numbers N . Informally, natural numbers are just the or-dinary whole numbers 0 , 1 , 2 ,...  starting with 0 and continuing indefinitely. 1 For a formal description, see the axiom system presented in the next section.Throughout your life you have acquired a substantial amount of knowl-edge about these numbers, but do you know the reasons behind your knowl-edge? Why is addition commutative? Why is multiplication associative?Why does the distributive law hold? Why is it that when you count a finiteset you get the same answer regardless of the order in which you count theelements? In this and following chapters we will systematically prove basicfacts about the natural numbers in an effort to answer these kinds of ques-tions. Sometimes we will encounter more than one answer, each yieldingits own insights. You might see an informal explanation and then a for-mal explanation, or perhaps you will see more than one formal explanation.For instance, there will be a proof for the commutative law of addition inChapter 1 using induction, and then a more insightful proof in Chapter 2involving the counting of finite sets.We will use the axiomatic method where we start with a few axiomsand build up the theory of the number systems by proving that each newresult follows from earlier results. In the first few chapters of these notesthere will be a strong temptation to use unproved facts about arithmeticand numbers that are so familiar to us that they are practically part of ourmental DNA. Resist this temptation! In the context of a formal proof, takethe attitude that such familiar facts are not certain until they are proved.So they cannot be used in a formal proof until after they have been proved.A similar thing can be said of definitions: pretend that your intuitive ideasof even basic things such as + and  <  are inaccessible until you can havea formal definition. In the beginning, the only terms that can be used areterms from logic and set theory, explained in Chapter 0, and the primitiveterms. The only facts that can be used are the axioms together with facts Date  : May 19, 2009. 1 Warning: some authors do not include 0 in the set of natural numbers. This will bediscussed in the next section. 1  2 MATH 378, CSUSM. SPRING 2009. AITKEN from logic and set theory as summarized in Chapter 0, including generalfacts about equality, functions, and relations. 2 The system of axioms we use here is a famous system called the  Dedekind-Peano axioms   (Section 2), or the  Peano axioms   for short. We will add to thisan axiom about iterating functions (Section 3), but in an optional section(Section 12) to this chapter, we will see that this iteration axiom is notnecessary since it can actually be proved from Peano’s axioms. Thus it isstrictly speaking a convenient “temporary” axiom: one could replace theiteration axiom by a theorem that says the same thing. We take it as atemporary axiom in these notes since the proof of the iteration axiom is abit subtle, and is at a higher level than most of the other theorems of theChapter. I do not want to start off the chapter by scaring away readers. Remark   1 .  Although we will be strict about not using unproved assertions inthe formal development, you do not need to be so shy about using your priorknowledge in the  informal   exercises. Such prior knowledge is also useful fortemporarily guiding your thinking until a firmer foundation is laid down inthe formal development.This distinction between formal and informal is especially important inthe many exercises that will arise in these notes. The informal exercises willbe labeled as such. The rest are considered to be formal exercises.The formal exercises may require you to fill in details of sketchy proofsor even to write complete proofs for theorems whose proofs are not toohard or are similar to earlier proofs. These constitute part of the officialdevelopment of the number systems, and the facts established in them canbe used in future proofs. On the other hand, the informal exercises aredesigned to help familiarize you with facts or definitions, or to lead you ininteresting but tangential directions. These do not have to be solved witha formal proof, and can appeal to prior knowledge. They are considered tobe outside the logical development of the number systems, and so cannot becited in a later formal proof.For example, suppose an informal exercise asks for an example of anassociative binary operation that his not commutative. Suppose you knowabout matrix multiplication from a linear algebra course. Then you canuse your knowledge of linear algebra to help solve the problem. On theother hand, you cannot use matrix multiplication in a formal exercise sincematrices are not developed in this course. Remark   2 .  In the above discussion, the term  theorem   refers to any resultthat has a proof. Keep in mind that other terms for theorems are commonlyused including  proposition  ,  lemma  , and  corollary  . The term  lemma   is used 2 In these notes, we start almost at the very beginning of mathematics, but you should beaware that there are other approaches that start with less and begin by proving theoremsabout set theory first before developing the number systems. For example, set theoriststypically start with the Zermelo-Fraenkel axioms for set theory, and from there developset theory, the number systems, and (most of) the rest of mathematics.  CHAPTER 1: THE PEANO AXIOMS 3 for a theorem that is only important as a stepping stone in proving othertheorems, and a  corollary   is a theorem that follows fairly easily, for exampleas an interesting special case, from a previous theorem. Some authors alsomake a distinction between the terms  theorem   and  proposition  , using thelabel  proposition   for more ordinary theorems and using  theorem   only forthe more important theorems. These are informal guidelines: one can findexceptions. Remark   3 .  As mentioned above, in the formal development of the naturalnumbers we begin by assuming that everything about the natural numbersis as yet unknown territory. On the other hand, we do allow logic as ex-pressed in everyday, but careful, language. This leads to a point that needsto be clarified: even though we are developing the natural numbers fromscratch, we will allow ourselves to use a few number-related terms such as“pair”, “unique”, “first”, “second”, and so on. We do so because we cansafely treat such basic terms as forming part of our  logical   vocabulary. 3 Wewill also use numerals for the labeling of sections, theorems, exercises, andsuch. These labels have no arithmetic content, and could have just as easilybeen any string of symbols. They are being used informally to help keep thechapter organized. On the other hand, we will not take any truly mathe-matical or arithmetic fact for granted, for example facts about addition andmultiplication. These all must be proved.2.  The Axioms Forget everything you think you know about the natural numbers, evensomething as basic as 1+1 = 2. Pretend you don’t even know the definitionof addition. In what follows, we will recreate all this knowledge on a solidlogical foundation by  proving   all the elementary theorems and  definining   allthe basic ideas. (Of course this self-imposed forgetting should be confinedto the official formal development of the natural numbers, and the formalproofs. Your past knowledge will come in handy for thinking up strategiesfor proofs, for helping you mentally digest definitions, and for warning youwhen you are about to make an error.)At this point, the only thing that you are officially allowed to know con-cerning the natural numbers is what is expressed in the following axioms.They function partially as descriptions of the primitive terms, and partiallyas a list of facts that we can use in later proofs. These axioms are called 3 For example, the statement “the set  S   has at least two elements” does not reallyrequire the number 2. It can be translated easily into basic logic as follows: ∃ x ∃ y “ ( x  ∈  S  )  ∧  ( y  ∈  S  )  ∧  ( x   =  y ) ” .  4 MATH 378, CSUSM. SPRING 2009. AITKEN the  Dedekind-Peano axioms   since they are based on the axioms of the Ger-man mathematician Richard Dedekind (1831 – 1916) and the the Italianmathematician Giuseppe Peano (1858 – 1932). 4 We begin with the primitive terms described in the axioms. They arecalled  primitive   because they do not have to be formally defined, but insteadare described in the axioms. All other terms, such as + or  <  must be defined.Such definitions can build on primitive terms, notions from Chapter 0, orany previously defined term. Primitive Terms.  The three primitive terms are   N ,  0 , and   σ . Axiom 1.  (i)  N  is a set, (ii)  0  is an element of   N , and (iii)  σ  is a function  σ  : N → N  with domain and codomain equal to  N . We call  N  the “set of natural numbers”, and we call its elements “naturalnumbers”. We call 0 the “zero element”, or just “zero”. We call  σ  the“successor function”. If   n  ∈  N  we call  σn  the “successor of   n .” Informally,the successor of   n  is the next number following  n . This is informal since wehave not yet defined an order  <  on  N . Axiom 2.  The image of   σ  : N → N  does not contain   0 : ¬  ∃  n  ∈ N . σn  = 0  In other words,  0  is not the successor of a natural number. Axiom 3.  The function   σ  :  N  →  N  is injective. 5 In other words, distinct natural numbers have distinct successors. ∀  x,y  ∈ N . x   =  y  = ⇒  σx   =  σy or equivalently  ∀  x,y  ∈ N . σx  =  σy  = ⇒  x  =  y. Axiom 4  ( Induction ) .  Suppose   S   is a subset of   N  such that   (i)  0  ∈  S  ,and   (ii)  n  ∈  S   implies   σn  ∈  S   for arbitrary   n  ∈ N . Then   S   = N . S   ⊆ N  ∧  0  ∈  S   ∧  ∀ n  ( n  ∈  S   ⇒  σn  ∈  S  )   = ⇒  S   = N 4 There are several variations of these axioms. We use a version of what is sometimescalled the  second-order Peano axioms   which allows the notion of subsets of   N . Thereis another, more elementary system called the  first-order   Peano axioms which does notquantify over sets of natural numbers. If you encounter the Peano axioms outside thesenotes, you might see the first order version with axioms that refer directly to addition andmultiplication. In our second-order version the operations of addition and multiplicationare not mentioned in the axioms, but must be defined in terms of the successor function. 5 The reader is expected to be familiar with the term  injective  , or the equivalentterm  one-to-one  . These terms describe functions  f   that map distinct elements to dis-tinct images.
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks