Příklad 1 Dokažte, že tyto dvě množiny nejsou spočetné: 1. Množina všech podmnožin N Co chceme dokázať? Spočetná množina: Množina M je spočetná práve vtedy keď existuje funkcia (nie nutne vyčíslitelná) / : M —> N taká, že / je bijekcia (/ je surjektívna a injektívna). Negácia definície: Množina M nie je spočetná práve vtedy keď pre všetky funkcie / : M —> N platí, že / nie je bijekcia. Dokazované tvrdenie: Množina 2 (značí sa aj "P(N)) nie je spočetná, teda pre všetky / : 2N N platí, že / nie je bijekcia. Úvaha: Dokazovať niečo o všetkých funkciách (alebo iných entitách) priamo je väčšinou dosť náročné (hlavne pokiaľ nie je možné použiť indukciu). Teda sa uchýlime k dôkazu sporom (alebo ako hovorí prvé pravidlo dokazovania - keď neviete, skúste to sporom). Poznámka: Dôkaz sporom je založený na pozorvaní, že pokiaľ —*A =4> B a súčasne —*A =4> —*B, potom musí platiť A (dá sa jednoducho overiť skonštruovaním príslušnej logickej tabuľky ;)) Dôkaz: Z poznámky vyplívá že potrebujeme vedieť ako vyzerá —*A. V tomto prípade stačí zameniť negáciu definície spočetnosti za pôvodnú, nenegovanú definíciu. Teda vo výsledku dostávame nasledujúce tvrdenie: Pre spor predpokladajme, že množina 2N je spočetná, a teda že existuje funkcia / : 2N —> N ktorá je bijekciou. Teraz potrebujeme nájsť vhodné tvrdenie B tak, aby sme získali spor. To je samozrejme netriviálna úloha na ktorú neexistuje jednoznačný postup. Prvé na čo by sme sa ale v tomto prípade mali pozrieť je čo "nové"vnáša do nášho "sveta"náš (zatiaľ údajne) sporný predpoklad. V tomto prípade nám predpoklad dáva existenciu funkcie f, ktorá je bijekciou. Teda môžeme pomerne bezpečne predpokladať, že f sa nejakým spôsobom bude vyskytovať v B, a že bude nutné využiť fakt že ide o bijekciu (Inak by sme rovanký spor mohli použiť aj bez predpokladu —iA, a teda by sme dokázali že celý systém je sporný.). Druhá vec, ktorá by sa s najväčšou pravdepodobnosťou v tvrdení B mala objaviť je potom samotná množina 2N. Prečo? Tento krát to nie je také očividné ako s funkciou f, ale dá sa argumentovať že ak je definičným oborom f práve 2N, a f je bijekciou (čo je definícia ktorá silne súvisí s definičným oborom a oborom hodnôt), tak bude asi nejakým spôsobom nutné tento fakt využiť. Pokiaľ stále nevieme ako by bolo možné B skonštruovať, môžeme pokračovať jemne redukcionistickou úvahou, a to síce: Chceme výrok ktorý sa nejakým spôsobom vyjadruje o množine. Množina je súborom prvkov. Teda hľadáme nejaký prvok ktorý nám vyvolá spor. Asi najočividnejší spor v súvislosti s množinami sa týka príslušnosti do množiny: Teda prvok ktorý do množiny zároveň patrí aj nepatrí. Prvý nápad by teda mohol byť "hľadať podmnožinu N ktorá zároveň nie je podmnožinou N". To sa nám bohužiaľ v tomto prípade asi nepodarí. Na druhej strane si ale pri tom môžeme všimnúť, že pvky 2N sú opäť množiny. Čo keby sme teda dokázali vyvolať nejaký problém tam... Nech B = {x G N | x 0 /_10E)} (/_1 existuje, keďže / je bijekcia). Táto definícia sa dá prepísať vo forme ekvivalencie x G B x 0 f-1 (x). Ďalej očividne B C N, teda musí existovať prirodzené číslo i také, že B = f (i) (z definície spočetnosti). Pre toto i dostávame (z definície B) že i G B 44> i 0 f-1 (i). Ale keďže B = f (i), tak i G B 44> i 0 B. Pre úplnosť: Dostávame teda dve tvrdenia: Ak je 2N spočetná, potom f (i) G -B a zároveň ak je 2N spočetná, tak f (i) 0 B. Teda logicky plynie že 2N nie je spočetná. Příklad 13 Nechť / : N —> N je vyčíslitelná bijekce. Uvažujme numeraci unárních vyčíslitelných funkcí 1pO,1pl, Ipn, ••• (1) kde ipn = ^/(n)- Dokažte, že pro tuto numeraci existuje vyčíslitelná univerzální funkcie \ř : N2 —> N. Ukažte, že existuje a takové, že funkce \ř je počítána programem Pf(a) ■ Zmení sa tvrdenie ak by / nebola injektívna/surjektívna, ale stále totálna? Čo chceme dokázať? Numerácia: Numerácia množiny M je surjektívna (nie nutne totálna) funkcia / : M —> N. Univerzálna funkcia: Univerzálna funkcia íl pre numeráciu (unárnych) funkcií uj je funkcia íl : N2 —> N taká, že íl (e, x) = we(x). (teda najprv v numerách' nájdem funkciu s indexom e a potom ju spustím so vstupom x) Našou úlohou je teda ukázať, že pre danú numeráciu (nazvime si ju ip), existuje vyčísliteľná univerzálna funkcia. Dôkaz: Pokiaľ chceme ukazovat vyčíslitelnost', najjednoduššie je väčšinou nájsť program ktorý počíta to, čo potrebujeme. Z definície univerzálnej funkcie vidíme, že na to, aby sme spočítali jej hodnotu, potrebujeme najskôr zistiť čo za funkciu vlastne vyčísľujeme (podľa indexu daného prvým argumentom). V prípade štandardnej numerácie na toto slúži kódovanie programov na indexy ktoré bolo definované na prednáške. V prípade našej novej numerácie sa musíme pozrieť na to, ako je vlastne definovaná. Podľa zadania máme k dispozícií vyčíslitelná bijekciu f ktorá mapuje indexy našej novej numerácie na indexy štandardnej numerácie (ipn = (ff(n}). A o štandardnej numerácií vieme, že má vyčíslitelná univerzálnu funkciu. Teda nám nič nebráni najskôr spočítať funkciu f, aby sme získali index programu v štandardnej numerácií, a potom pustiť štandardná univerzálnu funkciu nad týmto indexom: : N2 N : V ■= f{xi);xi:=§(y,x2) Takáto funkcia je vyčísliteľná (/ aj <í> sú vyčísliteľná) a spĺňa definíciu univerzálnej funkcie, keďže V(e,x) = $(/(e),x) = Vf(e){x) = Mx)- Z definície bijekcie potom plynie, že všetky vyčísliteľná funkcie majú index v numerácií ip, a teda aj \ř má nejaký index a taký, že je počítaná programom Pf(a) (keďže je vyčísliteľná). Pokiaľ by / nebola injektívna, nič sa nezmení (stále platí že všetky vyč. funkcie majú index v ip, len sa môže sať že jeden program má viac indexov). Pokiaľ by ale / nebola surjektívna, a nemusí existovať. Příklad 16 Ukažte, že existuje TVF g : N2 —> N taková, že Vg{i,j) {x) = (fi{x) + (fj(x) (2) (súčet je definovaný len ak oba argumenty sú definované) Čo chceme dokázať? To že g definované v zadaní existuje, je pomerne triválne pozorovanie. Problémom je ukázať, že g je totálne a vyčíslitelné. K tomu nám poslúži práve veta o parametrizácií. Veta o parametrizácií: Pre všetky m > 1, n > 1 existuje totálne vyčísliteľná funkcia s™ : Nm+1 —y N taká, že ^(i,!,!,...,!,™)^!.-.^) = v?+n(yi,-,yn,zi,-,zn) (3) Dôkaz: Uvažujme vyčísliteľnú funkciu f (i, j,x) = (p i (x) +

j{x) (jej while program je dúfam zjavný :)) Keďže / je vyčísliteľná, existuje index e taký, že tpe = f. Priamou aplikáciou vety o parametrizácií potom dostávame, že existuje totálne vyčísliteľná s\ taká, že: '■Psl{a,i,j){x) =