Peano’s Axioms and Natural Numbers

1 CONSTRUCTION OF number SYSTEMSN. MOHAN s Axioms and Natural NumbersWe start with the Axioms of s a set with the following properties.(1)Nhas a distinguished element which we call 1 .(2)There exists a distinguished set map :N N.(3) is one-to-one (injective).(4)There does not exist an elementn Nsuch that (n) = 1. (So,in particular is not surjective).(5)(Principle of Induction) LetS Nsuch that a)1 Sand b)ifn S, then (n) S. ThenS= call such a setNto be the set of Natural Numbers and elementsof this set to be Natural Nandn6= 1, then there existsm Nsuch that (m) = the subsetSofNdefined as,S={n N|n= 1 orn= (m),for somem N}.By definition, 1 S. Ifn S, clearly (n) S, again by definitionofS. Thus by the Principle of Induction, we see thatS=N. Thisproves the lemma. We define the operation of addition (denoted by +) by the followingtwo recursive rules.(1) For alln N,n+ 1 = (n).(2) For anyn,m N,n+ (m) = (n+m).Notice that by lemma , any Natural number is either 1 or of theform (m) for somem Nand thus the defintion of addition abovedoes define it for any two Natural numbersn, we define multiplication onN(denoted by , or sometimesby just writing letters adjacent to each other, as usual) by the followingtwo recursive rules.

2 (1) For alln N,n 1 = MOHAN KUMAR(2) For anyn,m N,n (m) =n m+ , lemma assures that this defines multiplication of any twonatural Numbers . To get a feel for how we identify this setNas ourusual number system, let meprovesome of the properties we are fa-miliar with. Remember, we may use only the Axioms , definitions andwhatever we have proved before to prove the successive principle should be rigidly adhered to follow our rules of (Associativity).Ifx,y,z N, thenx+(y+z) = (x+y)+ before let us define a subset ofNas {z N| x,y N, x+ (y+z) = (x+y) +z}To prove the lemma, we must show thatS=Nand again we plan touse the Principle of Induction. To apply the Principle, we must checktwo things and we will check them 1: 1 anyx,y N, we have,x+ (y+ 1) =x+ (y) (by definition of addition)= (x+y) (by definition of addition)= (x+y) + 1 (by definition of addition)Thus we get 1 2: Ifz S, then (z) anyx,y N, we havex+ (y+ (z)) =x+ (y+z) (by definition of addition)= (x+ (y+z)) (by definition of addition)= ((x+y) +z) (sincez S)= (x+y) + (z) (by definition of addition)This proves the lemma.

3 Lemma (commutativity of addition).For anyx,y N,x+y=y+ always we start with a {y N| x N, x+y=y+x}To use induction, we need to check two things. Of course, if we showS=N, we would have proved the 1: 1 this we define a new subsetTofNas {x N|x+ 1 = 1 +x}We apply induction to this OF number SYSTEMS3 Step a): Clearly 1 T, since 1 + 1 = 1 + b): Assumex T. Then1 + (x) = (1 +x) (by definition of addition)= (x+ 1) (sincex T)= ( (x)) (by definition of addition)= (x) + 1 (by definition of addition)Thus we see thatT=N. Going back, we see that this implies 1 2: Ify S, then (y) + (y) =x+ (y+ 1) (by definition of addition)= (x+y) + 1 (by associativity, proved before)= (y+x) + 1 (sincey S)= 1 + (y+x) (since 1 S)= (1 +y) +x(by associativity)= (y+ 1) +x(since 1 S)= (y) +x(by definition of addition) The correct order to prove some of the remaining properties ofNafter the above is the following. (There may be other possibilities, butat least this order will work).

4 (1) (Cancellative law) For anyx,y,z N, ifx+z=y+z, thenx=y.(2) (Distributive law) Ifx,y,z Nthenx (y+z) =x y+x zand (y+z) x=y x+z x.(3) (Associative law for multiplication ) For anyx,y,z N,x(yz) =(xy)z.(4) For anyx N, 1 x=x.(5) (commutative law for multiplication ) For anyx,y N,xy= me prove the distributive law now. We will only prove one of (Distributive law).For allx,y,z N,x(y+z) =xy+ , letS={z N|x(y+z) =xy+xz, x,y N}Step 1: 1 (y+ 1) =x (y) (by definition of addition)=xy+x(by definition of multiplication )=xy+x 1 (by definition of multiplication )4N. MOHAN KUMARStep 2: Ifz S, then (z) (y+ (z)) =x (y+z) (by definition of addition)=x(y+z) +x(by definition of multiplication )= (xy+xz) +x(sincez S)=xy+ (xz+x) (by associativity of addition)=xy+x (z) (by definition of multiplication )Thus by Induction,S=Nand we have proved the lemma. the remaining properties stated above. Remember,you may use anything proved earlier for a proof, but no later propertymay be used in the we introduce the ordering ,m N, we say thatnis less thanm, writtenn < m,if there exists ak Nsuch thatm=n+k.

5 We also writen m, readnis less than or equal tom, to mean that eithern=morn < ,y,z Nandx < yandy < zthenx < assumptionx < ymeansy=x+kfor somek we getz=y+lfor somel N. Thus, we get,z=y+l= (x+k) +l=x+ (k+l) (by associativity)Thus by definitionx < zsincek+l N. The same argument can be used to show the ,y,z N.(1)Ifx yandy < z, thenx < z.(2)Ifx < yandy z, thenx < z.(3)Ifx yandy z, thenx ,y,z Nandx < yshow thatx+z < y+zandxz < anym N,m6=m+ usual define a subsetS Nas follows:S={n N|n6=n+ 1}Clearly, 1 S, since if not, 1 = 1+1 = (1), by definition of additionand 16= (k) for anyk Nby Peano s Axioms ( number 4).CONSTRUCTION OF number SYSTEMS5 Assumen S. If (n) is not inS, then (n) = (n) + 1. Thenby definition of addition, (n) = ( (n)). By the third axiom , thismeans,n= (n) which in turn isn+ 1 by definition of addition. Thisis impossible sincen S. Lemma anym,k N,m6=m+ define a subsetS Nas follows:S={k N| m N,m6=m+k}From the previous lemma, we see that 1 S.

6 Ifk S, we want toshow that (k) Sand then by induction we would be done. Thatis, we want to show thatm6=m+ (k) for anym. Notice thatm+ (k) = (m+k), by definition of us define a subsetTas follows:T={m N|m6= (m+k)}Clearly 1 Tby axiom 4. Assumem T. Want to show that (m) T. If (m) = ( (m) +k), by axiom 3, we see thatm= (m) +k. Thus we have,m= (m) +k= (m+ 1) +k(by definition of addition)=m+ (1 +k) (by associativity)=m+ (k+ 1) (by commutativity)=m+ (k) (by definition of addition)= (m+k) (by definition of addition)But this contradicts our assumption thatm T. Lemma (Well ordering ofN).Ifn,m N, then exactly one of thefollowing is true. Eithern < morn=morm < us first prove only one of these can hold. Ifn < m, then bydefinition,m=n+kfor some elementk N. By the previous lemma,we see thatm6=n. Ifm < n, then there exists anl Nsuch thatn=m+lwhich impliesm= (m+l) +k=m+ (l+k) which againis not possible by the previous lemma. The other cases are similar andleft as an finish the proof we consider the setS, fixing {m N|n < m,n=morm < n}Step 1: 1 MOHAN KUMARIfn= 1, clearly 1 S.

7 Ifn6= 1, then by lemma ,n= (k) =k+ 1 = 1 +kand thus by definition of our ordering, 1< 2: Ifm Sthen (m) S. This means we have three possibilities, namelyn < morn=morm < n. First, let us look at the casen < +kfor somek. Thus (m) = (n+k) =n+ (k) andson < (m) and hence (m) S. Next possibility isn=m. Then (m) =m+1 =n+1 and thusn < (m) and again (m) S. Finally,we have the possibility ofm < n. Thusn=m+kfor some elementk N. Ifk= 1, thenn= (m) and thus (m) S. If not, by ,k= (l) and thusn=m+ (l) and thus,n=m+ (l)m+ (l+ 1) (by definition of addition)=m+ (1 +l) (by commutativity)= (m+ 1) +l(by associativity)= (m) +l(by definition of addition).Therefore (m)< nby definition of our ordering and thus (m) in any case (m) S. Therefore by induction,S=Nand we aredone. usual, we will writem > n, readmis greater thanntomeann < m. Similarl meaning is assigned tom I want to prove some alternate forms of induction which arefrequently used. We start with a N.

8 Then an elementn Sis called a leastelement if for anym S,n N. IfShas a least element, then it is it makes sense to use the definite article the instead of a if a leastelement exists and call it the least element . two least elements, saynandm. Thus we seethatn mandm n. From the well ordering lemma, it is clear thatn=m. Theorem (First alternate form of Induction).IfS NandS6= thenShas a least usual letT={n N|ifn S N,thenShas a least element}CONSTRUCTION OF number SYSTEMS7 Caution:HereTis a fixed set defined as above. But,Sis a variablesubset will leave it as an exercise to check that 1 T. Next assumethatn Tand we want to show that (n) T. So letS Nwith (n) S. Ifn S, then by hypothesis, we know thatShas a leastelement. So assume thatnis not inSand considerA=S {n}. Thenn Aand thusAhas a least element by hypothesis. Let us call thisleast are two possibilities. Eithera=nora6=n. Ifa6=n, thena S. Ifm S, then clearlym Aand thusa m.

9 So we see thata Sis a least assumea=n. Then I claim that (n) is the least elemnt ofS. Ifm S, we know thata=n m. Butn6 Sand thusn6= by definition of less than or equal to, we see thatn < m. Thuswe may writem=n+kfor somek Nby defintion. Ifk= 1, thenm=n+ 1 = (n). Ifk6= 1, then by the first lemma,k= (l) for somel N. Thusm=n+ (l+ 1) =n+ (1 +l) = (n+ 1) +l= (n) +land thus (n)< m. Thus we see that (n) is a least element ofSandwe are done. Some of you may be more familiar with the following form of induc-tion, though all the three are (Second alternate form of Induction).LetP(n)be math-ematical statements forn N. Assume(1)P(1)is true.(2)IfP(n)is true, thenP(n+ 1)is (n)is true for alln a setS={n N|P(n) is false}. We wish to show thatS= . If non-empty, by the previous form of induction,Theorem ,we have a least elementm S. By the first hypothesis of the theorem,m6= 1. Thenm=p+ 1 for somep N. Sincep < mandmbeingthe least elelement ofS, we know thatp6 Sand thusP(p) is true bydefinition of the setS.

10 Now, by our second hypothesis,P(p+1) =P(m)is true and hencem6 S, a contradiction, proving the result. Theorem (Third alternate form of Induction).LetP(n)be math-ematical statements fosn N. Asuume,(1)P(1)is true.(2)Ifn >1andP(k)is true for allk < n, thenP(n)is MOHAN KUMARThenP(n)is true for before, letS={n N|P(n) is false}and we wish to showthatS= . So assume that it is non-empty and letm Sbe theleast element assured by Theroem Again, as before, by the firsthypothesis, 16 Sand thusm >1. By minimality ofm, ifk < m, thenk6 Sand henceP(k) is true. Thus by second hypothesisP(m) is trueand thusm6 S, which is a contradiction, proving the theorem. We will use these forms in the next section on number Theory toprove results familiar to you. We state some more properties of naturalnumbers, which can be proved using the above ordering properties ofN.(1) (cancellative law for multiplication ) For anyx,y,z N, ifxz=yzthenx=y.(2) (uniqueness of identity) For somex,y N, ifxy=x, theny= this point, we will use our usual nomenclature for naturalnumber.