Ülessanne Kas antud hulkade omadused on rekursiivselt invariantsed: 1. Sisaldab vähemalt 3 elementi 2. On tühi 3. On lõputu 4. On rekursiivselt loenduv (RL) Millised neljast omadusest: on rekursiivne on rekursiivselt loenduv omab rekursiivst täiendit omab rekursiivselt loenduvat täiendit on antud hulkade põhjal 1. A = {x | x on paarisarv} 2. B = {x | x on väiksem kui 100} 3. C = {x | x on algarv} 4. D = {x | Wx on tühi} 5. E = {x | Wx sisaldab vähemalt 3 elementi} Lahendus Alusteooria Hulk on rekursiivselt invariantne, kui iga bijektiivse ja rekursiivse junktsiooni f korral, kui hulgal A on omadus P, siis ka hulgal f (a) on omadus P. 1 , kui x A
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 hulga B võimsus ei ületa, hulga A võimsust, siis hulgad A ja B on sama võimsusega. Teoreemi teine sõnastusvariant. Kui A B C ja A C, siis A B C. Teoreem
ühe korra paari esimese komponendina ja hulga iga element täpselt ühe korra paari teise komponendina. Kui vaatleme paaride teistest komponentidest koostatud jada {1,2,3,...}, siis selle jada elemendid on paarikaupa erinevad ja kehtib võrdus {1,2,3,...}=. Kui hulk on esitatud kujul ={1,2,3,...}, kus lõpmatu jada {1,2,3,...} on paarikaupa erinevate liikmetega, siis paaride hulk {(1,1),(2,2),(3,3),(4,4),... } on üksühene vastavus ja vahel. Teoreem 3. Iga lõpmatu hulk sisaldab loenduvat osahulka. Tõestus. Olgu suvaline lõpmatu hulk (seega ta pole lõplik, sealhulgas ). Seetõttu leidub temas elemente ja järgnevalt kirjeldamegi, kuidas hulga elemente valides saab moodustada paarikaupa erinevate elementidega lõpmatu jada. 1. Valime elemendi 1. See on võimalik, sest ei ole tühi. 2. Valime elemendi 2{1}. See on võimalik, sest kui hulk {1} oleks tühi, peaks hulk sisalduma hulgas {1} ja seega olema lõplik. 3. Valime elemendi 3{1,2}
Hulkade sümmeetriline vahe- Kahe hulga sümmeetriliseks vaheks on ,,kõik hulga A elemendid + kõik hulga B elemendid ilma nende ühise osata" (Tähistatakse ) [2]. Hulga võimsus. Kontiinumhüpotees. Hulga võimsus- Lõpliku hulga võimsus on tema elementide arv. Hulga võimsust tähistavat sümbolit nimetatase ka hulga kardinaalarvuks. *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
annaabi.ee 
