Millise hulga osahulk on iga hulk? Peaks vast olema et iga hulk on universaalhulga osahulk. Mis on hulga astmehulk? Astmehulk on selle hulga kõikide osahulkade hulk. Mitu elementi on n elemendilise hulga astmehulgas? 2n elementi. Millist hulka nimetatakse lõplikuks hulgaks? Lõplik hulk sisaldab kindla arvu elemente. Millsit hulka nimetatakse lõpmatuks hulgaks? Lõpmatu hulk sisaldab piiramatult palju elemente? Millist hulka nimetatakse loenduvaks hulgaks? Hulk on loenduv, kui tema elementidele saab hakata vastavaks seadma naturaalarve. Mis on loendamine? Objektide arvu tuvastamiseks nendele naturaalarvude omistamine on loendamine. Lõpmatu mitteloenduv ja lõpmatu loenduv hulk. Loenduv {0,1,2,.......} Mitteloenduv {7.16646...,7,16646..., ...... } kuna iga elemendi vahel on veel lõpmatult elemente. Millised hulgaaritmeetilised tehted on olemas? 1 unaarne ja 4 binaarset. Binaarsed Hulkade ühend ehk hulgaaritmeetiline liitmine,
Lõpmatute hulkade võimsuste võrdlemiseks kasutatakse hulkade üksühese vastavuse mõistet. Ütleme, et hulgad A ja B on sama võimsusega, kui leidub bijektsioon f : A B. Tähis: A B, öeldakse ka, et hulgad A ja B on ekvivalentsed. Kehtivad omadused: · refleksiivsus: A A · sümmeetrilisus: kui A B, siis B A · transitiivsus: kui A B ja B C, siis A C Hulka, mis on sama võimsusega nagu naturaalarvude hulk, nimetatakse loenduvaks hulgaks. · Järelikult on loenduvad parajasti need hulgad, mis on esitatavad jadana {a0, a1, a2, . . .}. · Iga lõpmatu hulk sisaldab loenduvat osahulka. · Loenduva hulga iga lõpmatu osahulk on samuti loenduv. Cantor-Bernsteini teoreem Definitsioon Ütleme, et hulga A võimsus ei ületa hulga B võimsust, kui leidub injektsioon f : A B. Teoreem (Cantor-Bernsteini teoreem.) Kui hulga A võimsus ei ületa hulga B võimsust ja
iseendaga. 2. Kui , siis leidub bijektsioon : . Funktsiooni pöördfunktsioon -1 on siis samuti bijektsioon 3. Kui ja , siis leiduvad bijektsioonid : ja : . Nende kompositsioon : on siis samuti bijektsioon. Hulga võimsuseks nimetatakse tema ekvivalentsiklassi seose ~ järgi. Võimsusi nimetatakse ka kardinaalarvudeks. Hulga võimsuse jaoks kasutatakse tähiseid ||, ja . Loenduvad hulgad Hulka nimetatakse loenduvaks, kui leidub üksühene vastavus naturaalarvude hulga ja hulga vahel. Seega loenduvad on parajasti need hulgad , mida saab esitada kujul ={1,2,3,...}. Näiteid 1. Täisarvude hulk ja paaris-naturaalarvude hulk on loenduvad hulgad. 2. Igasugune hulga lõpmatu osahulk on ise loenduv ning sama võimsusega kui naturaalarvude hulk . 3. Ratsionaalarvude hulk on loenduv ning sama võimsusega kui naturaalarvude hulk või täisarvude hulk . 4
15. Mitu erinevat osahulka on n-elemendilisel hulgal? Igal hulgal on osahulka. 16. Mis on hulga astmehulk? Astmehulk on hulga kõigi osahulkade hulk. 17. Mitu elementi on n-elemendilise hulga astmehulgas? elementi. 18. Millist hulka nimetatakse lõplikuks hulgaks? Hulk on lõplik, kui ta sisaldab kindla arvu elemente. 19. Millist hulka nimetatakse lõpmatuks hulgaks? Lõpmatu hulk sisaldab lõpmatult palju elemente. 20. Millist hulka nimetatakse loenduvaks hulgaks? Hulk on loendub, kui tema elementidele saab vastavusse seada naturaalarve {0,1,2,3,...}. 21. Mis on „loendamine“? Hulga elementidele naturaalarvude omistamine. 22. Tuua näide lõpmatust loenduvast hulgas ja lõpmatust mitteloenduvast hulgast. Lõpmatud loenduvad hulgad on naturaalarvude hulk ja täisarvudehulk . Lõpmatu mitteloenduv hulk on reaalarvude hulk . 23. Millised hulgaaritmeetilised tehted on olemas? Millised on nende tehtemärgid?
Karakteristlik aktsepteeriv TM on selline, mis aktsepteerib, kui x kuulub keelde. Muul juhul lükkab tagasi. Genereeriv aktsepteeriv TM on selline, mis aktsepteerib, kui x kuulub keelde. Muul juhul ei peatu. DEF: Hulka (keelt), millel leidub karakteristlik Turingi masin, nimetatakse lahenduvaks ehk rekursiivseks. DEF: Hulka (keelt), millel leidub genereeriv Turingi masin, nimetatakse rekursiivselt loenduvaks ehk genereeritavaks. Lemma: Iga lahenduv hulk on rekursiivselt loenduv. T: Igal lahenduva hulga karakteristlikku masinat saab tesendada nii, et ta jääks olekusse qr jõudmise asemel tsüklisse ehk muutuks genereerivaks masinaks. Registermasin sisaldab registreid R1… (sisuks naturaalarv) ja märgendeid N1… Operaatorid on INC (+1), DEC (-1), CLR (nullimine), R → R (omastad ühe väärtuse teisele), JMP Na (go to N), JMP Nb (go to N+1),
element) · bijektsiooniks -> kui kujutus on samaaegselt sürjektsioon ja injektsioon Idee poolest on kujutus teatud tüüpi vastavus hulgast A hulka B. Hulgad A ja B on võrdvõimsad, kui leidub bijektiivne vastavus (M:A B) nende vahel (ehk siis kõik elemendid mõlemast hulgast on haaratud ja igaühele vastab vaid 1 kindel element). Lõpmatut hulka nimetatakse loenduvaks, kui see on võrdvõimas naturaalarvude hulgaga. |H| on hulga võimsus ehk lõpliku hulga korral elementide arv hulgas. Lõpmatu hulga võimsus leitakse, seades tema elemendid bijektiivsesse vastavusse (üks- ühesesse) mõne tuntud võimsusega hulga (näiteks naturaalarvude hulga) elementidega. 4. Graafid. Puude esitused. Programmide esitamine puuna Mittejärjestatud ja mitteorienteeritud graaf on paar G = (A,R), kus A on tippude hulk ja kaarte hulk R on seos hulgal A.
*Lõpliku hulga kardinaalarv on selle hulga elementide arv, lõpmatute hulkade puhul kasutatakse aga eritähiseid: 0 tähistab loenduvat võimsust, 1 aga tähistab kontiinumvõimsust. (loendamatu) *Võrdvõimsad hulgad- Kui kahes hulgas on ühepalju elemente ning nende elementide vahel saab luua üksühese vastavuse, on need kaks hulka võrdvõimsad. (Tähistatakse |A|=|B|) *Loenduv hulk- Kui hulk on sama võimsusega nagu naturaalarvude hulk N, peetakse teda üldiselt loenduvaks. Loenduv hulk võib seega olla ka lõpmatu. *Loendamatu hulk- Kui hulk on sama võimsusega nagu reaalarvude hulk IR, peetakse teda loendamatuks. Tänu komakohtadele pole elemente lihtsalt võimalik ammendavalt loetleda. Kontiinumhüpotees- Kontiinumhüpotees on hüpotees, mille arendajaks oli George Cantor (aastal 1877) ning see puudutab lõpmatute hulkade võimalikke suurusi. *Hüpoteesis eristatakse nö. ,,väiksema võimsusega lõpmatut hulka", milleks on
2. Kui A B , siis leidub bijektsioon f : A B . Funktsiooni f pöördfunktsioon -1 f :B A on siis samuti bijektsioon (kontrolli seda!); 3. Kui A B B C , siis leiduvad bijektsioonid f : A B ja ja g :B C . Nende kompositsioon g · f : A C on siis samuti bijektsioon. Definitsioon Hulka X nimetatakse loenduvaks, kui leidub bijektsioon hulga X ja naturaalarvude hulga N vahel. Märksus. · Loenduvad hulgad on lõpmatud hulgad · Leidub lõpmatuid hulki, mis ei ole loenduvad. Näide: · Z on loenduv · Q on loenduv · R ei ole loenduv! · (0, 1) ei ole loenduv! David Hilbert (18621943) tutvustas 1924. aastal ühes oma loengus järgmist lõpmatust illustreerivat näidet.
J¨arelikult omab ruumi X lahtine kate A l˜oplikku osakatet ja ruum X on kompaktne. Implikatsioon 20 =⇒ 10 on n¨aidatud. Kuna teist loenduvuse aksioomi rahuldav topoloogiline ruum rahuldab ka esimest loenduvuse aksioomi, siis ekviva- lents 20 ⇐⇒ 30 j¨areldub lemmast 7.2. 7.3 Kompaktsus meetrilistes ruumides Laialt levinud topoloogilise ruumi erijuhuks on meetriline ruum. Meetrilised ruumid rahuldavad esimest loenduvuse ak- sioomi, sest iga punkti x u ¨mbruste loenduvaks baasiks on lahtiste kerade B(x; r) hulk, kus r muutub u ¨le ratsionaalarvu- de hulga. J¨argnevalt kirjeldatakse kompaktsed hulgad meetri- lises ruumis X meetrikaga d. Saadud tulemused kehtivad eri- juhuna ka ruumide R ja Rn jaoks. Lemma 7.4 Kui meetrilise ruumi X elementide jada {xn }n∈N koondub, siis iga > 0 korral leidub selline n0 ∈ N, et n, m ≥ n0 =⇒ d(xn , xm ) < . T˜oestus. Olgu x vaadeldava jada piirv¨a¨artus
(selgitada!)z, see on harilike murdude loomulik järjestus. Kokkuvõttes oleme selgitanud, et ϕ : Q → Q ⊆ F , kus ϕ([(a, b)]) = ab−1 , on järjestatud korpuste isomorfism. Eelneva arutelu võtame kokku järgmises lauses 1.17. Lause 1.17 Iga järjestatud korpus F sisaldab alamkorpust Q, mis on isomorfne kõigi rat- sionaalarvude järjestatud korpusega Q. Lõpuks märgime veel üht hulga Q tähelepanuväärset omadust. Meenutame, et hulka A ni- metatakse loenduvaks, kui tema ja kõigi naturaalarvude hulga N elementide vahel eksisteerib üksühene vastavus. Omadus 1.18 Kõigi ratsionaalarvude hulk Q on loenduv. Tõestus. Iseseisvalt!z 20 1 Reaalarvud 1.4 Täieliku järjestatud korpuse ühesus. Reaalarvude definitsioon Praeguseks me juba teame, et täielikke järjestatud korpusi eksisteerib. Käesolevas
annaabi.ee 
