KONSTRUKCIJA NARAVNIH STEVIL ˇ

UNIVERZA V LJUBLJANI PEDAGOˇ SKA FAKULTETA Pouˇ cevanje: Predmetno pouˇ cevanje

SPELA ZOBAVNIK ˇ

AKSIOMATSKA

KONSTRUKCIJA NARAVNIH STEVIL ˇ

MAGISTRSKO DELO

LJUBLJANA, 2016

UNIVERZA V LJUBLJANI PEDAGOˇ SKA FAKULTETA Pouˇ cevanje: Predmetno pouˇ cevanje

Matematika in tehnika

SPELA ZOBAVNIK ˇ

AKSIOMATSKA

KONSTRUKCIJA NARAVNIH STEVIL ˇ

MAGISTRSKO DELO

Mentor: izr. prof. dr. MARKO SLAPAR

Ljubljana, 2016

Zahvala

Mentorju izr. prof. dr. Marku Slaparju

Hvala, da ste me vzeli pod svoje okrilje, predvsem pa hvala za vso po- trpeˇzljivost, skrb, ˇcas in strokovno pomoˇc pri nastajanju magistrskega dela.

Mojim

Hvala za vso podporo, zaupanje in razumevanje ter tisoˇckrat hvala, da ste vedno verjeli vame in mi stali ob strani.

Povzetek

V magistrskem delu so najprej predstavljena naravna ˇstevila, in sicer smo jih vpeljali preko Peanovih aksiomov. Z vsemi petimi aksiomi po- stopoma prikaˇzemo raˇcunski operaciji seˇstevanje in mnoˇzenje ter njune osnovne lastnosti (nevtralni element, komutativnost, asociativnost, di- stributivnost). Predstavljena so tudi rekurzivno definirana zaporedja, urejenost naravnih ˇstevil ter odˇstevanje in deljenje, ki pa sta le delno definirani operaciji v naravnih ˇstevilih. V nadaljevanju je velik po- udarek na natanˇcnih dokazih osnovnih lastnosti naravnih ˇstevil le s pomoˇcjo Peanovih aksiomov. V poglavju o mnoˇzicah smo se v glav- nem posvetili sistemu ZFC aksiomov, ki so ime dobili po matematikih Zermelu in Fraenkelu ter aksiomu izbire (C). S pomoˇcjo aksiomatske teorije mnoˇzic (predvsem aksioma o neskonˇcnosti) naravna ˇstevila vpe- ljemo kot mnoˇzico, v kateri pokaˇzemo veljavnost Peanovih aksiomov.

V zadnjem delu smo vpeljali ˇse cela in racionalna ˇstevila kot kvocientni mnoˇzici karteziˇcnega produkta N×N oziroma Z×Z\ {0}.

Kljuˇcne besede: naravna ˇstevila, Peanovi aksiomi, rekurzivno za- poredje, teorija mnoˇzic, ZFC aksiomi, cela ˇstevila, racionalna ˇstevila.

Abstract

The natural numbers are presented first in the master’s thesis. We introduced them through Pean axioms. With all five axioms we gradu- ally show the arithmetic operations of addition and multiplication and their basic characteristics (neutral element, commutative, associative and distributive properties). The recursively defined sequences, order of natural numbers and subtraction and division, which are only parti- ally defined operations in natural numbers, are also presented. A great emphasis is on accurate proofs of basic properties of natural numbers only with the help of Pean axioms. In the chapter about sets we focu- sed our attention to the system of ZFC axioms, which got their names after mathematicians Zermel and Fraenkel and the axiom of choice (C).

With the help of axiomatic of the theory of sets (mainly axiom of infi- nity) we introduce natural numbers like a set in which we show validity of Pean axioms. In the last part of the thesis we also introduced inte- gers and rational numbers like quotient sets of the Cartesian product N×N or Z×Z\ {0}.

Key words: Natural numbers, Pean axioms, recursive sequence, the- ory of sets, ZFC axioms, integers, rational numbers.

Kazalo

Poglavje 1. Uvod 1

Poglavje 2. Naravna ˇstevila 3

2.1. Peanovi aksiomi 3

2.2. Rekurzivno definirana zaporedja 9

2.3. Seˇstevanje naravnih ˇstevil 9

2.4. Lastnosti seˇstevanja 11

2.5. Urejenost naravnih ˇstevil 13

2.6. Mnoˇzenje naravnih ˇstevil 15

2.7. Lastnosti mnoˇzenja 16

2.8. Odˇstevanje in deljenje v naravnih ˇstevilih 19

Poglavje 3. Mnoˇzice 21

3.1. ZFC aksiomi 22

3.2. Konstrukcija naravnih ˇstevil 28

3.3. Ekvipolenca mnoˇzic 30

Poglavje 4. Cela in racionalna ˇstevila 35

4.1. Cela ˇstevila 35

4.2. Racionalna ˇstevila 41

Poglavje 5. Sklep 47

Literatura 49

POGLAVJE 1

Uvod

V magistrskem delu bomo pokazali enega izmed standardnih naˇcinov definicije naravnih ˇstevil, s pomoˇcjo Peanovih aksiomov, ki jih je prviˇc postavil Giuseppe Peano (1858 - 1932). To ni edini naˇcin za definicijo naravnih ˇstevil, saj drug pristop zajema pogovor o kardinalnosti (moˇci) konˇcnih mnoˇzic, kjer lahko vzamemo mnoˇzico elementov in definiramo npr. ˇstevilo kot ˇstevilo elementov v tej mnoˇzici. Vendar se bomo sami osredotoˇcili na Peanove aksiome in z njimi definirali naravna ˇstevila.

Neformalno lahko reˇcemo:

Definicija 1.1 (neformalno). Naravno ˇstevilo je katerikoli element v mnoˇziciN:={0,1,2,3, . . .}, kjer je mnoˇzica dobljena tako, da zaˇcnemo z 0 in nato ˇstejemo naprej v neskonˇcnost. Mnoˇzico N imenujemo mnoˇzica naravnih ˇstevil.

Kljub temu to ni ravno zadovoljujoˇce, saj se poraja vpraˇsanje, kaj pa je N. Definicija zaˇcni pri 0 in ˇstej v neskonˇcno je sicer intui- tivno jasna, ni v pa celoti sprejemljiva, saj puˇsˇca veliko neodgovorjenih vpraˇsanj. Na primer: kako vemo, da lahko ˇstejemo v neskonˇcnost, brez da se bomo slej ko prej vrnili nazaj na 0? Kako izvajamo operacije, kot so seˇstevanje, mnoˇzenje ali potenciranje? Na zadnje vpraˇsanje bo dokaj preprosto odgovoriti: definiramo lahko kompleksne operacije s pomoˇcjo preprostejˇsih operacij. Potenciranje ni niˇc drugega kot pona- vljajoˇce mnoˇzenje (5³ ni niˇc drugega kot tri petice zmnoˇzene skupaj), mnoˇzenje ni niˇc drugega kot ponavljajoˇce seˇstevanje (5·3 ni niˇc drugega kot tri petice seˇstete skupaj). In seˇstevanje? Ne gre za niˇc drugega kot ponavljajoˇco operacijo ˇstetja oziroma poveˇcevanja. ˇCe dodamo petici ˇstevilo 3, pravzaprav petico trikrat poveˇcamo za 1. Seveda bomo v na- daljevanju videli, da tudi takˇsne definicije zahtevajo nekaj razmisleka.

Po drugi strani pa zgleda, da je poveˇcevanje ˇstevila za 1 osnovna opera- cija, ki je ne moremo razbiti na bolj preprosto operacijo in je dejansko

prva operacija, ki se jo nauˇcimo na ˇstevilih, celo preden se nauˇcimo seˇstevanja.

Zgodovinsko gledano je spoznanje, da lahko s ˇstevili ravnamo aksi- omatiˇcno, precej novo, ni staro veˇc kot 100 let. Pred tem so bila ˇstevila obiˇcajno razumljena kot neloˇcljivo povezana z nekim zunanjim koncep- tom, kot je na primer doloˇcanje moˇci mnoˇzice, merjenje dolˇzine dela ˇ

crte ali mase fiziˇcnega objekta itd. Ta naˇcin je deloval precej dobro, dokler se ni bilo potrebno premakniti iz enega sistema ˇstevil v drugega;

na primer, razumeti ˇstevila v smislu ˇstetja kroglic na abaku je zelo do- bro za predstavitev ˇstevil kot sta 3 in 5, ampak ne deluje tako dobro za ˇstevila kot so −3, 1/2, √

2, π ali 1 +i; zato je vsak velik napredek v teoriji ˇstevil (npr. negativna ˇstevila, cela ˇstevila, iracionalna ˇstevila, kompleksna ˇstevila) vodil do veliko nepotrebne filozofske tesnobe. Ve- liko odkritje pozno v devetnajstem stoletju je bilo, da lahko ˇstevila razumemo abstraktno, preko aksiomov, ne da nujno potrebujemo kon- kretni model. Zato bomo tudi z uporabo ZFC aksiomov predstavili mnoˇzico in poslediˇcno naravna ˇstevila, iz le teh pa bomo izpeljali ˇse cela in racionalna ˇstevila.

POGLAVJE 2

Naravna ˇ stevila

2.1. Peanovi aksiomi

Za definiranje naravnih ˇstevil bomo uporabili dva osnovna kon- cepta: niˇcelno ˇstevilo in operacijo poveˇcevanja (naslednika). Podobno kot v modernih programskih jezikih, bomo uporabilin++ za oznaˇcevanje naslednika ˇstevila n. Tako je na primer 3 + + = 4 naslednik ˇstevila 3, (3 + +) + + = 5 naslednik ˇstevila 4, itd. To je malce drugaˇcna uporaba kot v programskih jezikih (npr. C), kjer n+ + pravzaprav preoblikuje vrednost n-ja v njegovega naslednika. V matematiki ne ˇzelimo defi- nirati vrednosti spremenljivke veˇc kot enkrat v kakrˇsnihkoli pogojih, saj to lahko vodi v zmedo; veliko trditev, ki so bile resniˇcne za staro vrednost spremenljivke, bi postale lahko napaˇcne in obratno.

Naravna ˇstevila Nˇzelimo definirati tako, da je 0 naravno ˇstevilo in da bodo naravna ˇstevila vse, kar lahko dobimo iz ˇstevila 0 s pomoˇcjo operacije naslednik. Od tako definiranih naravnih ˇstevil tudi zahte- vamo, da se bodo kot matematiˇcni objekt dovolj dobro ujemala z naˇso vnaprejˇsnjo intuicijo. To bomo storili tako, da bomo naravna ˇstevila vpeljali s pomoˇcjo Peanovih aksiomov:

P1 0 je naravno ˇstevilo.

P2 ˇCe jen naravno ˇstevilo, potem je tudin+ + naravno ˇstevilo.

P3 ˇStevilo 0 ni naslednik nobenega naravnega ˇstevila.

P4 Razliˇcni naravni ˇstevili imata razliˇcna naslednika.

P5 ˇCe neka znaˇcilnost P velja za ˇstevilo 0 in ˇce iz P(n) sledi P(n+ +) za vsako naravno ˇstevilo n, potem velja znaˇcilnost P za vsa naravna ˇstevila.

Naravna ˇstevila so sestavljena iz ˇstevila 0 in njegovih naslednikov:

0, 0 + +, (0 + +) + +, ((0 + +) + +) + +, itd. Takˇsen zapis pa je zelo okoren (hitro postane predolg), zato je dobro sprejeti dogovor in ˇstevila pisati v bolj primernem zapisu. Tako lahko definirajmo 1 kot

0 + + , 2 kot (0 + +) + +, 3 kot ((0 + +) + +) + +, itd. Seveda ˇcisto formalno ni jasno, kaj itd. pomeni, vendar se je v veˇcini kultur razvil naˇcin pisanja naravnih ˇstevil vse do precej velikih ˇstevil. Zavedati se moramo, da pri tem ne gre za nikakrˇsno vpeljavo novih pojmov, temveˇc le za vpeljavo simbolov, s katerimi ˇstevila zapiˇsemo v nekoliko krajˇsi, praviloma sistematiˇcni obliki.

V nadaljevanju bomo s pomoˇcjo virov [1], [3], [4] in [7] pogledali, kako vsak aksiom posebej vpliva na definicijo naravnih ˇstevil oziroma na lastnost naslednika. V tem poglavju se namenoma izogibamo poj- mom teorije mnoˇzic, saj bomo naravna ˇstevila kot mnoˇzico vpeljali v naslednjem poglavju. Vseeno pa bomo obˇcasno primere navajali v obliki mnoˇzic, da se izognemo pretiranemu zapletanju notacij. Tako naj bralec to poglavje razume ne kot povsem formalno obravnavo Peano- vih aksiomov, temveˇc raje kot pol formalno razlago, zakaj so Peanovi aksiomi dobra aproksimacija naˇse vnaprejˇsnje intuitivne predstave o naravnih ˇstevilih.

Vloga aksioma P1 je dokaj jasna. Poglejmo si primer trditve, ki jo lahko na primer dokaˇzemo le z uporabo aksiomov P1 in P2.

Trditev 2.1. 3 je naravno ˇstevilo.

Dokaz. Dokaˇzemo z aksiomoma P1 in P2. P1 pravi, 0 je naravno ˇstevilo. Po P2 je 1 = 0 + + naravno ˇstevilo. Ponovno, po P2, je 2 = 1++ naravno ˇstevilo. S ˇse zadnjo uporabo aksioma P2 je 3 = 2++

naravno ˇstevilo.

Zdi se, da je zgornja trditev, in s tem aksioma P1 in P2, dovolj, da definiramo naravna ˇstevila. Vendar se izkaˇze, da potrebujemo dodatne omejitve glede operacije naslednik. Poglejmo si primer.

Primer 2.2. Oglejmo si ˇstevilski sistem, ki je sestavljen iz ˇstevil in operacija naslednik (n+ +) poskrbi, da pridemo nazaj v ˇstevilo 0.

Ce na primer v mnoˇˇ zico A = {0,1,2,3} vpeljemo operacijo naslednik 1 = 0 + +, 2 = 1 + +, 3 = 2 + + in 3 + + = 0, bo mnoˇzica A skupaj s tako vpeljano operacijo naslednik zadoˇsˇcala aksiomoma P1 in P2.

Vsekakor pa to ni ˇstevilski sistem, ki ga razumemo kot naravna ˇstevila.

Kot smo videli v zgornjem primeru, aksioma P1 in P2 (brez doda- tnih aksiomov) dopuˇsˇcata, da se pri ˇstetju po konˇcno korakih vrnemo nazaj v ˇstevilo 0. To se ne more zgoditi, ˇce uporabimo ˇse aksiom P3.

Trditev 2.3. 4 ni enako 0.

Dokaz. Iz Trditve 2.1 sledi, da je 3 naravno ˇstevilo. Ker po P3 0 ni naslednik nobenega naravnega ˇstevila, ne velja 3 + + = 0. Torej

46= 0.

Vendar je ˇse kljub vsemu (kljub temu, da smo definirali P3) mogoˇce, da ˇstevilski sistem deluje na drugaˇcne naˇcine.

Primer 2.4. Oglejmo si ˇstevilski sistem s petimi ˇstevili pri katerih se operacija poveˇcevanja konˇca pri neki zgornji meji. Bolj natanˇcno, naj bo A = {0,1,2,3,4}, pri ˇcemer naj velja 1 = 0 + +, 2 = 1 + +, 3 = 2 + +, 4 = 3 + + in pa 4 + + = 4. To ni v nikakrˇsnem nasprotju z aksiomi P1, P2 in P3. Podobna ne bi bilo v nasprotju z aksiomi P1, P2 in P3, ˇce bi definirali 1 = 0 + +, 2 = 1 + +, 3 = 2 + +, 4 = 3 + + in pa 4 + + = 1. V obeh teh primerih velja med drugim 4 = 8. V prvem primeru zato, ker je 5 = 4 + + = 4, 6 = 5 + + = 4 + + = 4, 7 = 6++ = 5++ = 4++ = 4 in 8 = 7++ = 6++ = 5++ = 4++ = 4;

v drugem primeru pa, ker je 5 = 4 + + = 1, 6 = 5 + + = 1 + + = 2, 7 = 6 + + = 2 + + = 3 in 8 = 7 + + = 3 + + = 4.

Obstaja veliko naˇcinov, kako prepreˇciti zgornjo situacijo, pri ˇcemer je aksiom P4 verjetno eden bolj primernih moˇznosti. S pomoˇcjo P4 lahko dokaˇzemo na primer:

Trditev 2.5. 8 ni enako 4.

Dokaz. Dokaˇzimo s protislovjem. Recimo, da je 8 = 4. Potem je po aksiomu P4 7 = 3, nato 6 = 2, 5 = 1 in 4 = 0. To pa je ˇze v

nasprotju s Trditvijo 2.3.

Kot lahko vidimo iz zgornje trditve, je videti, da se vsa naravna ˇstevila med seboj razlikujejo. Vendar ˇse vedno obstaja en problem.

Ce upoˇstevamo le aksiome P1-P4, je mnoˇˇ zica naravnih ˇstevil lahko prevelika.

Primer 2.6. Poglejmo si nekoliko neformalno zapisano mnoˇzico A = {0,0.5,1,1.5,2,2.5, . . .}, torej ˇstevilski sistem, ki je sestavljen iz naravnih in poloviˇcnih ˇstevil. ˇCe v A definiramo operacijo naslednik kot 0++ = 1, 1++ = 2,. . .in 0.5++ = 1.5, 1.5++ = 2.5,. . ., mnoˇzica A skupaj s tako definirano operacijo zadoˇsˇca aksiomom P1-P4.

Potrebujemo torej dodaten aksiom, ki bo doloˇcal, da so edina ˇstevila v N tista, ki jih lahko pridobimo iz 0 z operacijo naslednik. To nam omogoˇca aksiom P5 oziroma princip matematiˇcne indukcije: Naj bo P(n) kakrˇsnakoli smiselna lastnost naravnega ˇstevila n. Predposta- vimo, da je res P(0) in da izP(n) slediP(n+ 1). Sledi da je P res za vsako naravno ˇstevilo. Oziroma povedano v jeziku mnoˇzic (naslednje poglavje), P5 pravi, da ˇce neka podmnoˇzica naravnih ˇstevil vsebuje 0 in z vsakim ˇstevilom tudi njegovega naslednika, je ta podmnoˇzica enaka mnoˇzici vseh naravnih ˇstevil. Za primer poglejmo, kako aksiom P5 razreˇsi teˇzavo iz primera 2.6. Vzemimo (zopet nekoliko neformalno) za lastnost P(n)n ni poloviˇcno ˇstevilo oziroma nekoliko bolj formalno, n = 0 ali n lahko dobimo iz 0 z veˇckratno uporabo operacije naslednik.

Jasno velja P(0), in tudiP(n+ +) sledi iz P(n). Torej lastnost P(n) velja za vsa naravna ˇstevila. Ker ta lastnost ne velja za poloviˇcna ˇstevila 0.5, 1.5,. . ., mnoˇzica A niso naravna ˇstevila.

Seveda je precej nejasno, kaj naj pomeni lastnost P. Nekateri pri- meri takˇsnih lastnosti so: je sodo ˇstevilo,je enak 3,reˇsi enaˇcbo in tako naprej. Precej teh konceptov ˇse nimamo definiranih, bomo pa nekatere od njih bolj natanˇcno definirali v nadaljevanju. Bolj formalno, vendar ˇ

ze v jeziku mnoˇzic, funkcij in izjavnega raˇcuna, biP pomenil katerokoli funkcijo P :N→ {>,⊥}, kjer>pomeni resnico,⊥pa neresnico, lahko pa P pomeni neko formulo znotraj logike drugega reda.

Opomba. Ker se aksiom P5 ne navezuje le na spremenljivke ampak tudi na lastnosti, je nekoliko drugaˇcne narave kot ostali ˇstirje aksiomi;

tako bi lahko aksiom P5 imenovali aksiomska shema namesto aksiom, saj je predloga za izdelavo (neskonˇcno) mnogo aksiomov, bolj kot za samostojen aksiom.

Princip matematiˇcne indukcije (aksiom P5) je zelo moˇcno orodje pri dokazovanju lastnosti naravnih ˇstevil. Predstavlja naˇcin za doka- zovanje, da neka lastnost velja za vsako naravno ˇstevilo. Tako bomo v nadaljevanju videli trditev oblike:

Trditev: Lastnost P(n) velja za vsako naravno ˇstevilon.

S pomoˇcjo matematiˇcne indukcije takˇsno trditev dokaˇzemo tako, da najprej dokaˇzemo bazo indukcije P(0), kar pomeni, da dokaˇzemo, da lastnost (formula, enakost,...) velja za ˇstevilo 0, nato pa s pomoˇcjo predpostavkeP(n) dokaˇzemoP(n+ +). Temu drugemu koraku reˇcemo indukcijski korak. Hitro lahko vidimo, zakaj je tak naˇcin dokazova- nja dobrodoˇsel: v vsakem primeru moramo dokazati, da lastnost P velja za vsa naravna ˇstevila n. Indukcijski korak nam dovoljuje, da pri dokazovanju, ˇce seveda potrebujemo, lahko uporabimo dejstvo, da lastnost velja za predhodnika ˇstevilan. V pomoˇc pri dokazovanju torej dobimo dodatno orodje.

Poglejmo si primer.

Primer 2.7. Za vsako naravno ˇstevilonvelja, da je 3²ⁿ−1 deljivo z 8, oziroma P(n)≡8|3²ⁿ−1. Uporabimo indukcijo.

1. baza indukcije: P(0)

3^2·0−1 = 1−1 = 0 Ker 8|0 velja P(0).

2. indukcijski korak: P(n) =⇒ P(n+ 1)

3^2·(n+1)−1 = 9·3²ⁿ−1 = 9(3²ⁿ−1) + 8 Po indukcijski predpostavki P(n), 8|3²ⁿ−1, zato

8|9(3²ⁿ−1) + 8, oziroma velja P(n+ 1) [10].

Opazite lahko, da naˇsa definicija naravnih ˇstevil ni konstruktivna, ampak aksiomatska. Nismo povedali, kaj naravna ˇstevila so, ampak smo naˇsteli nekaj lastnosti, ki jih smiselno priˇcakujemo od mnoˇzice, v kateri lahko ˇstejemo (P1-P4), skupaj z aksiomom P5, ki nam na nek naˇcin zagotovi, da so naravna ˇstevila najmanjˇsa taka mnoˇzica, v

kateri lahko obiˇcajno ˇstejemo. V bistvu smo naravna ˇstevila definirali kot objekt, v katerem ˇstejemo (poveˇcujemo ˇstevila za eno vrednost).

Kot bomo videli v nadaljevanju, ostale operacije, ki smo jih navajeni v naravnih ˇstevilih, lahko definiramo le z uporabo operacije naslednik. Za enkrat se pa ˇse nismo vpraˇsali, ali tak ˇstevilski sistem dejansko obstaja in kakˇsen matematiˇcni objekt naj to bo. V naslednjem poglavju bomo pokazali naslednji izrek.

Izrek 2.8. Obstaja mnoˇzicaNskupaj z operacijo naslednik, ki zadoˇsˇca vsem aksiomom P1−P5.

Opomba. Na ta ˇstevilski sistem, ki ga bomo pisali kot mnoˇzico N = {0,1,2, . . .}, bomo gledali kot na sistem naravnih ˇstevil. Seveda bi lahko obravnavali moˇznost, da obstaja veˇc kot en sistem naravnih ˇstevil, npr. lahko bi vzeli arabski ˇstevilski sistem in rimski ˇstevilski sistem in bi na te ˇstevilske sisteme gledali kot medsebojno razliˇcne.

V naslednjem poglavju bomo med drugim pokazali, da v primeru ko imamo dva modela naravnih ˇstevil, torej (A,0_A,++_A) in (B,0_B,++_B), kjer sta A, B mnoˇzici, 0_A ∈ A in 0_B ∈ B pripadajoˇca elementa 0, ter ++_A in ++_B pripadajoˇci operaciji naslednik v mnoˇzicahA inB, tako da so izpolnjeni aksiomi P1-P5, potem obstaja bijekcija

f :A→B, da velja

f(n+ +_A) = f(n) + +_B

za vsak element n ∈ A. Tako bomo rekli, da obstaja natanko ena mnoˇzica naravnih ˇstevil do izomorfizma, ki ohranja operacijo naslednik.

Opomba. (neformalno) Ena od zanimivih znaˇcilnosti mnoˇzice na- ravnih ˇstevil je, da je, ˇceprav je vsako posamezno naravno ˇstevilo konˇcno, mnoˇzica naravnih ˇstevil neskonˇcna. Da neskonˇcno velika na- ravna ˇstevila (kaj to formalno pomeni, bomo videli v nadaljevanju) ne obstajajo, lahko dokaˇzemo z uporabo aksioma P5. Kljub vsem tre- nutnim nejasnostim, je dokaz preprosto naslednji: ˇstevilo 0 je konˇcno ˇstevilo. Ce predpostavimo, da je naravno ˇsteviloˇ n konˇcno ˇstevilo, je tudi n + + konˇcno ˇstevilo. Torej so vsa naravna ˇstevila konˇcna.

Naravna ˇstevila se lahko pribliˇzajo neskonˇcnosti, vendar je ne morejo

doseˇci, kajti neskonˇcnost ni eno od naravnih ˇstevil. Obstajajo pa drugi sistemi ˇstevil, ki dopuˇsˇcajo neskonˇcna ˇstevila. To so npr. kardinalna ˇstevila, ordinalna ˇstevila in p-adiˇcna ˇstevila.

2.2. Rekurzivno definirana zaporedja

Peanov aksiom P5 nam omogoˇca, da rekurzivno definiramo zapo- redja naravnih ˇstevil.

Trditev 2.9 (Rekurzivne definicije). Predpostavimo, da imamo za vsako naravno ˇstevilo n neko funkcijo f_n :N → N iz naravnih ˇstevil v naravna ˇstevila. Naj bo c neko naravno ˇstevilo. Nato lahko vsakemu naravnemu ˇstevilu n doloˇcimo natanko eno naravno ˇstevilo a_n, tako da velja a₀ =cin a_n++=f_n(a_n).

Dokaz. Uporabimo indukcijo. Najprej opazimo, da lahko an defi- niramo pri n= 0, s tem da je a₀ =c. Sedaj predpostavimo, da imamo definirano vrednosta_n, in definiramoa_n++ =f_n(a_n) (iz aksiomov P3 in P4 sledi, da vrednosti a₀, a₁,· · · , a_ns tem ne spremenimo). To zakljuˇci indukcijo in tako je a_n enoliˇcno definiran za vsako naravno ˇstevilo.

Opazimo lahko, da je bilo potrebno uporabiti vse aksiome. V sis- temu ˇstevil, ki bi vseboval neke vrste zanko, rekurzivne definicije ne bi delovale, saj bi rekurzija lahko doloˇcene elemente preoblikovala za nazaj. ˇCe bi na primer veljalo 3 + + = 0, bi tako rekurzija zahtevala dve (morda) razliˇcni vrednosti a₀, in sicer cin f₃(a₃).

Rekurzivne definicije so moˇcno orodje. Uporabimo jih na primer lahko za definiranje seˇstevanja in mnoˇzenja, ˇcemur se bomo zdaj po- svetili [4] in [11].

2.3. Seˇstevanje naravnih ˇstevil

Sistem naravnih ˇstevil je v tem trenutku ˇse zelo pomanjkljiv. Imamo le eno operacijo – naslednik (poveˇcevanje) – in nekaj aksiomov. V tem poglavju bomo s pomoˇcjo vira [4] v naravna ˇstevila vpeljali ˇse operacijo seˇstevanje.

Seˇstevanje deluje po naslednjem sistemu. Popolnoma enako je, ˇce dodamo tri k pet ali pet k tri. Je pa to en korak veˇc, kot ˇce bi dodali

dva k pet, kar je en korak veˇc, ˇce bi dodali ena k pet in ˇse en korak veˇc ˇ

ce bi dodali niˇc k pet. Seˇstevanje definiramo rekurzivno.

Definicija 2.10 (Seˇstevanje naravnih ˇstevil). Naj bo m naravno ˇ

stevilo. ˇCe dodamo 0 k m, to definiramo kot m+ 0 := m. Nadalje rekurzivno definiramo m+ (n+ +) := (m+n) + +.

Kar smo definirali, je operacija priˇstevanja poljubnega naravnega ˇstevila n k danemu naravnemu ˇstevilu m, in to oznaˇcimo z m +n.

Bolj formalno, v obliki rekurzivno definiranih zaporedij iz prejˇsnjega poglavja, smo danemu naravnemu ˇstevilu m priredili rekurzivno zapo- redje a_n s predpisom a₀ =m ina_n++ =f_n(a_n), kjer so f_n:N→Nvse enakef_n(k) =k+ + za vsakk izN. Vsotom+npotem definiramo kot m+n = a_n. Nikakor pa na prvi pogled ni jasno, ali nam priˇstevanje n k m da isto naravno ˇstevilo kot priˇstevanje m k n, oziroma, ali velja m+n =n+m.

Primer 2.11. Izraˇcunajmo 3 + 5. Po definiciji seˇstevanja velja 3 + 0 = 3

3 + 1 = (3 + 0) + + = 3 + + = 4 3 + 2 = (3 + 1) + + = 4 + + = 5 3 + 3 = (3 + 2) + + = 5 + + = 6 3 + 4 = (3 + 3) + + = 6 + + = 7 3 + 5 = (3 + 4) + + = 7 + + = 8.

Torej je 3 + 5 = 8. Izraˇcunajmo ˇse 5 + 3:

5 + 0 = 5

5 + 1 = (5 + 0) + + = 5 + + = 6 5 + 2 = (5 + 1) + + = 6 + + = 7 5 + 3 = (5 + 2) + + = 7 + + = 8.

Opazimo priˇcakovano 5 + 3 = 8 = 3 + 5.

2.4. Lastnosti seˇstevanja

V naslednjih treh razdelkih povzemamo predvsem po [2], [4] in [7].

V tem trenutku vemo le dve dejstvi o seˇstevanju in sicer m+ 0 =m in m+ (n+ +) = (m+n) + +. Presenetljivo se izkaˇze, da sta ti dve dejstvi dovolj, da izpeljemo vse ostale lastnosti (seveda s pomoˇcjo Peanovih aksiomov), ki jih poznamo o seˇstevanju. Omenimo na tem mestu, da nekateri avtorji ti dve lastnosti seˇstevanja privzamejo med aksiome naravnih ˇstevil. Pri naslednji trditvi se spomnimo, da ˇse nismo dokazali komutativnosti seˇstevanja, in da rezultat ne sledi povsem oˇcitno iz dejstva n+ 0 =n.

Trditev 2.12. Za vsako naravno ˇstevilo n velja 0 +n=n.

Dokaz. Uporabili bomo indukcijo. Baza indukcije 0 + 0 = 0 sledi iz definicije. Sedaj lahko induktivno predpostavimo, da je 0 +n = n in pokaˇzimo, da velja tudi 0 + (n + +) = n+ +. Iz definicije sledi 0 + (n + +) = (0 +n) + + = n + +, kjer smo pri drugem enaˇcaju uporabili indukcijsko predpostavko. S tem zakljuˇcimo indukcijo.

Lema 2.13. Za vsaki dve naravni ˇstevilim in n velja(m+ +) +n = (m+n) + +.

Dokaz. Ponovno ne moremo kar direktno sklepati, da trditev sledi izn+ (m+ +) = (n+m) + +, saj nimamo komutativnosti. Uporabimo indukcijo na spremenljivko n (m se torej ne spreminja). Najprej nare- dimo bazo indukcije. V tem primeru moramo dokazati (m+ +) + 0 = (m+ 0) + +. Ampak po definiciji seˇstevanja je (m+ +) + 0 =m+ + in m+ 0 =m, zato je (m+ +) + 0 = (m+ 0) + +.

Sedaj predpostavimo, da je (m+ +) +n = (m+n) + + in dokaˇzimo (m + +) + (n + +) = (m+ (n + +)) + +. Iz definicije sledi (m + +) + (n+ +) = ((m+ +) +n) + +, iz indukcijske predpostavke pa (m++)+n = (m+n)++. Zato je (m++)+(n++) = ((m+n)++)++.

Ker pa je po definiciji seˇstevanja (m+n) + + enako m+ (n+ +), smo

s tem zakljuˇcili indukcijo.

Kot posebno posledico Trditve 2.12 in Leme 2.13 lahko opazimo, da velja 1 +n=n+ +.

Trditev 2.14 (Zakon komutativnosti). Za vsak par naravnih ˇstevil m in n velja m+n=n+m.

Dokaz. Uporabili bomo indukcijo nan (m se torej ne spreminja).

Vemo ˇze, da veljam+ 0 = 0 +m, saj to sledi iz definicije seˇstevanja ter Trditve 2.12. Predpostavimo sedaj, da veljam+n =n+min dokaˇzimo m+ (n+ +) = (n+ +) +m. Po definiciji seˇstevanja je m+ (n+ +) enako (m+n) + +, po Lemi 2.13 pa je (n+ +) +m = (n+m) + +.

Rezultat sedaj sledi iz indukcijske predpostavke.

Trditev 2.15 (Zakon asociativnosti).Za katerakoli naravna ˇstevila l, m, n velja (l+m) +n =l+ (m+n).

Dokaz. Fiksirajmo l inm ter naredimo indukcijo po n. Pri n= 0 imamo (l + m) + 0 = l +m in l + (m + 0) = l +m iz definicije seˇstevanja. Predpostavimo sedaj (l+m) +n =l+ (m+n) in dokaˇzimo (l+m) + (n+ +) =l+ (m+ (n+ +)).Iz definicije seˇstevanja sledi

(l+m) + (n+ +) = ((l+m) +n) + + in

l+ (m+ (n+ +)) =l+ ((m+n) + +) = (l+ (m+n)) + +.

S tem je dokaz zakljuˇcen.

S tem smo pokazali, da so naravna ˇstevila za seˇstevanje komuta- tivna polgrupa z enoto, oziroma komutativni monoid, saj velja komuta- tivnost, asociativnost in m+ 0 = 0 +m=m. Pokaˇzimo, da v naravnih ˇstevilih za operacijo seˇstevanje velja pravilo krajˇsanja (v sploˇsnem pra- vilo krajˇsanja ne velja v polgrupah).

Trditev 2.16 (Pravilo krajˇsanja). Naj bodol, m, n naravna ˇstevila in naj velja l+n=m+n. Potem je l =m.

Dokaz. Uporabimo indukcijo na n. Pri n= 0 trditev oˇcitno sledi iz definicije seˇstevanja. Predpostavimo sedaj, da iz l+n =m+n sledi l =m in naj bo l+ (n+ +) =m+ (n+ +).Velja

l+ (n+ +) = (l+n) + +

in

m+ (n+ +) = (m+n) + +.

Torej je

(l+n) + + = (m+n) + +, in zato po aksiomu P4

l+n=m+n.

Po indukcijski predpostavki je l =m.

Definicija 2.17. Naravno ˇstevilo n je pozitivno, ˇce je n 6= 0.

Lema 2.18. Naj bo n pozitivno naravno ˇstevilo. Potem obstaja natanko eno naravno ˇstevilo m, da je n =m+ +.

Dokaz. Trditev, ki jo bomo pokazali s pomoˇcjo indukcije je: Za vsako naravno ˇstevilo n obstaja natanko eno naravno ˇstevilo m, da je n = m+ +, ali pa je n = 0. Baza indukcije je oˇcitna, saj je 0 = 0.

Predpostavimo sedaj, da trditev velja za ˇstevilo n, in dokaˇzimo, da trditev velja za n+ +. To je oˇcitno, saj je n+ + =n+ +, enoliˇcnost

pa sledi iz aksioma P4.

Trditev 2.19. Naj bo m pozitivno naravno ˇstevilo in n naravno ˇ

stevilo. Potem je m+n pozitivno naravno ˇstevilo.

Dokaz. Ker jem pozitivno naravno ˇstevilo, obstaja (natanko eno) naravno ˇstevilok, da veljam=k+ +. Potem je m+n= (k+ +) +n = (k+n) + +.Torej jen+m naslednik nekega naravnega ˇstevila in zato

po P3 m+n6= 0.

Skupaj s komutativnostjo lahko to trditev preuredimo v

Posledica 2.20. Ce staˇ m in n naravni ˇstevili in velja m+n = 0, potem sta tako m kot n enaka 0.

2.5. Urejenost naravnih ˇstevil

Definicija 2.21. Naj bosta m in n naravni ˇstevili. Pravimo, da je m manjˇsi ali enak n, zapiˇsemo m ≤ n, ˇce je n = m+k za neko naravno ˇstevilo k. Nadalje reˇcemo, da je m strogo manjˇsi odn, piˇsemo m < n, ˇce m6=n in m ≤n

Tako je na primer 3 <8, ker je 8 = 3+5 in 5 6= 0. ˇCe jem≤n, lahko reˇcemo tudi, da je n veˇcji ali enak m, in zapiˇsemon ≥m. Podobno za strogo veˇcji. Tako je na primer 8>3.

Za vsako naravno ˇstevilo n velja 0 +n. Torej je n ≥ 0 za vsako naravno ˇstevilo in n > 0 natanko tedaj, ko n 6= 0 (torej je pozitivno ˇstevilo). Vidimo lahko tudi, da jem < nnatanko tedaj, ko je m+ +≤ n.

Iz definicije tudi takoj sledi, da ne obstaja najveˇcje naravno ˇstevilo, saj je n+ +> n za vsako naravno ˇstevilo n, ker je n+ + =n+ 1.

Trditev 2.22 (Osnovne lastnosti urejenosti). Relacija ≤ zadoˇsˇca naslednjim lastnostim.

(i) Refleksivnost: n ≤n za vsako naravno ˇstevilo n.

(ii) Tranzitivnost: ˇce je l≤m in m≤n je l ≤n.

(iii) Antisimetriˇcnost: ˇce je m≤n in n ≤m je m=n.

(iv) Stroga sovisnost: za poljubni dve naravni ˇstevili m, nveljan ≤ m ali m≤n.

Dokaz. Refleksivnost sledi iz n =n+ 0. Pokaˇzimo tranzitivnost.

Velja m = l+j in n = m+k, kjer sta j in k naravni ˇstevili. Potem je n= (l+j) +k =l+ (j+k) zaradi asociativnosti seˇstevanja. Torej je l≤ n. Pokaˇzimo antisimetriˇcnost. Po predpostavki je n =m+j in m =n+k. Torej jen = (n+k)+j =n+(k+j), torejn+0 =n+(k+j).

Pravilo krajˇsanja nam pove, da je k +j = 0 in zato k = 0 in j = 0 (Posledica 2.20). Zato je n = m. Strogo sovisnost bomo pokazali z indukcijo nan(mfiksirajmo). ˇCe jen = 0 velja 0≤m. Predpostavimo sedaj, da zan veljan ≤malim ≤n in pokaˇzimo, da veljan+ +≤m ali m ≤n+ +. ˇCe velja n ≤m, potem je bodisi n=m ali pa n < m.

V prvem primeru je n+ + =m+ 1≥m, v drugem pa n+ +≤m. ˇCe velja m≤n, potem je m≤n+ +. S tem je trditev dokazana.

V zgornji trditvi smo refleksivnost napisali kot posebno lastnost, vendar direktno sledi iz stroge sovisnosti. Prav tako iz stroge sovistnosti lahko hitro izpeljemo tudi trihotomijo: za vsaki naravni ˇstevili m in n velja bodisi m < n bodisi m = n bodisi m > n. Zgornja trditev nam pove, da je urejenost na naravnih ˇstevili linearna urejenost oziroma totalna urejenost.

Trditev 2.23 (Povezava med seˇstevanjem in urejenostjo). Naj bo m ≤n in l poljubno naravno ˇstevilo. Potem je m+l ≤n+l.

Dokaz. Dokaz takoj sledi iz opazke n = m +k =⇒ n +l =

(m+l) +k.

2.6. Mnoˇzenje naravnih ˇstevil

V tem razdelku bomo v naravna ˇstevila vpeljali ˇse operacijomnoˇzenje.

Tako kot seˇstevanje je tudi mnoˇzenje definirano rekurzivno.

Definicija 2.24 (Mnoˇzenje naravnih ˇstevil). Naj bo m naravno ˇ

stevilo. Mnoˇzenje ˇstevila m z 0 definiramo kot m·0 = 0. Rekurzivno definiramo m·(n+ +) =m·n+m.

Podobno kot pri seˇstevanju si poglejmo, zakaj je zgornja definicija smiselna. Mnoˇzenje ˇstevila m z naravnimi ˇstevili definiramo preko rekurzivnega zaporedjaa_n, ki je definirano kota₀ = 0 ina_n++=f_n(a_n), kjer je f_n : N → N definirana z f_n(k) = k +n. Nato definiramo m·n=a_n.

Primer 2.25. Izraˇcunajmo 3·5. Po definiciji mnoˇzenja velja 3·0 = 0

3·1 = (3·0) + 3 = 0 + 3 = 3 3·2 = (3·1) + 3 = 3 + 3 = 6 3·3 = (3·2) + 3 = 6 + 3 = 9 3·4 = (3·3) + 3 = 9 + 3 = 12 3·5 = (3·4) + 3 = 12 + 3 = 15.

Torej je 3·5 = 15. Izraˇcunajmo ˇse 5·3:

5·0 = 0

5·1 = (5·0) + 5 = 0 + 5 = 5 5·2 = (5·1) + 5 = 5 + 5 = 10 5·3 = (5·2) + 5 = 10 + 5 = 15.

Opazimo priˇcakovano 5·3 = 15 = 3·5.

Definirajmo ˇse potenciranje naravnih ˇstevil.

Definicija 2.26. Naj bo m naravno ˇstevilo. Naj bo an rekurzivno definirano zaporedje a₀ = 1 in a_n+1 = f_n(a_n), kjer je f_n : N → N definirana kot f_n(k) = k·m. Definiramo n-to potenco ˇstevila m kot mⁿ:=a_n.

Primer 2.27. Poglejmo si 5³. 5⁰ = 1

5¹ = 5⁰·5 = 1·5 5² = 5¹·5 = (1·5)·5 5³ = 5²·5 = ((1·5)·5)·5.

V nadaljevanju bomo videli, da so oklepaji, ki smo jih pisali, nepotrebni (asociativnost), da je 1·5 = 5, in da je zato zapis 5³ = 5·5·5 povsem smiseln.

2.7. Lastnosti mnoˇzenja

Trditev 2.28 (Komutativnost mnoˇzenja). Naj bosta m in n na- ravni ˇstevili. Potem velja m·n =n·m.

Dokaz. Pokaˇzimo najprej z indukcijo, da je 0·m = 0 za vsako naravno ˇstevilo m. Seveda je res za m= 0, in predpostavimo, da velja 0·m = 0. Potem je 0·(m+ +) = (0·m) + 0 = 0 + 0 = 0.

Pokaˇzimo sedaj, tokrat z indukcijo pom, da velja (n+ +)·m= (n· m)+m.Prim = 0 je izjava resniˇcna. Naj velja (n++)·m = (n·m)+m in dokaˇzimo (n+ +)·(m+ +) = (n·(m+ +)) + (m+ +).

(n+ +)·(m+ +) = ((n+ +)·m) + (n+ +)

= (n·m) +m+ (n+ +)

= (n·m) +n+ (m+ +)

= (n·(m+ +)) + (m+ +).

Sedaj smo pripravljeni, da z indukcijo po n dokaˇzemo, da velja m · n = n · m pri danem poljubnem m. Velja m ·0 = 0 ·m = 0.

Predpostavimo m·n =n·m in pokaˇzimo m·(n+ +) = (n+ +)·m.

Velja

m·(n+ +) = (m·n) +m= (n·m) +m.

Po drugi strani pa je prav tako

(n+ +)·m= (n·m) +m,

kot smo videli zgoraj.

Iz komutativnosti in definicije mnoˇzenja dobimo

Trditev 2.29 (Obstoj enote za mnoˇzenje). Za vsako neniˇcelno naravno ˇstevilo n velja n·1 = 1·n=n.

V nadaljevanju bomo upoˇstevali, da ima mnoˇzenje prednost pred seˇstevanjem, in si s tem prihranili nekaj pisanja oklepajev.

Trditev2.30 (Distributivnost). Za vsa naravna ˇstevilal, m, nimamo (l+m)·n=l·n+m·n.

Dokaz. Pokaˇzimo z indukcijo po n. Ker velja (l+m)·0 = 0 in l·0 +m·0 = 0, imamo bazo indukcije. Predpostavimo (l+m)·n = l·n+m·n in dokaˇzimo (l+m)·(n+ +) =l·(n+ +) +m·(n+ +).

Velja

(l+m)·(n+ +) = (l+m)·n+l+m

=l·n+m·n+l+m

=l·n+l+m·n+m

=l·(n+ +) +m·(n+ +),

kar je enako desni strani. S tem je trditev dokazana.

Trditev 2.31 (Asociativnost mnoˇzenja). Za vsaka naravna ˇstevila l, m, n velja (l·m)·n=l·(m·n).

Dokaz. Pokaˇzimo z indukcijo pon. Za n = 0 sta obe strani enaki 0. Predpostavimo sedaj, da velja (l·m)·n = l·(m·n) in dokaˇzimo (l·m)·(n+ +) =l·(m·(n+ +)). Leva stran je enaka

(l·m)·(n+ +) = (l·m)·n+ (l·m)

=l·(m·n) + (l·m),

desna pa

l·(m·(n+ +)) =l·(m·n+m) l·(m·n) +l·m.

Torej sta obe strani enaki.

Trditev 2.32 (Naravna ˇstevila nimajo deliteljev niˇca). Naj bosta m in n naravni ˇstevili. Potem je m·n = 0 natanko tedaj, ko je vsaj eden od m ali n enak 0.

Dokaz. Naj bo m neniˇcelno. Pokazati moramo, da je m·n = 0 natanko tedaj, ko je n = 0. Recimo, dan 6= 0. Potem je n =l+ + za nek l. Zato je

m·n=m·(l+ +) = (m·l) +m≥m >0.

Posledica2.33 (Pravilo krajˇsanja).Naj bodol, m, nnaravna ˇstevila in l 6= 0. ˇCe velja m·l =n·l, potem je m=n.

Poglejmo si ˇse, kako sta povezani operacija mnoˇzenja in relacija urejenosti.

Trditev 2.34 (Povezava med mnoˇzenjem in urejenostjo). Ce staˇ l in m naravni ˇstevili in je l ≤ m ter m naravno ˇstevilo, potem velja l·n ≤m·n.

Dokaz. Dokaˇzimo z indukcijo po n. Prin = 0 dobimol ≤m =⇒ 0≤0.Predpostavimo, da trditev velja pri n in jo dokaˇzimo pri n+ +:

l·(n+ +) =l·n+l≤m·n+m=m·(n+ +).

Opomba. Povedali smo ˇze, da so naravna ˇstevila komutativni mo- noid brez deliteljev niˇca za operacijo seˇstevanje. V tem razdelku smo pokazali, da so neniˇcelna naravna ˇstevila tudi komutativni monoid brez deliteljev niˇca za operacijo mnoˇzenja. Skupaj z distributivnostnim za- konom dobimo, da so naravna ˇstevila komutativni polkolobar brez de- liteljev niˇca. Lastnosti operacije ≤ (v povezavi s + in ·) nam povedo, da so naravna ˇstevila linearno urejen polkolobar.

2.8. Odˇstevanje in deljenje v naravnih ˇstevilih

Odˇstevanje in deljenje lahko le delno definiramo v naravnih ˇstevilih [4].

Definicija 2.35. Naj bo m≤n. Potem definiramo n−m kot tisto naravno ˇstevilo k, za katerega velja n =m+k.

Da je zgornja definicija dobra, se lahko hitro prepriˇcamo. m≤npo definiciji pomeni, da obstaja tako ˇstevilok, da jen =m+k. Preverimo ˇse, da je tako ˇstevilo eno samo. Naj bo tudi n = m+l. Potem nam pravilo krajˇsanja pove, da je l =k. Pravilo krajˇsanja je torej tisto, ki nam omogoˇca, da delno definiramo operacijo odˇstevanja. Podobno je z deljenjem, le da v tem primeru ni tako enostavno povedati, kdaj je le to definirano.

Definicija 2.36. Naj bosta m in n taki naravni ˇstevili, da je n = k ·m za neko naravno ˇstevilo k. Predpostavimo nadalje, da n 6= 0.

Potem definiramo n/m:=k.

Da je ta definicija dobra, ugotovimo s pomoˇcjo pravila krajˇsanja, tokrat seveda za mnoˇzenje.

Naslednja trditev nam pove, da v naravnih ˇstevilih lahko vedno definiramo operacijo deljenje z ostankom.

Trditev 2.37 (Osnovni izrek o deljenju). Naj bomnaravno ˇstevilo in n pozitivno naravno ˇstevilo. Potem obstajata enoliˇcno doloˇceni na- ravni ˇstevili k in l, l < n, da velja m=k·n+l.

Dokaz. Pokaˇzimo najprej enoliˇcnost. Predpostavimo, da obsta- jajo ˇstevilak, l, k⁰, l⁰ da veljam=k·n+linm=k⁰·n+l⁰, pri ˇcemer je l, l⁰ < n. ˇCe veljak =k⁰ takoj vidimo, da je tudil =l⁰. Predpostavimo torej, da je k⁰ > k. Potem mora veljati (k⁰ −k)n+l⁰ = l. Ker pa je (k⁰−k)n+l⁰ ≥n, to ni mogoˇce.

Pokaˇzimo sedaj s pomoˇcjo indukcije po m ˇse obstoj. ˇCe je m = 0, je k = 0 in l = 0 za vsak n > 0. Naj bo sedaj m = kn+l. Potem je m+ 1 = kn+ (l + 1). ˇCe je l + 1< n, smo konˇcali. Ker je l < n, je moˇzno le ˇse l+ 1 =n. V tem primeru je m+ 1 = (k+ 1)n+ 0.

POGLAVJE 3

Mnoˇ zice

Intuitivno kot mnoˇzico razumemo skupek nekih reˇci, kot na pri- mer mnoˇzica otrok na igriˇsˇcu, mnoˇzica galebov, mnoˇzica racionalnih ˇ

stevil,... Pojem mnoˇzice je nekaj, kar smo si izmislili, da si laˇzje pred- stavljamo stvari in o njih govorimo. Je abstrakten pojem, ki pa zahteva bolj natanˇcno definicijo.

Utemeljitelj teorije mnoˇzic, Georg Cantor je pojem mnoˇzice defi- niral kot:“Mnoˇzica je skupek doloˇcenih, razliˇcnih stvari iz naˇsega na- zornega ali miselnega sveta, ki ga imamo za celoto.” Ampak teˇzava te ‘definicije’ je, da nas hitro pripelje do protislovij. Enega je opa- zil Bertrand Russel leta 1902. Po Cantorju bi morala obstajati tudi mnoˇzica vseh mnoˇzic, recimo ji U. Vzemimo tisto njeno podmnoˇzico A, ki je sestavljena iz vseh tistih mnoˇzic B, ki niso vsebovane same v sebi. Torej

A={B ∈U; B 6∈B}.

Imamo dve moˇznosti in sicer, da je A vsebovana v A, ali pa da A ni vsebovana v A. ˇCeA je elementA, potem iz definicije mnoˇziceAsledi, da A ni element mnoˇzice A. ˇCe pa A ni vsebovana v A, pa iz defini- cije mnoˇzice A sledi, da A je element mnoˇzice A. Torej pridemo do paradoksa. Kot bomo videli kasneje, paradoks izhaja iz preveˇc ohla- pne definicije pojma mnoˇzica. Sama definicija mnoˇzice A ni toliko problematiˇcna, saj bo eden od aksiomov teorije mnoˇzic dopuˇsˇcal, da lahko naredimo bolj ali manj poljubno podmnoˇzico dane mnoˇzice. Pro- blem je bolj v tem, da je A definirana kot podmnoˇzica “mnoˇzice vseh mnoˇzic”. ˇCe torej dopustimo, da lahko dokaj poljubno gradimo pod- mnoˇzice, moramo biti precej bolj restriktivni pri tem, katere objekte bomo imenovali mnoˇzice.

V nadaljevanju bomo predstavili sistem aksiomov ZFC teorije mnoˇzic.

Ta sistem aksiomov se imenuje po matematikih Ernstu Zermelu in

Abrahamu Fraenkelu, in je eden izmed najbolj uporabljenih aksiomat- skih modelov teorije mnoˇzic. Simbol C pomeni, da bomo v teorijo privzeli ˇse aksiom izbire. Sistem aksiomov, predvsem aksiom o ne- skonˇcnosti, bomo nato uporabili pri konstrukciji modela naravnih ˇstevil kot mnoˇzice. Podobno kot v prejˇsnjem poglavju, bo tudi v tem poglavju obravnava aksiomov precej neformalna, ˇse posebej pri navajanju pri- merov. Prav tako bomo za laˇzje razumevanje dodali nekaj aksiomov, ki bi jih sicer lahko izpeljali kot posledice ostalih aksiomov. Pri pisanju tega poglavja se bomo predvsem naslonili na [2], [4] in [6].

3.1. ZFC aksiomi

Celotna teorija mnoˇzic temelji na pojmu biti element oziroma na odnosu pripadnosti. ˇCe je neka reˇc x element mnoˇzice A, to zapiˇsemo kot x ∈ A. Edini objekti, ki jih bomo obravnavali pri tej teoriji so mnoˇzice. Zato bodo tudi elementi mnoˇzic lahko le mnoˇzice same. Zato bodo mnoˇzice vˇcasih oznaˇcene z malimi tiskanimi, vˇcasih pa z velikimi tiskanimi ˇcrkami. Z malimi predvsem takrat, ko jih ˇzelimo gledati le kot elemente veˇcje mnoˇzice. To je sicer nekoliko ne intuitivno, vendar nam omogoˇca bolj ˇcisto teorijo. Vseeno pa bomo vˇcasih v primerih za laˇzje razumevanje pisali nekoliko neformalno npr. {1,2,3}. Ker pa bomo ob koncu poglavja naravna ˇstevila opisali kot mnoˇzice, bo tudi s povsem formalnega staliˇsˇca to v redu.

Povejmo najprej, kdaj sta dve mnoˇzici enaki. Enakost dveh mnoˇzic AinBv sploˇsnem oznaˇcimo s simbolom =, torejA=B. ˇCe pa mnoˇzici A inB nista enaki, to zapiˇsemo kot A 6=B. Enakost mnoˇzic vpeljemo z naslednjim aksiomom.

Aksiom 3.1 (Aksiom o ekstenzionalnosti). Dve mnoˇzici Ain B sta enaki natanko tedaj, ko imata natanko iste elemente. Torej

∀A∀B :∀x(x∈A ⇐⇒ x∈B)⇒A=B.

Primer 3.2. Imamo mnoˇzico A = {1,2,3} , ki jo vsi prav dobro poznamo. Tudi B = {n ∈ N : 1 ≤ n ≤ 3} je mnoˇzica. ˇCeprav na prvi pogled zgleda, da A in B nimata niˇc skupnega, po aksiomu o ekstenzionalnosti velja A=B. Aksiom o ekstenzionalnosti pravzaprav vpeljuje pojem enakosti. Pravi, da za mnoˇzico ni prav niˇc pomembno,

kako smo opisali elemente. Pomembno je le, kateri elementi to so. Prav tako ni pomembno, ˇce se pri naˇstevanju elementi ponavljajo, oziroma kakˇsen je njihov vrstni red. Torej{1,2,3}={1,3,2}={1,2,1,3,1,2}.

Z naslednjim aksiomom bomo vpeljali prazno mnoˇzico. Obstoj pra- zne mnoˇzice bi sicer lahko kasneje izpeljali iz ostalih aksiomov.

Aksiom 3.3 (Obstoj prazne mnoˇzice). Obstaja mnoˇzica ∅, ki ne vsebuje nobenega elementa. Torej

∃∅:∀x(x6∈ ∅).

Opomba. Po aksiomu o ekstenzionalnosti je prazna mnoˇzica ena sama, saj oˇcitno velja trditev

∀x(x6∈A∧x6∈B)⇒ ∀x(x∈A ⇐⇒ x∈B).

Veˇcina aksiomov v nadaljevanju nam pove, kako lahko iz ˇze ob- stojeˇcih mnoˇzic dobimo nove mnoˇzice.

Aksiom 3.4 (Aksiom o podmnoˇzici). Naj bo A dana mnoˇzica in L lastnost, ki je smiselna za elemente mnoˇzice A. Tedaj obstaja mnoˇzica B, ki sestoji iz natanko tistih elementov mnoˇzice A, ki imajo lastnost L. Bolj natanˇcno, naj bo L formula v teoriji mnoˇzic s prostimi spre- menljivkami x, w₁, . . . w_n, A. Potem velja

∀w1, . . . , wn∀A∃B∀x(x∈B ⇐⇒ (x∈A∧L(x, w1, . . . , wn, A))).

Opomba. Po aksiomu o ekstenzionalnosti je mnoˇzica B natanko doloˇcena z mnoˇzico A in lastnostjo L.

Vpeljimo sedaj ˇse formalni pojem podmnoˇzice.

Definicija 3.5. Ce staˇ A in B mnoˇzici, in je vsak element A tudi element B, potem reˇcemo, da je A podmnoˇzica B, oziroma B vsebuje A in to zapiˇsemo kot A⊂B ali B ⊃A.

Prazna mnoˇzica je seveda podmnoˇzica vsake mnoˇzice. Seveda je vsaka mnoˇzica tudi podmnoˇzica sama sebe. Relacija “biti podmnoˇzica”

je torej refleksivna. Prav tako je relacija tudi tranzitivna, saj velja (A ⊂ B) ∧(B ⊂ C) ⇒ A ⊂ C, in po aksiomu o ekstenzionalnosti antisimetriˇcna, torej (A ⊂ B)∧(B ⊂ A) ⇒ A =B. ˇCe imamo torej

neko mnoˇzico A, katere elementi so zopet mnoˇzice, nam relacija “biti podmnoˇzica” poda delno urejenost na A.

Aksiom 3.6 (Aksiom o paru). Naj bosta x in y poljubni mnoˇzici.

Tedaj obstaja mnoˇzica A, katere edina elementa sta x in y. Bolj na- tanˇcno

∀x∀y∃A(x∈A∧y ∈A).

Primer 3.7. Edina mnoˇzico, ki smo jo dosedaj spoznali, je prazna mnoˇzica∅. Poglejmo si, kako nam aksiom o paru omogoˇca, da zgradimo nove mnoˇzice. Naj boxpoljubna mnoˇzica. Potem je tudi{x}mnoˇzica, saj lahko vzamemo pri aksiomu o paru y=x. ˇCe vzamemo x=y=∅, dobimo mnoˇzico {∅}. ˇCe sedaj vzamemo x = ∅ in y = {∅} dobimo novo mnoˇzico {∅,{∅}}. S postopkom lahko nadaljujemo.

Aksiom 3.8 (Aksiom o uniji). Naj bo A poljubna mnoˇzica. Potem obstaja mnoˇzica A, katere elementi so natanko elementi, ki pripadajo vsaj eni od mnoˇzic iz A. Bolj formalno

∀A∃A∀Y∀x((x∈Y ∧Y ∈ A)⇒x∈A).

Po aksiomu o ekstenzionalnosti je taka mnoˇzica natanko doloˇcena z mnoˇzico A. Lahko jo oznaˇcimo zS

A. Ce je na primerˇ A={X, Y}, pa piˇsemo kar X∪Y. Podobno lahko piˇsemo pri vsaki konˇcni uniji.

Primer3.9. Podobno kot v prejˇsnjem primeru, lahko tudi s pomoˇcjo aksioma o uniji skonstruiramo nove mnoˇzice. Mnoˇzico {∅,{∅}} lahko dobimo kot unijo mnoˇzic {∅} in {{∅}}, vendar teh dveh mnoˇzic ne moremo dobiti brez aksioma o paru.

Zanimivo je, da za definicijo poljubnega preseka mnoˇzic ne potrebu- jemo dodatnega aksioma, ampak lahko presek definiramo ˇze s pomoˇcjo aksioma o podmnoˇzicah. Naj bo A neprazna mnoˇzica in Y poljuben element v A. Potem lahko presek mnoˇzic iz A dobimo kot

\A ={x∈Y :∀X(X ∈ A ⇒x∈X)}.

Podobno lahko vpeljemo razliko dveh mnoˇzic kot A\B ={x∈A:x /∈B}.

Aksiom 3.10 (Aksiom o zamenjavi). Naj bo A mnoˇzica. Za vsak x∈A in vsak element y naj bo P(x, y) izjava, ki je resniˇcna za najveˇc en element y. Potem obstaja mnoˇzica B, ki vsebuje natanko tiste ele- mente y, da je izjavaP(x, y) resniˇcna za vsaj nek element x∈A. Bolj formalno je izjava P formula v teoriji mnoˇzic s prostimi spremenljiv- kami x, y, w₁, . . . , w_n, A in velja

∀w1, . . . , wn∀A((∀x∈A∃!yP(x, y, w1, . . . , wn, A))

⇒ ∃B∀y(y∈B ⇐⇒ ∃x∈AP(x, y, w1, . . . , wn, A))).

Zgornji aksiom nam na primer omogoˇca, da iz mnoˇziceA={1,2,3}

naredimoB ={2,3,4}. To dobimo tako, da vzamemo izjavo y=x+ 1.

Seveda pa lahko to mnoˇzico naredimo tudi brez zgornjega aksioma.

Da se izognemo Russelovemu paradoksu, bomo od mnoˇzic zahtevali naslednji aksiom. Za dve mnoˇzici AinB reˇcemo, da sta disjunktni, ˇce ne vsebujeta nobenega skupnega elementa, torej

@x:x∈A∧x∈B.

Aksiom 3.11 (Aksiom o regularnosti). Vsaka neprazna mnoˇzicaA vsebuje element, ki je disjunkten z A.

Ta aksiom nam onemogoˇca, da bi bila mnoˇzica element same sebe.

Naj bo na primer mnoˇzica A poljubna mnoˇzica. Potem je A edini element mnoˇzice {A}, zato mora biti A disjunkten z {A}, kar pa po definiciji pomeni, daA6∈A. Aksiom nam tudi pove, da ni neskonˇcnega ugnezdenega zaporedja mnoˇzic in da za par mnoˇzic A in B ne more hkrati veljati, da je A∈B in B ∈A.

Aksiomi o prazni mnoˇzici, o podmnoˇzici, o uniji in o paru nam ˇ

ze omogoˇcajo, da iz prazne mnoˇzice gradimo poljubno velike ‘konˇcne’

mnoˇzice. Pravzaprav se izkaˇze, da so to edini aksiomi, ki jih potrebu- jemo, ˇce ˇzelimo operirati le s konˇcnimi mnoˇzicami. Ne omogoˇcajo pa nam ˇse, da bi zgradili kakrˇsnokoli neskonˇcno mnoˇzico, kot je na primer mnoˇzica naravnih ˇstevil.

Aksiom 3.12 (Aksiom neskonˇcnosti). Obstaja vsaj ena mnoˇzicaM, ki ima lastnosti

• prazna mnoˇzica ∅ je njen element: ∅ ∈M,

• ˇce je poljubna mnoˇzica x njen element, potem je mnoˇzica x∪ {x} tudi njen element: x∈M ⇒x∪ {x} ∈M.

Krajˇse

∃M(∅ ∈M ∧ ∀x∈M((x∪ {x})∈M)).

Kot bomo videli v nadaljevanju, je mnoˇzica M neskonˇcna. Zdi se, da je najmanjˇsa mnoˇzica, ki ustreza aksiomu o neskonˇcnosti, mnoˇzica

N={∅,{∅},{∅,{∅}},{∅,{∅},{∅,{∅}}}, ...}.

Potenˇcna mnoˇzica dane mnoˇziceAje mnoˇzicaP(A), katere elementi so natanko podmnoˇzice mnoˇziceA. ˇCeprav se izkaˇze, da lahko potenˇcne mnoˇzice konˇcnih mnoˇzic skonstruiramo brez dodatnih aksiomov, pa v sploˇsnem potrebujemo nov aksiom.

Aksiom 3.13 (Aksiom o potenˇcni mnoˇzici). Za vsako mnoˇzico A obstaja njena potenˇcna mnoˇzica P(A). Bolj natanˇcno

∀A∃P(A)∀B(B ∈P(A) ⇐⇒ ∀x(x∈B ⇒x∈A)).

Primer 3.14. Imamo mnoˇzico A = {1,2}. Poiˇsˇcimo P(A) in P(P(A))

P(A) = {∅,{1},{2},{1,2}}

P(P(A)) ={∅,{∅},{{1}},{{2}},{{1,2}},{∅,{1}},{∅,{2}},{∅,{1,2}}, {{1},{2}},{{1},{1,2}},{{2},{1,2}},{∅,{1},{2}},{∅,{1},{1,2}},

{∅,{2},{1,2}},{{1},{2},{1,2}},{∅,{1},{2},{1,2}}

Aksiom o potenˇcni mnoˇzici nam omogoˇca, da definiramo karteziˇcni produkt dveh mnoˇzic. Naj bosta A in B mnoˇzici, ter a ∈ A in b ∈ B elementa. Definirajmo mnoˇzico

(a, b) := {a,{a, b}}.

Ta mnoˇzica obstaja po aksiomu o paru. Karteziˇcni produkt ˇzelimo definirati kot mnoˇzico A×B, ki bo vsebovala natanko take pare (a, b).

Tako mnoˇzica {a} kot mnoˇzica {a, b} sta elementa mnoˇzice P(A∪B).

Zato je {a,{a, b}} ∈P(P(A∪B)) in lahko definiramo

A×B ={C ∈P(P(A∪B)) :∃a∈A∃b ∈B, C = (a, b)}.

Karteziˇcni produkt treh mnoˇzic A, B in C lahko definiramo kot (A× B)×C) in nato induktivno za vsak konˇcen karteziˇcni produkt.

Vsako podmnoˇzico R ⊂ A×B imenujemo dvoˇclena relacija med mnoˇzicama A in B. ˇCe je A = B, reˇcemo kar, da imamo relacijo na A. ˇCe je (a, b) ∈R piˇsemo tudi aRb. Domena relacije R ⊂ A×B je definirana kot mnoˇzica

{a∈A:∃b∈B,(a, b)∈R}, kodomena pa kot

{b∈B :∃a ∈A,(a, b)∈R}.

Za relacijo R ⊂A×B reˇcemo, da je levo totalna, ˇce je domena enaka mnoˇzici A. Relacija je funkcijska, ˇce za vsak a∈A velja

(a, b)∈R∧(a, c)∈R⇒b =c.

Definicija 3.15. Dvoˇclena relacija R ⊂ A×B je preslikava med mnoˇzicama A in B, ˇce je levo totalna in funkcijska.

Opomba. Naj bo R ⊂ A×B preslikava med A in B. Potem za vsak a∈Aobstaja natanko enb ∈B, da velja (a, b)∈R. ˇCe oznaˇcimo f(a) :=b, dobimo bolj obiˇcajen zapis za preslikavo, ki jo pogosto raje piˇsemo kot trojico f : A → B. V nadaljevanju bomo uporabljali tak zapis.

Preden nadaljujemo, si poglejmo ˇse definicijo ekvivalenˇcne relacije in kvocientne mnoˇzice.

Definicija 3.16. Dvoˇclena relacija ∼ na A je ekvivalenˇcna rela- cija, ˇce je refleksivna (∀a∈A(a∼a)), simetriˇcna (∀a, b∈A(a∼b ⇒ b ∼a)) in tranzitivna (∀a, b, c∈A(a∼b∧b∼c⇒a∼c)).

Ce jeˇ ∼ ekvivalenˇcna relacija na A in a ∈ A, lahko definiramo ekvivalenˇcni razred [a] = {b ∈ A : a ∼ b}. Za a, b ∈ A sta ekviva- lenˇcna razreda [a] in [b] bodisi enaka, bodisi disjunktna. Mnoˇzico A

lahko razbijemo na disjunktno unijo ekvivalenˇcnih razredov, oziroma, definiramo kvocientno mnoˇzico A/∼

A/∼={B ∈P(A) :∀a, b∈B∀c∈A((a∼b)∧(a ∼c⇒c∈B))}.

Naj bosta sedajI inAmnoˇzici in f :I → Apreslikava. ˇCe jei∈I piˇsimo A_i = f(i). Potem lahko definiramo karteziˇcni produkt druˇzine mnoˇzic iz A indeksirane s f kot

Y

i∈I

A_i ={g :I →[

A :∀i∈I, g(i)∈A_i}.

Karteziˇcni produkt dveh mnoˇzic AinB je prazna mnoˇzica natanko tedaj, ko je vsaj ena od njiju prazna mnoˇzica. Podobno lahko vidimo pri konˇcnem karteziˇcnem produktu. Pri poljubnem karteziˇcnem pro- duktu indeksirane druˇzine mnoˇzic pa moramo del te trditve postaviti kot aksiom.

Aksiom 3.17 (Aksiom izbire). Ce jeˇ A_i poljubna druˇzina nepraznih indeksiranih mnoˇzic, potem je karteziˇcni produkt te druˇzine neprazna mnoˇzica.

3.2. Konstrukcija naravnih ˇstevil

V tem razdelku bomo znotraj ZFC teorije mnoˇzic skonstruirali mo- del naravnih ˇstevil s pomoˇcjo vira [2] in [5]. Pokazali bomo naslednji izrek.

Izrek 3.18 (Obstoj naravnih ˇstevil). Obstaja mnoˇzicaN, za katero velja

P1 Prazna mnoˇzica je element mnoˇzice N,

∅ ∈N. Oznaˇcimo 0 :=∅.

P2 Za vsak n ∈ N, obstaja element n + + ∈ N, ki mu pravimo naslednik elementa n.

P3 V mnoˇzici N ni nobenega elementa, ki bi imela 0 za svojega neposrednega naslednika,

∀n∈N:n+ + 6= 0.

P4 ˇCe sta neposredna naslednika dveh elementov enaka, potem sta tudi ta dva elementa enaka,

∀n, m∈N((n+ + =m+ +)⇒n =m).

P5 ˇCe je S ⊂ N, tako da je 0 ∈ S in je za vsak n ∈ S tudi n+ +∈S, potem je S=N. Oziroma

(S ⊂N)∧(0∈S∧(∀n ∈S ⇒n+ +∈S))⇒S=N.

Dokaz. Naj bo Ω mnoˇzica, ki jo dobimo iz aksioma o neskonˇcnosti.

Za vsak n∈Ω oznaˇcimo

n+ + :=n∪ {n}.

Potem jen++∈Ω. Imenujmo podmnoˇzicoS ⊂Ω induktivna mnoˇzica, ˇ

ce velja ∅ ∈ S in n ∈ S ⇒ n + + ∈ S. Seveda je Ω induktivna mnoˇzica. Vse induktivne mnoˇzice so elementi potenˇcne mnoˇziceP(Ω), zato obstaja mnoˇzica S ={S∈P(Ω) :S induktivna}. Naj bo

N=\ S.

Poglejmo, da mnoˇzica N zadoˇsˇca aksiomom 1-5.

Aksiom 1. Ker je 0∈S za vsak S∈ S je 0∈N.

Aksiom 2. Naj bo n ∈ N. Potem je n ∈ S za vsak S ∈ S in zato n+ +∈S za vsakS ∈ S. Torej je n+ + ∈N.

Aksiom 3. Predpostavimo, da je 0 = m+ + za nek m ∈ N. Torej je

∅=m∪ {m}in zato m∈ ∅, kar pa ni moˇzno.

Aksiom 5. Pokazati moramo, da je vsaka induktivna podmnoˇzica N enaka N. To je oˇcitno, saj je N induktivna in je hkrati presek vseh induktivnih mnoˇzic.

Aksiom 4. Pokaˇzimo najprej, da za vsak n ∈N veljam ∈n ⇒m⊂n.

Naj bo S := {n ∈ N : (∀m ∈ n : m ⊂ n)}. Preverimo, da velja n ∈ S ⇒ (n∪ {n}) ∈ S. Naj bo m ∈ n∪ {n}. Potem je m ∈ n ali pa m =n. V obeh primerih je m ⊂n+ +. Mnoˇzica S je induktivna, saj je tudi 0 ∈ S. Torej je N ⊂ S. Ker pa je tudi S ⊂ N je S = N,

kar smo ˇzeleli pokazati. Naj bo sedaj n + + = m + +. Potem je n ∪ {n} = m∪ {m}. ˇCe m 6= n, potem {m} 6= {n}, kar pomeni, da mora veljati m ∈ n in n ∈m. Po zgornjem dobimo m ⊂ n inn ⊂m, kar pomeni m =n. Dobili smo protislovje.

Mnoˇzico naravnih ˇstevil smo torej skonstruirali kot najmanjˇso in- duktivno podmnoˇzico neke induktivne mnoˇzice, katere obstoj nam za- gotavlja aksiom o neskonˇcnosti. Sama naravna ˇstevila so seveda tudi mnoˇzice, in sicer 0 =∅, 1 ={∅}, 2 ={∅,{∅}}, 3 ={∅,{∅},{∅,{∅}},...

Operacija naslednik je definirana kot n+ + = n∪ {n}. Urejenost na- ravnih ˇstevil je v tem modelu podana kar kot m≤n ⇐⇒ m⊂n.

Spomnimo se, da je totalna urejenost ≤ na mnoˇzici M dobra ure- jenost, ˇce ima vsaka neprazna podmnoˇzica A⊂M najmanjˇsi element.

To je, obstaja tak a∈A, a≤b za vsakb ∈A. Najmanjˇsi elementAje zaradi antisimetriˇcnosti en sam.

Izrek 3.19. Mnoˇzica naravnih ˇstevil je dobro urejena.

Dokaz. Naj bo A neprazna podmnoˇzica naravnih ˇstevil. Potem obstaja naravno ˇstevilo b ∈ A. Naj bo a najmanjˇsi izmed ˇstevil {0,1, . . . , b} ki je tudi vA. Hitro vidimo, da je a najmanjˇsi element v

A.

3.3. Ekvipolenca mnoˇzic

Naslednji razdelek je napisan s pomoˇcjo [2], [9] in [13]. Naj bo f :A→B preslikava med mnoˇzicamaAinB. Preslikava jeinjektivna, ˇ

ce razliˇcne elemente slika v razliˇcne elemente, to je

∀x, y ∈A(x6=y⇒f(x)6=f(y))

in surjektivna, ˇce je kodomena preslikave cela mnoˇzica B. ˇCe je presli- kava injektivna in surjektivna, reˇcemo, da je bijektivna.

Definicija 3.20 (Ekvipolenca mnoˇzic). Mnoˇzici A in B sta ekvi- polentni, ˇce obstaja bijektivna preslikava f :A →B.

Seveda je vsaka mnoˇzica ekvipolentna sama sebi, ker za preslikavo lahko vzamemo kar identiteto. Prav tako velja tranzitivnost: ˇce je A

ekvipolentnaB inB ekvipolentnaC, jeAekvipolentnaC. Ekvipolenca je torej ekvivalenˇcna relacija.

Definicija 3.21 (Konˇcne mnoˇzice). Mnoˇzica A je konˇcna, ˇce je ekvipolentna nekemu naravnemu ˇstevilu n. V tem primeru reˇcemo, da ima mnoˇzica moˇc n. ˇCe mnoˇzica ni konˇcna, reˇcemo, da je neskonˇcna.

Naj bo sedaj mnoˇzica A ekvipolentna naravnemu ˇstevilu n 6= 0.

Torej A vsebuje vsaj en element a. Po naˇsi konstrukciji je n toˇcno mnoˇzica, ki kot svoje elemente vsebuje vsa naravna ˇstevila manjˇsa od n, torej n = {0,1,2, . . . , n−1}. Torej obstaja bijektivna preslikava f :A→ {0,1, . . . , n−1}. Naj boB =A\{a}in definirajmo preslikavo g :B → {0,1,2, . . . , n−2} kot

g(b) =

( f(b) ;f(b)< f(a) f(b)−1 ;f(b)> f(a) .

Ker je preslikava g bijektivna, je B =A\{a}ekvipolentna n−1.

Trditev 3.22. Ce staˇ n in m razliˇcni si naravni ˇstevili, potem n ni ekvipolenten m.

Dokaz. Pokaˇzimo trditev z indukcijo pon. ˇStevilo 0 =∅oˇcitno ni ekvipolentno nobeni neprazni mnoˇzici. Predpostavimo sedaj, da n ni ekvipolenten nobenemu naravnemu ˇstevilu m 6= n in predpostavimo, da je n+ 1 ekvipolenten nekemu naravnemu ˇstevilu k. Po zgornjem premisleku je n =n+ 1\{n}potem ekvipolenten k−1. Po indukcijski predpostavki je k−1 =n in zato k =n+ 1.

Konˇcne mnoˇzice se obnaˇsajo priˇcakovano. ˇCe je A ekvipolentna n in B ekvipolentnam, potem je A∪B ekvipolentnam+n, ˇce sta A in B diskunktni. To lahko vidimo dokaj preprosto. Naj bosta f : A→n in g :B →m bijekciji. ˇCe definiramo h:A∪B →m+n kot

h(c) =

( f(c) ;c∈A g(c) +n c∈B; ,

imamo bijekcijo med A∪B inm+n. ˇCe A in B nista disjunktni, pa je A∪B ekvipolentna nekemu naravnemu ˇsteviluk ≤m+n.

Izrek 3.23. Mnoˇzica naravnih ˇstevil je neskonˇcna.

Dokaz. Recimo, da imamo poljubno preslikavo f : n → N, torej preslikavo iz {0,1,2, . . . , n−1} v N. Poglejmo si s pomoˇcjo indukcije, da obstaja m∈N(ki je lahko odvisen od n), da veljaf(k)≤mza vsak k = 0,1, . . . , n−1. ˇCe je n= 0, je to oˇcitno. Naj torej trditev velja za n in naj bo f : n+ 1→N. Definirajmo g :n →N kot g(k) =f(k) za vsak k = 0,1, . . . , n−1. Po indukcijski predpostavki obstaja m⁰ ∈ N, da velja g(k) ≤ m⁰ za vsak k = 0,1, . . . , n−1. Naj bo m =m⁰, ˇce je f(n)≤m⁰ oziroma m =f(n), ˇce je f(n)> m⁰. Potem velja f(k)≤m za vsak k = 0,1, . . . , n, kar smo ˇzeleli pokazati. Sedaj lahko enostavno vidimo, da nobena preslikava f :n →N ne more biti surjektivna. Naj bo namreˇc m ∈ N tak, da je f(k) ≤ m za vsak k = 0,1, . . . , n−1.

Potem ˇstevilo m+ 1 ni v sliki preslikave f. Definicija 3.24 (ˇStevno neskonˇcne mnoˇzice). MnoˇzicaAje ˇstevno neskonˇcna, ˇce je ekvipolentna mnoˇzici naravnih ˇstevil.

Poiˇsˇcimo bijekcijo mnoˇzice naravnih ˇstevilNna kakˇsno njeno pravo (neskonˇcno) podmnoˇzico. Preprost zgled je preslikava f, ki vsakemu naravnemu ˇstevilu n priredi njegovega naslednika n⁰ =n+ 1. Ta pre- slikava je bijekcija iz N na pravo podmnoˇzico N\ {0} brez ˇstevila 0.

0 1 2 3 · · ·

↓ ↓ ↓ ↓ · · · 1 2 3 4 · · ·

Ce jeˇ A ⊂ N in je A konˇcna, potem je N\A neskonˇcna, saj bi v nasprotnem bila N = A ∪N\A konˇcna, kot smo videli zgoraj. Po- glejmo si sedaj, da je N\A po priˇcakovanjih ˇstevno neskonˇcna. ˇCe je A ekvipolentna 0, nimamo kaj dokazovati, saj je A∅. Predpostavimo sedaj, da je naˇsa trditev resniˇcna za vse podmnoˇzice A, ekvipolentne N. Naj bo sedaj A⁰ ⊂ N ekvipolentna n+ 1. Naj bo a ∈ A⁰ tak, da je b < a za vsak b ∈ A⁰, b 6= a (a je najveˇcji element v A⁰). Potem je A⁰ = A⁰\{a} ∪ {a}. Ker je A = A⁰\{a} ekvipolentna n, imamo bijektivno preslikavo f :N\A→N in definirajmo f⁰ :N\A⁰ →N kot

g(b) =

( f(b) ;b < a f(b−1) ;b > a .

Hitro lahko preverimo, da je f⁰ bijekcija. Poglejmo si sedaj precej bolj sploˇsno trditev.

Izrek 3.25. Vsaka podmnoˇzica naravnih ˇstevil je bodisi konˇcna, bodisi ˇstevno neskonˇcna.

Dokaz. Naj bo A ⊂ N neskonˇcna mnoˇzica. Pokazati moramo, da obstaja bijekcija f : N → A. Definirajmo f(0) = a₀, kjer je a₀ najmanjˇsi element mnoˇzice A. Tak element obstaja, saj je A dobro urejena. MnoˇzicaA\{a₀}je neskonˇcna, in naj boa₁ =f(a₁) najmanjˇsi element mnoˇzice A\{a₀}. Potem je a₁ > a₀. ˇCe imamo ˇze definirane a_n=f(n), definirajmoa_n+1 =f(n+ 1) kot najmanjˇsi element mnoˇzice A\{a₀, a₁, . . . , a_n}. Velja a_n+1 > a_n. Tako rekurzivno definiramof kot funkcijo f : N → A. Preslikava f je oˇcitno injektivna, saj iz n < m sledi f(n) < f(m). Prav tako velja f(n) ≥ n. ˇCe bi torej obstajal tak b ∈ A, da b ne bi bil v sliki preslikave f, bi seveda moralo veljati b ≥ a_n ≥ n. Torej tudi b ≥ b+ 1, kar pa ni res. Torej je f tudi

surjektivna.

POGLAVJE 4

Cela in racionalna ˇ stevila

V drugem poglavju smo predstavili osnovne lastnosti sistema narav- nih ˇstevil, toda dosegli smo meje moˇznega za seˇstevanje in mnoˇzenje.

Radi bi uvedli tudi operacijo odˇstevanja in deljenja, ampak pri teh dveh operacijah moramo iz naravnega ˇstevilskega sistema preiti v ce- lega oziroma racionalnega, pri ˇcemer se bomo opirali na [2].

4.1. Cela ˇstevila

Neformalno lahko reˇcemo, da so cela ˇstevila tista, katera dobimo pri odˇstevanju dveh naravnih ˇstevil. Na primer 3−5 je celo ˇstevilo in tudi 6−2 je celo ˇstevilo. To sicer ni popolna opredelitev celih ˇstevil, saj:

a) ne pove, kdaj sta dve ˇstevili enaki (na primer 3−5 je enako 2−4, ni pa enako 1−6),

b) ne pove, kako se raˇcuna z razlikami dveh naravnih ˇstevil (na primer, kako se seˇsteje 3−5 in 6−2),

c) ta definicija nekako predpostavlja, da ˇze znamo vedno odˇsteti dve naravni ˇstevili.

K sreˇci lahko zaradi predhodnih izkuˇsenj s celimi ˇstevili odgovorimo na zgornja vpraˇsanja. Pri odgovoru na a) si lahko pomagamo z naˇsim vnaprejˇsnjim znanjem iz raˇcunstva: a−b =c−d, natanko takrat, ko je a +d = b+c in tako lahko opredelimo enakost razlik z uporabo koncepta seˇstevanja.

Podobno lahko odgovorimo na b), saj vemo, da naj bi veljalo (a− b)+(c−d) = (a+c)−(b+d) in tudi (a−b)(c−d) = (ac+bd)−(ad+bc).

S svojim predznanjem lahko na tak naˇcin definiramo cela ˇstevila.

Se prej pa moramo reˇsiti problem c), ˇˇ cesar se bomo lotili nekoliko bolj formalno. Razliko celih ˇstevil bomo zapisali na nekoliko drugaˇcen naˇcin in sicer ne kota−b, paˇc pa kot (a—b), pri ˇcemer bo zapisa—b

pomenil toˇcno isto, kot (a, b) ∈ N×N. Kasneje, ko bomo definirali odˇstevanje, bomo videli, da jea—b v bistvu enako a−bin tako bomo lahko zavrgli — . Tega potrebujemo samo zaˇcasno.

Definicija 4.1 (Cela ˇstevila). Celo ˇstevilo je izraz oblike a—b, kjer sta a in b naravni ˇstevili. Dve celi ˇstevil a—b =c—d sta enaki, ˇ

ce in samo ˇce velja a+d =c+b. Mnoˇzico celih ˇstevil oznaˇcimo z Z. Bolj formalno,

Z= (N×N)/∼,

kjer je∼ekvivalenˇcna relacija naN×N, definirana za—b∼c—d ⇐⇒

a+d=b+c.

Na primer 3 — 5 je celo ˇstevilo in je enako 2 — 4, saj je 3+4 = 2+5, medtem ko 3 — 5 ni enako 2 — 3, saj 3 + 3 6= 2 + 5. Sicer je ta zapis za enkrat ˇse nekoliko nejasen in pomanjkljiv, saj na primer 3 ni celo ˇstevilo oblikea—b. Vse to bomo razreˇsili v nadaljevanju.

Preverimo najprej, da je relacija∼ res ekvivalenˇcna relacija. Refle- ksivnost in simetriˇcnost precej oˇcitno veljata, zato preverimo le aksiom tranzitivnosti. Predpostavimo, da a—b ∼ c—d in c—d ∼ e—f, potem velja a+d =c+b in c+f = d+e. ˇCe to zdruˇzimo, dobimo a+d+c+f =c+b+d+e. S trditvijo 2.16, lahko krajˇsamo cind in dobimo, a+f =b+e, t.j. a—b ∼e—f.

Definicija4.2. Vsoto dveh celih ˇstevil(a—b)+(c—d)definiramo kot

(a—b) + (c—d) := (a+c)—(b+d), produkt pa kot

(a—b)·(c—d) := (ac+bd)—(ad+bc).

Tako je na primer (3 — 5) + (1 — 4) enak 4 — 9. Seveda moramo ˇse dokazati, da sta obe operaciji dobro definirani na kvocientni mnoˇzici Z.

Primer 4.3. 3 — 5 je enako 2 — 4, tako mora imeti izraz (3 — 5) + (1 — 4) enako vrednost kot (2 — 4)+(1 — 4), drugaˇce definicija o seˇstevanju celih ˇstevil ne drˇzi. V prvem primeru je rezultat 4 — 9, v drugem pa 3 — 8. Seveda je 4 — 9 ∼3 — 8.

Lema 4.4 (Seˇstevanje in mnoˇzenje sta dobro definirana). Naj bodo a, b, a⁰, b⁰, c, d naravna ˇstevila. ˇCe (a—b)∼(a⁰—b⁰), potem (a—b) + (c—d) ∼ (a⁰—b⁰) + (c—d) in (a—b)·(c—d) ∼ (a⁰—b⁰)·(c—d) in tudi (c—d) + (a—b) ∼ (c—d) + (a⁰—b⁰) in (c—d)·(a—b) ∼ (c—d)·(a⁰—b⁰) Tako sta seˇstevanje in mnoˇzenje dobro definirana.

Dokaz. Da dokaˇzemo, da (a—b) + (c—d) ∼ (a⁰—b⁰) + (c—d), moramo pokazati, da velja (a+c) — (b+d)∼(a⁰+c) — (b⁰+d), torej a +c+b⁰ +d = a⁰ +c+b +d. Vendar, ker je (a—b) ∼ (a⁰—b⁰), velja a+b⁰ = a⁰ +b, in ˇce dodamo c+d, na obeh straneh dobimo ˇ

zelen izraz. Pokazati moramo ˇse (a—b)·(c—d) ∼ (a⁰—b⁰)·(c—d), torej (ac+bd) — (ad +bc) ∼ (a⁰c+b⁰d) — (a⁰d +b⁰c), oziroma ac+ bd+a⁰d+b⁰c = a⁰c+b⁰d +ad +bc. Levo stran lahko zapiˇsemo kot c(a+b⁰) +d(a⁰ +b), medtem ko desno c(a⁰ +b) +d(a+b⁰). Ker je a+b⁰ =a⁰+b, sta obe strani enaki. Drugi dve identiteti se dokazujeta podobno.

Cela ˇstevilan— 0 se obnaˇsajo enako kot naravna ˇstevila. Preverimo lahko, da je (n— 0) + (m— 0) = (n+m) — 0 in (n— 0)·(m— 0) = nm— 0. Poleg tega je (n— 0) ∼ (m— 0), ˇce in samo ˇce je n = m.

Tako dobimo bijekcijo med naravnimi ˇstevili n in celimi ˇstevili oblike n— 0, ki ohranja seˇstevanje in mnoˇzenje. Naravna ˇstevila lahko tako identificiramo s podmnoˇzico celih ˇstevil preko identifikacije n=n— 0.

Na primer naravno ˇstevilo 3 lahko obravnavamo enako kot celo ˇstevilo 3 — 0, torej je 3 = 3 — 0, 0 enako 0 — 0 ter 1 je enako 1 — 0. Seveda pa lahko 3 razumemo ne le kot 3 — 0, paˇc pa tudi 4 — 1, 5 — 2...

Na celih ˇstevilih lahko definiramo tudi operacijo naslednik, in sicer kot (n—m) + + = (n + +) —m. Preverimo lahko, da je operacija dobro definirana in zadoˇsˇca ˇcetrtemu Peanovemu aksiomu.

Poglejmo si sedaj, da so cela ˇstevila dejansko grupa za seˇstevanje.

Definicija 4.5 (Obratni element). Naj bo a—b celo ˇstevilo. De- finirajmo

−(a—b) :=b—a.

Posebej, ˇce je n=n—0 naravno ˇstevilo, je −n = 0—n.

Primer 4.6. −(3 — 5) = (5 — 3)

Obratni element je dobro definiran v celih ˇstevilih, saj iz a—b ∼ c—d oˇcitno sledi b—a∼d—c.

Naslednja trditev nam pove, da so cela ˇstevila komutativni kolobar z enoto za operaciji seˇstevanje in mnoˇzenje. Kot smo ˇze zapisali, je 0 = 0 — 0 in 1 = 1 — 0.

Trditev 4.7. Naj bodo x, y in z cela ˇstevila. Potem velja:

Komutativnost seˇstevanja: x+y=y+x.

Asociativnost seˇstevanja: (x+y) +z =x+ (y+z).

Obstoj enote za seˇstevanje: x+ 0 = 0 +x=x.

Obstoj inverza za seˇstevanje: x+ (−x) = (−x) +x= 0.

Komutativnost mnoˇzenja: xy =yx.

Asociativnost mnoˇzenja: (xy)z =x(yz).

Obstoj enote za mnoˇzenje: x1 = 1x=x.

Razliˇcnost enot: 06= 1.

Distributivnost: x(y+z) =xy+xz.

Dokaz. Zgornje identitete najlaˇzje dokaˇzemo tako, da zapiˇsemo x = (a—b), y = (c—d) in z = (e—f) in vedno poraˇcunamo obe strani. To omogoˇca, da je vsaka identiteta dokazana v nekaj vrsticah.

Pokazali bomo le najdaljˇso in sicer (xy)z =x(yz). Leva stran je enaka (xy)z =

= ((a—b)(c—d))(e—f)

= ((ac+bd) — (ad+bc))(e—f)

= ((ace+bde+adf +bcf) — (acf +bdf +ade+bce)), desna pa

x(yz) =

= (a—b)((c—d)(e—f))

= (a—b)((ce+df) — (cf +de))

= ((ace+adf +bcf +bde) — (acf +ade+bce+bdf)).

Vidimo, da sta (xy)z in x(yz) enaka. Ostale identitete se dokazujejo

na podoben naˇcin.