; TeX output 1995.11.06:1344;'nMdMW&XQ cmr12KAPITELISI}-Nff cmbx12Nats3UurlicheffZahlen-qB,N cmbx121.Dienat`urlichenZahlenc cunddievollstandigeInduktion:Wie amAnfangderMengenlehreeineaxiomatiscrheEinfSyuhrungstand,ȌsosollenjetztdienatSyurlicrhenZahlenaxiomatischein-gefSyuhrtwrerden.DabSeistehtderProzedesgewyohnlichenZyah-lens^RzunyacrhstimVVordergrund.^DieheuteyublicheBegrSyundungderplnatSyurlicrhenZahlenbasiertaufAxiomen,pdievonPeano1889vreryo entlicht6wurden,7OdieabSeraucrhDedekind1888schonbSe-kXannrtwaren.JWirwrerdeneinigeeinfacheEigenschaftendernatSyurlichenZahleninderfolgendenDe nitionfestlegen.ADabSeiwrerdenwirneben-einanderi]einemathematiscrhpryaziseFVormulierung,i~diewirinderSpracrhederMengenlehregebSenkyonnen, unddieumgangssprach-licrheFVormulierungdergewSyunschtenEigenschaftenfSyurnatSyurlicheZahlen angebSen.FDieseEigenscrhaftennenntmanauchdiePeano-Axiome.DiexExistenzeinzelnernatSyurlicrherZahlen(z.B.zweioSderdrei)istin denlogiscrhenGrundlagen,diewirhierverwenden,enthalten,wreilmaneinzelneObjektenebSeneinanderstellenkXannundsienK`y cmr1059<*'nMR60}hIGI.UUNA*T@fURLICHEZAHLENd&Mdamit 1abzyahlenkXann. :DieExistenzder4@ cmti12MengeRallernat'yurlichenZahlen5istdadurcrhjedoSchnichtgegebSen.wDasistnyamlicheineMengeqmitunendlicrhvielenElementen.vWirwissenbishernichteinmal,obesVyubSerhauptirgendeineMengemitunendlicrhvielenElemenrten͚gibt.DahermSyussenwirdieExistenzderMengeal-lerېnatSyurlicrhenZahlenzusyatzlichdurcheinmengentheoretischesAxiomfordern.Das\RecrhnenmitnatSyurlichenZahlenisteinwesentlichkomplexe-rer(VVorgang.Bevrorwir>yubSerhauptdieAdditionvonnatSyurlichenZahleneinfSyuhrenkyonnen,ݖwraserstimAbschnitt3geschehenwird,I=mSyussenI%wirstarkreHilfsmittelyubSerRekursionundInduk-tionbSereitstellen.De nition1.1.sEin*TVripSel( msbm10N'g cmmi12;1;)*bestehendauseinerMengeN,einemNElemenrt1Ta(!", cmsy102NNundeinerAbbildungTa:N !N,genannrtNachfolgerfunktion,heit(eine)MengeADdernat'yurlichenZahlen,PwrenndiefolgendenAxiomeerfSyulltsind:!(P1)=1UR2N,(*"g1isteinenatSyurlicrheZahl-l\Ҕ),!(P2)=w:N [!N+@isteineAbbildung,+(*"gjedenatSyurlicrheZahl=bSesitzteineneindeutigbestimmrtenNachfolger-l\Ҕ),!(P3)=8nI2N[(n)6=1],B(*"g1AistkreinNachfolgereinernatSyur-=licrhenZahl-l\Ҕ),!(P4)=wistinjektiv,(*"gnatSyurlicrheZahlenmitgleichenNachfol-=gernsindgleicrh-l\Ҕ),!(P5)=(PrinzipdervrollstyandigenInduktion)Q8E iURN[(12E^^8n2E[(n)2E])=)E i=N];=(*"geine {Eigenscrhaft, dieder1zukommtundmiteinerbSe-=liebigen/natSyurlicrhenZahlauchihremNachfolger,/kommt=allennatSyurlicrhenZahlenzu-l\Ҕ).WirescrhreibSenmitderNachfolgerfunktionundn 2Nehyau gn+1UR:=(n):='nMRoܠ1.UUDIENA*T@fURLICHENZAHLENKȤ61d&MAxiom6.U%(ExistenzderMengedernatSyurlicrhenZahlen)EsexistierteineMengedernatSyurlicrhenZahlen(N;1;).&KtWiewicrhtigdieFVorderungnachderExistenzeinerMengedernatSyurlicrhengZahlenist,hersiehtmanausdemfolgendenSatz.hNurwrennXXeseineMengedernatSyurlichenZahlengibt,XtkXannesyubSer-hauptaucrhandereunendlicheMengengebSen.KDieMengedernatSyurlicrhenZahlenkXannmanalsdenkleinstenPrototypeinerunendlicrhen wMengeau assen. WVeiterkXannmaninjederunend-licrhenMengeeinMoSdellfyureineMengevronnatyurlicrhenZahlen nden.֓Wir֎erinnernnoScrheinmalanunsereDe nitioneinerun-endlicrhenfMengeM(Kap.I.2.29undKap.I.2.31).fEsmuzuihreine(Selbst-)Abbildungt:M 1!MԈgebSen,dieinjektivabernicrhtsurjektivist.ZumBewreisdesfolgendenSatzesbSenyotigenwirzunyachsteinLemma.OLemma1.2.cOSeienMEeineMenge,ٍ:Mq o!MeineA2bbil-dung?Sundmk2M7ein?SElement.?VDanngibtesinMeinekleinsteTeilmenge35Ntmit(N@)URNund35m2N@.&5- cmcsc10Beweis.XWir.bSetracrhtendieMenge#%n eufm10MallerTVeilmengenAM@,fSyur(diegilt(A)"A(undm"2A.Diese(Mengeenrthyaltsicrherlichk4MalsElemenrt.kUNunbildenwirdenDurchschnittžyubSerallesogefundenenTVeilmengenߍ`!N6:=URu cmex10\qfAURM@j(A)A;m2Ag:O enrbaristdannmR2N@.FSyurn2NeistninallengenannrtenTVeilmengenAenrthalten,alsoauch(n).Damitistauch(n)o2N@.NAist]daherdiekleinsteTVeilmengevronMmitm`2Nund(N@)URN.InsbSesondere8istdiesekleinsteTVeilmengeNyinMmit(N@)URNundmUR2N+eindeutigbSestimmrt. yff٘ ̍ ff ̄ ffffff٘>'nMR62}hIGI.UUNA*T@fURLICHEZAHLENd&MMankXannsicrhdiesekleinsteTVeilmengeNPinMvrorstellenalsdieMengederElemenrte,diemanausmdurchbSeliebighyau geAn-wrendung6/vonerhyalt,6CalsodieMengefm;(m);((m));:::ʜg.Leider istesrecrht schwierig, dieseMengeformalrichtiganzu-gebSen,M;dashalbLhabenwirdenunanscrhaulichen,M;abSermathe-matiscrh&bSequemenWVegderDurchschnittsbildungeingeschlagen.Wir [wrerdendieseMothoSdebeidenalgebraiscrhenStruktureninKapitel4hyau gvrerwenden. Satz1.3.QDie35folgendenA2ussagensindyaquivalent:;)ו(1)=Es35existierteineMengedernat'yurlichenZahlen.)ו(2)=Es35existierteineunendlicheMenge.&Beweis.XWVennHeseineMengedernatSyurlicrhenZahlen(N;1;)gibt,^so^istnacrh(P4)injektivundnach(P3)nichtsurjektiv.AlsoistNeineunendlicrheMenge.Sei.LumgekrehrtMo0eineunendlicheMengeundeineinjektiveundunicrhtsurjektiveAbbildungvonMinM@.uDanngibteseinElemenrt$Kml2M@,$YdasnicrhtimBildvonliegt.$YWirbSetrachtenjetztFdiekleinsteTVeilmengeN6URM*mit(N@)N*undm2N@.Sei"*#:h\N@ !NcdieEinscrhryankungvonaufdieTVeilmengeN@.;Wir7zeigen,dafSyur(N;m;)diePreano-AxiomeerfSyulltsind.O enrbarhist*alsEinschryankungvonwiederinjektiv,iundesgilth 8nUR2N@[(n)6=m],h/damnicrhtimBildvonliegt.h/EsbleibtnrurJdieGSyultigkeitdesPrinzipsdervollstyandigenInduktionfSyur(N;m;)C9zuzeigen.COIstE)Nmitm2EPund8n2E[(n)2E],danngiltfSyurEaucrhdieBedingung(E)UEbzw.(E)E.uWVeilON3diekleinstesolcrheMengeistundE UNgilt,ufolgtE=N@.0Damit0istdieGSyultigkreitdesPrinzipsdervollstyandigenInduktion(P5)bSewiesen. yff٘ ̍ ff ̄ ffffff٘"O,DieKonstruktioneinerMengedernatSyurlicrhenZahlenineinerbSeliebigenGunendlicrhenMengekXannzurecht՞yubSerraschendenBei-spielen,fSyuhren.]DieAbbildungf:R2|{Ycmr8+ z3x7!x22+-12R2+ ǤvrondenEpSositivrenrellenZahleninsichistbSekXanntlichinjektivund?-'nMRoܠ1.UUDIENA*T@fURLICHENZAHLENKȤ63d&MesIagilt1[=2fG(R2+x).IyEineMengedernatSyurlicrhenZahleninR2+ eistdannN6=URf1;2;5;26;:::ʜg.Aus:;denvielenwicrhtigen:;Eigenschaften,:dieeineMengevonnatSyurlicrhenhZahlenbSesitzt,istdasZahlenrechneninNhervor-zuhebSen.+BevrorwiraberdieeinfacrhstenRechenopSerationenein-fSyuhrengkyonnen,gmSyussenwireinesderwicrhtigstengBeweisprinzipi-enz$studieren,zIdenBewreisdurchvollstyandigeInduktion.zIEsgibtdazuXvieleVVarianrten.XWirwollenlediglichzweidavonangebSen.SieallebauenaufdemPreano-Axion(P5)auf.WVeiterbSenyotigenwirtbeinvroralleminderInformatikundmathematischenLogikwicrhtiges£Hilfsmittel,®dieDe nitionvronAbbildungendurchpri-mitivreiRekursion,ibSevorwirdieeinfachstenRechenopSerationenin derMengedernatSyurlicrhenZahleneinfSyuhrenkyonnen.EDiesesHilfmittelwrerdenwirimnyachstenParagraphenbSeprechen.Satz1.4.Q('yubffer35denBeweisdurchvollstyandigeInduktion):F'yurjeffdenat'yurlicheZahlnUR2NseieineA2ussageA(n)formuliert.Daf'yur35gelteUTʍInduktionsanfang:A(1)35istrichtig(wahr)undInduktionsannahme:aus35derR2ichtigkeitvonA(n)Induktionsschlu:folgt35dieR2ichtigkeitvonA(n+1).Dann35istA(n)f'yurallenUR2N35richtig.(Formal:35(A(1)^8nUR2N[A(n)=)A(n+1)])UR=)8n2N[A(n)])&Beweis.XSei.#E0:={fn2NjA(n)g:Esgilt12E:und8n2E[n+12E]wregenderInduktionsvoraussetzungen.Nach(P5)istE i=URN,also8n2N[A(n)]. yff٘ ̍ ff ̄ ffffff٘VVarianrtenMdiesesSatzessindvorallemInduktionsaussagen,~dieerstvroneinervorgegebSenenZahln0V2URNangelten:K.A(n0)^8nUR2N[nn0j^A(n)=)A(n+1)])q=)UR8n2N[nn0V=)A(n)]:Diese{AussagewrerdenwirandieserStellenichtbSeweisen,{zumalwir@dieOrdnrungm_.n@aufdennatSyurlichenZahlennoSchgar@('nMR64}hIGI.UUNA*T@fURLICHEZAHLENd&Mnicrht|kennen.|gDieAussageergibtsichspyaterabSerganzleichtausdemBeispieleinerMengevronnatSyurlichenZahlen,dieeineTVeilmengeTvronNistmitderselbSenNachfolgerabbildung,demAnfangselemenrt.n0,.undderenElementegeradediejenigennUR2Nsind,hfSyurdien0 HDngilt,also(fnD2Njn0 Hng;n0;).(vgl.Beispiel3.8(2)).M*FSyur1dennyacrhstenSatzsetzenwirvoraus,1dadieOrdnungvonN;scrhonbSekXanntist.uDieseOrdnungwirdzwarerstin3.3ein-gefSyuhrtHwrerden.ȁDerSatzgehyortjedoSchsystematischindiesenAbscrhnitt(۞yMubServollstyandigeInduktion.ՉErwirdzurHerleitungdesOrdnrungsbSegri esinNauchnichtverwendet.mSatz1.5.Q('yubffer35diestarkevollstyandigeInduktion)F'yurjeffdenat'yurlicheZahlnUR2NseieineA2ussageA(n)formuliert.Daf'yur35gelte"UTʍInduktionsanfang:A(1),Induktionsannahme:aus358iURn[A(i)],d.h.ausA(1);:::ʚ;A(i);:::;A(n),Induktionsschlu:folgt35A(n+1).#Dann35giltA(n)f'yurallenUR2N.&Beweis.XWirvde nierenB(n):()8i2N[in=)A(i)]:DanngeltenB(1)und8nZL2N[B(n)=)B(n+1)].Xfegp?f Ѝf1g8s̬q؟q؟*ЎhsHq؟Hq؟j莎&zx  kommutiert,35wobffei (1)UR=c,35(1)=1:&Beweis.XQuelleOundZielfSyurdiegesucrhteOAbbildung cstehenfest.WirsucrhendenGraphenvon .DazubSetrachtenwirdieAbbildung(')UR:NXF3UR(n;x)7!((n);'(x))2NXunddasElemenrt(1;c)>2NX.NachLemma1.2seiGdiekleinsteTVeilmengevronNX+mit(')(G)URGund(1;c)2G.1)Esist(m;yn9)r2G()((m;yn9)=(1;c)[_9(n;x)r2G[(m;yn9)=(n+1;'(x))].HierbSeigilt*"B(=-l\&wregenderDe nitionvonG.DieRicrhtungɟ*" ly=)-l\]erhyaltmanausderfolgendenArgumenrtation:Angenommen, 6die FVolgerunggiltnicrht.Dann gibtesein(m;yn9)UR2Gmit(m;yn9)6=(1;c)und8(n;x)2G[(m;yn9)6=(n8+1;'(x))].DannkJgilt(')(Gnf(m;yn9)g)Gnf(m;yn9)gkJund(1;c)2G.nf(m;yn9)g.0Das0kXannabSernicrht0sein,weil0GdiekleinsteMengemitdiesenEigenscrhaftenist.2)W GistGrapheinerAbbildungvronNnachX.W1WirzeigendurchvrollstyandigeInduktion8n2N9x2X[(n;x)2G]:SeialsoA(n)dieInduktionsaussage9xUR2X[(n;x)2G].Induktionsanfang:A(1)giltwregen(1;c)UR2G.B>'nMR66}hIGI.UUNA*T@fURLICHEZAHLENd&MInduktionsannahme:GelteA(n),d.h.9xUR2X[(n;x)2G].Induktionsscrhlu:WVegen(n+1;'(x))UR2GgiltA(n+1).DamitfolgtdieBehauptung.WVeiter-zeigenwirdurcrhvollstyandigeInduktion:. 8n2N-8x;y6"2X[(n;x) 2G&^(n;yn9) 2G=)x=y].PSeiPA(n)dieInduktions-aussage8x;yË2URX[(n;x)2G^(n;yn9)2G=)x=y].Induktionsanfang:Sei(1;x)W2Gund(1;c)2G.AngenommenxTn6=c.WVegen1)gibtes(n;z)Tn2G[(1;x)=(n+1;'(z))],also1o/=n+1imWidersprucrhzu(P3).Alsoistxo/=c.DarausfolgtA(1).Induktionsannahme:kGeltek{A(n),d.h.8x;yR2WX[(n;x)2G^(n;yn9)UR2G=)x=y].Induktionsscrhlu:>Seien>xx;yË2URX/gegebSenmit(nJ+1;x)UR2G>xund(n+1;yn9)a2G.`ODa`1ndurcrhn+1`1eindeutigfestgelegtist(istinjektiv),gibtes(nacrh1))u;v2qGmit(n;u)q2G;(n;vn9)2Gund:C'(u)UR=xund'(vn9)=y,:pwregen:C(nB]+1;'(u))UR=(nB]+1;x):Cund(n+1;'(vn9))[=(n+1;yn9).NacrhInduktionsannahmeistu[=v,alsoxUR='(u)='(vn9)=y.Alsoist h:=UR(N;XJg;G)eineAbbildung.3)y erfSyulltdieBedingungen (1)qD=cyund8nqD2N[ (n<+1)qD='( (n))],XAdennW(n;x)2Gund(nS+1;'(x))2Gimplizieren (n)UR=xund (n+1)UR='(x)=' (n).4)*PEsbleibtzuzeigen,*da =eindeutigbSestimmrtist.Seialso :URN !Xfmit O(1)=cund8n2N[ O(n<&+1)UR=' (n)]gegebSen.WirzeigendurcrhvollstyandigeInduktion8n{2N[ (n)= O(n)].SeiA(n)dieInduktionsaussage (n)UR= O(n).Induktionsanfang:Esist (1)UR=c= O(1),alsogiltA(1).Induktionsannahme:Sei (n)UR= O(n).Induktionsscrhlu:.Dann-ist (n+1){/='( (n))='( O(n))= O(n+1).Damitgilt h=UR O. yff٘ ̍ ff ̄ ffffff٘'dIn>diesemSatzistdasHilfsmitteldervrollstyandigenInduktiongleicrh9Pmehrfachangewendetworden.9~DamithabSenwirjetztaberCK'nMz2.UUPRIMITIVEREKURSIONV67d&MaucrhNdieMyoglichkeit,cdieFVunktion'2n >fSyurallenUR2zude nieren.WirscrhreibSeneinfach'21(c)9=cund'2n+1(c)9='('2nP(c)).FSyurfestgewyahlteso'cUR2X`gibtesdamiteineAbbildung'()(c):N !XgegebSen,ywrobeih'(n)(c)UR='2nP(c)gelte.yDadamitderWVertfSyurjedes}cNt2Xneindeutigfestgelegtist,}+habSenwiraucrhdieAbbil-dungen_'2n 2:X|" {!XfSyurallen2Nde niert.Hyau gbraucrhtmanzurrekursivrenDe nitionvonAbbildungenetwaskompli-ziertereBedingungenandieRekursion.IDereinfacrhsteFVallistder9Satz2.2.Q('yubfferdieprimitiveRekursion):(SeiXDeineMenge,cu2X6*einDElementund'u:NXg$ }!uXeineDA2bbildung.DDanngibt35esgenaueineA2bbildung h:URN !X$mitX)ו(1)= (1)UR=c,)ו(2)=8nUR2N[ (n+1)UR='(n; (n))],d.h.35sodadasDiagrffamm8tˍwgnNwgN8҄fd.8ά-x "%#NXxXƹ32fd a؍ά-q%%'<Xfeo?ЍoP(id\!msbm5N 1; )4>Xfegp?f Ѝf1g8s̬q؟q؟*ЎhsHq؟Hq؟j莎&zx %kommutiert,wobffei (1) =(1;c),(1)=1und(id ʤqymsbm7NX; )(n) :=(n; (n)).9&Beweis.XWirwrenden2.1anaufNNX,(1;c)Sp2NNXqwund <:ܿNX_ !NX,1 n9(n;x):=(n+1;'(n;x)).1Dann1ygibtesgenau@eineAbbildung :߆N 4!NHVXmit@ O(1)߆=(1;c)und O(n+1)UR= n9( (n))fSyurallenUR2N@:9wwghNwgN8҄fd.8ά-x  NXٵuNXJg: 32fdƍά-:ɳ #XfeVڟ?ЍVJ 8XfeNj?ЍM Ѝ~l{f1g8Z̬XҟXҟ*ЎhZHXҟHXҟj莎&pzr z#DurcrhU &werdeneindeutigAbbildungen:N !Nund :N A!Xde niertmit O(n)=((n); (n)). FSyurdieseAbbildun-gencgilt(1)UR=1,c (1)=ccund((n=+1); (n+1))UR= O(n=+1)UR=DW>'nMR68}hIGI.UUNA*T@fURLICHEZAHLENd&M n9( O(n))g= ((n); (n))=((n)?+1;'((n); (n))),,alsoist(n+1)=(n)+1Y?und (n+1)='((n); (n)).Y\DaY?dieAb-bildungabSer(1)UR=1und(nE`+1)UR=(n)E`+1UR=(n)erfyulltundebSensoid [qN(1)UR=1undid [qN(n +1)UR=id ʢNX(n)gilt,istUR=id Nnacrh2.1,alsoist (n+1)UR='(n; (n)).Ist 2K cmsy80 :NkI!XgegebSenmit 20(1)=cund 20(n*+1)='(n; 20(n))fSyurallen2N,ysoerfSyullt O20 :N !NUXmit O20x(n)5:=(n; 20(n))dieBedingungen O20(1)5=(1; 20(1))=(1;c)und O20x(n{+1)hc=(n{+1; 20(n+1))hc=(n{+1;'(n; 20(n)))hc= n9(n; 20(n))UR= ( O20x(n)),alsoist =UR O20c0unddamit h= 20. yff٘ ̍ ff ̄ ffffff٘&w䍑WirFDkrommenjetztzudenGrundlagendernatSyurlichenZahlenzurSyucrk.Wirhattenschongefordert,daeineMengedernatSyurli-crhen`Zahlenexistierensoll.`EsistabSerzunyachstnichtklar,`obeshierWvrerschiedeneWVahlmyoglichkeitenfSyurdieseMengegibt.XWirwrerden^inBeispiel3.8tatsyachlichverschiedeneMengenange-bSen,MdieMdiePreano-AxiomeerfyullenunddamitalsMengendernatSyurlicrhen'aZahleninFVragekommen.'Damitwyareesmyoglich,da gspyateresRecrhnenmitnatSyurlichenZahlenvonderWVahlderMenge1abhyangt,1AwrasnatSyurlichrechtunsinnigwyare.1ADeswegenistderfolgendeSatzwicrhtig.MSatz2.3.Q(vonderEindeutigkeitderMengedernat'yurlichenZahlen): JSeienaX(N;1;)und(A;a;)Mengendernat'yurlichenZahlen.DanngibtesgenaueineA2bbildung :ZN I!Amit (1)UR=a35und UR= ,35unddieseA2bbildungistbijektiv.&Beweis.X:kNacrhb2.1folgtExistenzundEindeutigkeitvon :NUR !URA?Ymit (1)=a,? (nL+1)=( (n)).?EbSenso?Ygibtesgenauein :URA !N,sodadasDiagramm:ፍ9;A93(Ah8҄fd-,؍ά- ՍE qǍNqǍ\dN:;32fd-,؍ά-q%CoڟXfe ?Ѝ| gjXfe?Ѝ Ѝ*fag8̬*ЎhHHj莎&8\IK6=;.WVennnyamlicrhdannr&V2AC>\I,dannQgilt8i2I[rW<i],Q2d.h.r2IBistQdaskleinsteElemenrtvonI.$Wir$anehmenjetztan,daAA\I\=kP;.Nacrh$a(3)ist1kP2A.Sein2Aundseii2I.WVegenAe\I-=;istnv=2!UI,alsoJ!'nMR74}hIGI.UUNA*T@fURLICHEZAHLENd&Mn6=i.;WVeiteristni,alsoexistierteint2Nmitn"+t=i.WVegenO1Gtistn[q+1Gn[q+tG=i,alsoistaucrhn[q+1G2A.NacrhInduktionsprinzipistdaherA=NundI{N=A,5einWidersprucrhzuA\IF=UR;. yff٘ ̍ ff ̄ ffffff٘G퍍&Beweis.Xvron3.2(3)ii)Aus1~m=1~nfolgtm=n.WVennaus-tmz=tndieGleicrhungmz=nfolgt,-soscrhlieenwirwiefolgt.Sei(t#+1)mg=(t#+1)n.WVennmg=n,dannsind=wirscrhonfertig.>Sonstgiltn~m=oSderm~n.Bis=aufUmrbSenennung"&kyonnenwirngm"&mitn~+sg=m"&annehmen.Dann@YisttLn+n+1=(tL+1)n+1=(tL+1)m+1=(t+1)(n+s)+1u=tn+n+ts+1,nacrh3.2(3)i)also1UR=tYs+1imWidersprucrhzu(P3).AlsokXannnY+sUR=mnichteinrtreten.EsgiltdahernUR=m. yff٘ ̍ ff ̄ ffffff٘G퍍Bemerkung3.6.|R3Die-letzteAussagedesSatzesisteinwicrhtigesmathematiscrhes*Beweismittel,hdasmanauchdie*"cJagdnachdemkleinsten0VVerbrecrher-l\snennt.^Wenn0maneineAussageA(n)fSyuralleXn%2NbSewreisenwillundeinevollstyandigeInduktionkom-pliziertwird,Wsohilfthyau gdiefolgendeArgumenrtation.Mannimmrtan,daesElementer2URNgibt,fSyurdiedieAussageA(n)falscrhEist.DanngibtesnachTVeil(4)desSatzesaucheinkleinstessolcrhesn0 ?2N,FfSyurdasA(n0)falschist.FDasElementn0 ZnenntmanaJoftaucrhdenkleinsten*" VVerbrecher-l\Ҕ.ahManzeigtdann,dadieseCBedingungzueinemWidersprucrhfSyuhrt.TEsgibtalsokeineElemenrten 2N,fSyurdiedieAussagefalscrhist.SieistdaherfSyurallenUR2Nricrhtig.!"DerkBegri derWVohlordnrunghateineweitereungemeinwich-tigeBedeutunginderMengenlehre.Esgibtnyamlicrheinwei-teres*AxiomderMengenlehreVyubSerdieWVohlordnrung.qFyurvie-lekAnrwendungensinddiedazuyaquivXalenten(unddamitauchalsܐAxiomederMengenlehrevrerwendbaren)ܐAussagenebSensowicrhtig.[zWir[]kyonnensiehiernrurfSyurspyatereAnwendungenfor-mrulieren,abSerihrebpxAquivXalenznichtbSeweisen.K\'nMR0(3.UUDIESTRUKTURENAUFDENNA*T@fURLICHENZAHLEN ,75d&MAxiom7.U%JedeMengekXannwrohlgeordnetwerden,Ad.h.aufjederMengegibteseineWVohlordnrung.zSatz3.7.QUnter$denKyubrigenAxiomenderMengenlehrffesindyaquivalent:)ו(1)=(Wohlorffdnungsaxiom):JedeMengekannwohlgeordnet=werffden.)ו(2)=(ZornschesLffemma)BesitztineinergeordnetenMenge=A%ajeffdetotalgeordneteTeilmengeeineobereSchranke,%eso=bffesitzt35AeinmaximalesElement.)ו(3)=(A2uswahlaxiom)Z9ZujeffderMengeMv6=;gibteseineAb-=bildung35fQ:URP(M@) !MtmitderEigenschaft]8U62URP(M@)nf;g[fG(U)UR2U]:=*"D*{EsgibteineA2bbildungfG,dieausjeffdernichtleerenTeil-=mengeU_vonMeinesihrfferElemente,ZnyamlichfG(U@),=auswyahlt.(\('BevrorcwirweitereEigenschaftendernatSyurlichenZahlenstudie-ren,wrollenwireinigeBeispielefSyurMengendernatSyurlichenZah-lenanfSyuhrenunderinnerndazunoScrhmalsandenSatz2.3.Beispiele3.8.|~V(1)Ein(durcrhAxiom6gegebSenesTVripel=(N;1;)isteineMengedernatSyurlicrhenZahlen.)ו(2)=SeiNn0V2URNeinenatSyurlicrheZahl.ODannistdieMengeN6:==fnUR2Njn0Vng>zusammenmitn0BundderEinscrhryankung=jN vronÐalsjN n:URN6 !NteineÐMengedernatSyurlichen=Zahlen.)ו(3)=N0V:=URN[f0gzusammenmit0und20mit"ÆE 09(n)UR=􍓫8 < : 8(n);BfSyurTwn2N;ɍ 81;BfSyurTwn=0;"ڍ=isteineMengedernatSyurlicrhenZahlen.L,'nMR76}hIGI.UUNA*T@fURLICHEZAHLENd&M)ו(4)=N0BN0wzusammenmit(0;0)und:URN0BN0Vj!N0BN0=mit ](m;n)UR:=􍓫8 < : 8(m+1;n1);s|,falls|n>0;ɍ 8(0;m+1);s|,falls|n=0; ^=isteineMengedernatSyurlicrhenZahlen."DasT;letzteBeispielistetrwasT;komplizierterundzeigt,Tdaeshyau grnicrhtsofortersichtlichist,sobmaneinMoSdellfyureineMenge2dernatSyurlicrhenZahlenvorsichhat.2DabSeigibteseineneinfacrhenf0g.'DadieMengeo enrbarnichtleerist0undinNliegt,existiertt,undesistt2=a0m5+b0n:0DieDivisionu2mitRestergibtm=qn9tG+rmitu20rHm6ersetzt,bisr=UR0eintritt.0Oڍ,m0V:=URm;sn0V:=URn;hm0V=URq0n0j+r0;0URr0VndurcrhfSyuhrt(derFVallmUR=nisttrivial)undihnnoScrhumeineZeilenachobSenhinerwreitert,nyamlich-ʍ!Tm1:=URn;^Q*n1:=URm;Mm1=UR0n1$+r1 \|;W0URr1EsistnacrhKapitelI2.30zuzeigen,da Esurjektivist.WirbSewreisendasqdurcrhvollstyandigeInduktionnachn.r)DieBehauptungistklarfSyurnG=1.9Sei :f1;:::ʚ;n>+1gG !Gf1;:::ʚ;n+1geineinjektivreoaAbbildungund 20:7;f1;:::ʚ;ng !f1;:::ʚ;n+1goadieEinscrhryankungvon .1.JFVall:Bic( 20)URf1;:::ʚ;ng.JDannist 20injektivundnacrhInduk-tionsannahme>damitaucrhsurjektiv,@alsobijektiv.Da injektivist,ist (n+1)#=u2f1;:::ʚ;ng,also (n+1)u=n+1.Damitist 7surjektiv.2.{FVall:WennBiY( 20){6f1;:::ʚ;ng,{danngibtesgenaueinimit2 20(i)m=n+1m= (i).2Da Finjektivist,gibtesaucrheinjH2?uf1;:::ʚ;ng mit (nn+1)=j. Sei nrun :f1;:::ʚ;ng !f1;:::ʚ;ngde niertdurcrh!} O(m)UR=􍓫8 < : 8 (m);63m6=i;ɍ 8j;63m=i: FOinjektiv2=)UR surjektiv=)alleZahlenf1;:::ʚ;n3+1gnfj;n+1gپkrommeninBiog( )vor,n0ist,dannistdieKompSosi-tionlf1;:::ʚ;mg g UY!U[f1;:::;ng2T,!f1;:::;mglebSenfallsinjektiv,also nacrh4.1surjektiv, abSermistnichtnurimBilddieserAb-bildungwregenmUR>n.Widerspruch.DamitistmURn:(2)SeimURn:Dannist#VL (i)UR=􍓫8 < : 8i1inɍ 81nalsoA6=;>endlicrh.? WirbSenutzeneineAuswahlabbildungfQ:URP(A)nf;g !A(vgl.3.7)mitfG(U@)2UYrfSyuralleTVeilmengenS'nML4.UUANZAHLAUSSAGENbP83d&MU6=t;vronA.WVeiterseig&:P(A)nfAg F!AdieAbbildunggn9(U@)UR:=fG(A’nU).Danngiltgn9(U)=UR2UUrm3ist,3danngibtesmindestenseinSchubfach,das=mehrffere35Objekteenthyalt.)ו(2)=WennmannObjekteaufmSchubfyacherverteiltund=nURmmdimpli-ziert,da dnicrhtinjektivist.AlsoexistierteinSchubfachjBundObjektei1;i2mit (i1)UR= (i2)=j:(2)6 :nf1;:::ʚ;ng +!f1;:::ʚ;mg6undnn?'nMR86}hIGI.UUNA*T@fURLICHEZAHLENd&MAUR !URf0;1gmitBN>(a)UR=􍓫8 < : 80a62Bɍ 81a2B:\DannistP(A)]k3Bq7!B 2Abb:(A;f0;1g)]k=f0;1g2A einebijektivreAbbildung. &Beweis.XDie]Umkrehrabbildungist 7!B-:=fa2Aj (a)=1gUR= 21 p (1): yff٘ ̍ ff ̄ ffffff٘Folgerung4.9.rSei+AeineendlicheMengemitnElementen.Dann[bffesitztAgenau22nTeilmengen,d.h.die[PotenzmengeP(A)bffesitzt35genau22n ۅElemente.򐍍&Beweis.XP(A)yrXundxf1;2g2A VhabSengleicrhviele,y0also22n !Ele-menrte. yff٘ ̍ ff ̄ ffffff٘De nition4.10.yDerLBinomialkoffezientf\ ō nYyV0rf\!"KyistdieAnzahlU^derDrS-elemenrtigenTVeilmengeneinerMengeAmitnElementenU]fSyur0r/hn.SWirde nierenfSyurr/h>0:Sf\ ōsnYy rof\!(u:=0,SundfSyurmUR>n:ꨟf\ ō wnYy Tmif\!!\g:=0.Beacrhte:ꨟf\ ō TnYy g0ݟf\!=URf\ ō ?nYy ?nCf\!=UR1:&Folgerung4.11.yޟP*n̍r0Yy>0D f\!j16df\ ō>1Yy>rD f\!7p116df\ ō>2Yy>rD f\!y81j21jПf\ ōnYyU|r618f\!p+-f\ ō5EnYy68}r<Οf\!6df\ ō>3Yy>rD f\!n17p33P1if\ ō Tn+1Yy32r%f\!6df\ ō>4Yy>rD f\!d1y84j6471ˍJeffderOEintragdiesesDreiecksindern-tenZeileanderrS-tenU]Stelle35enthyaltdanndenWertf\ ō nYy r!jf\! .XV'nMR88}hIGI.UUNA*T@fURLICHEZAHLENd.MSatz4.14.XF'yur350URrngiltf\ ō nYy r!jf\!ah=ō{n!Qmfe0  rS!(nr)!&|&Beweis.XDurcrhvollstyandigeInduktionnachnbSeweisenwir"7A(n)UR:()8r2Nf^G0rn=)f\ ō ?nYy 6rCf\!=ō{n!Qmfe0  rS!(nr)!\ǟf^b@:,ҍInduktionsanfang:Espistf\ ō 1Yy 0gf\!=UR1=ō o1!Qmfe  0!1!]¤undf\ ō 1Yy 1gf\!=UR1=ō o1!Qmfe  1!0! n: Induktionsannahme:SeiA(n)wrahr.Induktionsscrhlu:.ŅCf\ ō&n+1Yy1HrB[f\!M=URf\ ōnYy ?r61%if\!/+f\ ō TnYy Grݟf\!=ō0n!Qmfeb  (r61)!(nr+1)!ka+ōn!۟Qmfe0  rS!(nr)!E=ōn!r6+n!(n+1rS)Qmfejf  HrS!(n+1r)!s+p=ō{(n+1)!QmfeN^  rS!((n+1)r)!1ٍfSyur1URrn:FSyurҦr3=20istf\ ō Rn+1Yy{0(f\!3Y=UR1=ō I(n+1)!Qmfe0  0!(n+1)!undfSyurr=2nH+1Ҧistf\ ō!n+1Yy!n+1=[f\!H=1UR=ō I(n+1)!Qmfe0  (n+1)!0!6: yff٘ ̍ ff ̄ ffffff٘#ɍSatz4.15.X(Die& binomischeFormel)F'yurallea;bUR2R& undnUR2Ngilt|(a+b) n=8n ܟX ҁURr6FVaktorenergebSenb2nrW*. yff٘ ̍ ff ̄ ffffff٘Ycs'nMD(5.UUEINKURZERAUFBAUUUDESZAHLENSYSTEMS l,89d&ME+5.VkEinkurzerAufbaudesZahlensystems!NލInmdiesemkurzenAbscrhnittwollenwirandeuten,nwiemannunmitBdenfSyurdienatSyurlicrhenZahlengewonnenenEigenschaftendaswreitereZahlsystementwickeltwerdenkXann.WWirgebSenle-diglicrhdieKonstruktionenderMengenderganzenZahlen,derrationalen Zahlen, derreellenZahlenundderkromplexenZahlenan, ohnejewreilsdieRechengesetzeherzuleiten. LediglichfSyurdiekromplexenZahlende nierenwirdieAdditionunddieMultipli-kXation.LDe nition5.1.sDieMengederganzenBZahlenZwirdwiefolgtde niert.AufN NbildetmaneineZpxAquivXalenzrelationdurcrhh(a;b)UR(c;d):()a+dUR=b+c:DieMengederbpxAquivXalenzklassenNN=URistdannZ:ManfassedieKlasseщfe 3/(a;b)!fMalsabauf.De nition5.2.sDieWvMengederrffationalenZahlenQwirdwiefolgtKode niert.KAufZ(Znf0g)KobildetmaneinepxAquivXalenzre-lationdurcrhws(a;b)UR(c;d):()ad=cb:Dannode niertmanQUR:=Z(Znf0g)=URoundkSyurztщfe 3/(a;b) durcrhFuG-aG-콉feϟ'pzb$ab.De nition5.3.sDie6MengederrffeellencZahlen6Rwirdwiefolgtde niert.jEineTVeilmengeaQheitDeffdekindschercSchnitt,wrennS)ו(1)=aUR6=;^aUR6=Q;)ו(2)=8xUR2a8yË2Q[xy=)y2a];)ו(3)=a4enrthyaltkeinkleinstesElement(bzgl.4derOrdnungvon=Q):DieMengeRderreellenZahlenistdieMengederDedekindscrhenScrhnitte.EinereelleZahlistalsoeinDedekindscherSchnitt.Zn|'nMR90}hIGI.UUNA*T@fURLICHEZAHLENd&MNacrhU,EinfSyuhrungderOrdnunginderMangederreellenZah-len73undderIdenrti zierungderrationalenZahlenmitspSeziellenreellen'Zahlenstelltsicrhdannheraus,2daderzugehyorigeDede-kindscrheSchnittfSyureinereelleZahlr:KausallenrationalenZahlenxmitr<URxbSestehrt.De nition5.4.sDiéMengederkomplexenZahlenCistRDmRmitdenRecrhenopSerationen(a;b)Y+(c;d) T=(aY+c;b+d)und(a;b)(c;d)UR=(acbd;ad+bc):EsistiUR:=(0;1):w;'naH 5- cmcsc104@ cmti12-Nff cmbx12,N cmbx12(!", cmsy10'g cmmi12&XQ cmr12#%n eufm10K cmsy82cmmi8|{Ycmr8!msbm5qymsbm7 msbm10K`y cmr10O line10u cmex10z