Vasakpoolses graafis on tipud astmega 3 ühendatud omavahel ühe servaga ja mõlemad tipud veel kahe tipuga, mille aste on 2. Kuid parempoolses graafis pole tipud astmega 3 omavahel servaga ühendatud ning mõlemad tipud astmega 3 on ühendatud kolme tipuga, mille aste on 2. Seega olen leidnud sellised tipud, mis on vasakpoolses graafis naabrid, kuid parempoolses graafis ei ole(need on 2 tippu, mille aste on 3). See aga tähendab, et nende kahe graafi tipuhulkade vahel ei leidu sellist bijektsiooni, et need kaks graafi oleksid isomorfsed. Seega ei ole need graafid isomorfsed. Vastus: Need graafid ei ole isomorfsed. ÜLESANNE 4. Graafi G sidususkomponentideks nimetatakse tema maksimaalseid sidusaid alamgraafe. Vähim võimalik graafi sidususkomponent on seega üksik tipp, mille aste on 0(ehk selline tipp, mis pole teistega ühendatud). Väide kehtib vaid juhul kui n m, sest graafil ei saa olla negatiivne arv sidususkomponente ning juhul n =
..,}, siis kõigi (lõpliku pikkusega) sõnade hulk tähestikus on loenduv. 2. Programmide hulk igas programmeerimiskeeles on loenduv. 3. Kui on loenduv tähestik {1,2,3,...}, siis kõigi (lõpliku pikkusega) sõnade hulk tähestikus on loenduv. Mitteloenduvad hulgad. Kontiinumi võimsusega hulgad Vahemik (0,1) ei ole loenduv hulk. Iga vahemik (,) arvsirgel on ekvivalentne vahemikuga (0,1) ja seega on mitteloenduv. Tõestus. Tõestamiseks on hea kasutada nn projekteerimist, mis annab bijektsiooni : (,)(0,1) või bijektsiooni -1: (0,1)(,). Hulka, mis on ekvivalentne vahemikuga (0,1) nimetatakse kontiinumi võimsusega hulgaks. (Lad. k. continuum pidev, katkematult jätkuv). Niisiis, hulk ja kõik vahemikud ning ka lõigud [,], kus <, on kontiinumi võimsusega. Kui ja on vastavalt kõigi ratsionaal- ja irratsionaalarvude hulgad, siis =. Et on loenduv hulk, siis ei saa olla loenduv, sest vastasel juhul oleks ka loenduv hulk. Irratsionaalarvude hulk on kontiinumi võimsusega hulk.
Funktsioon on osaliselt määratud, kui lähtehulgas leidub vastavuses mitteosalevaid elemente. 16. Mis on pealekujutus? Pealekujutuseks nimetatakse sürjektsiooni. 17. Mis on sürjektsioon? Sürjektsioon on kõikjale määratud funktsioon. 18. Mis on injektsioon? Injektsioon on üks-ühene funktsioon. 19. Mis on bijektsioon? Bijektsioon on kõikjale määratud üks-ühene funktsioon. Bijektsioon on samaaegselt nii sürjektsioon kui ka injektsioon. 20. Mis järeldub bijektsiooni korral lähtehulga ja sihthulga võimsuste kohta? Bijektsiooni korral on lähtehulga ja sihthulga võimsused võrdsed. 21. Mis on binaarne relatsioon? Binaarne relatsioon on vastavuse erijuht, kus nii lähtehulk kui ka sihthulk on üks ja sama hulk. 22. Mis on binaarsuhte alushulk? Binaarsuhte alushulk on hulk, millel on määratud relatsioon. 23. Mis on relatsioonikriteerium? Relatsioonikriteerium on reegel, mille abil on alushulga elemendid seotud vastavuspaarideks. 24
Kui hulga A võimsus ei ületa hulga B võimsust ja hulga B võimsus ei ületa hulga A võimsust, siis hulgad A ja B on sama võimsusega. Teisisõnu, CantorBernsteini teoreem ütleb, et kui eksisteerivad injektiivsed funktsioonid f : A B ja g :B A , siis hulgad A ja B on sama võimsusega. Või veel lühemalt, kui ¿ AB¿ ja ¿ B A¿ , siis ¿ A¿B¿ . Näide: Tõestada, et (0,1) ¿ . TÕESTUS Lahendus 1. Kõigepealt märgime, et ei ole üldse ilmne, kuidas konstrueerida bijektsiooni hulkade (0, 1) ja ¿ vahel. Tänu CantorBernsteini teoreemile piisab meil konstrueerida ainult kaks injektsiooni, mis on palju lihtsam ülesanne. Esiteks, injektsiooniks hulgast (0, 1) hulka ¿ sobib f (x)=x iga x (0, 1) korral, sest (0, 1) ¿ . x ¿ (0, 1) g( x)= x ¿ korral,
annaabi.ee 
