11 Nekonečné množiny, Zastavení algoritmu Bystrého čtenáře může snadno napadnout myšlenka, proč se vlastně zabýváme dokazováním správnosti algoritmů a programů, když by to přece (snad?) mohl za nás dělat automaticky počítač samotný. Bohužel to však nejde a je hlavním cílem této lekce ukázat důvody proč. Stručný přehled lekce * Nekonečné množiny, jejich „velikost" a Cantorova diagonála. * „Naivní" množinové paradoxy: Cantorův a Russelův. * Důkaz algoritmické neřešitelnosti problému zastavení programu. Petr Hliněný, Fl MU Brno, 2016 1/13 Fl: IB000: Nekonečno a zastaven nekonečných množinách a kardinalitě Uvažme problém stanovit, kolik má nekonečná množina prvků. Co nám třeba brání zavést pro velikost nekonečné množiny symbol oc? - Ponejvíce závažný fakt, že není „nekonečno" jako „nekonečno" (Věta 11.2)!c Definice: Množina A je „nejvýše tak velká11 jako množina B, právě když existuje injektivní funkce f : A B. Množiny A a B jsou „stejně velké11 právě když mezi nimi existuje bijekce. Í7) <7\ vy V případech nekonečných množin pak mluvíme formálně o jejich kardinalitě. Petr Hliněný, Fl MU Brno, 2016 2/13 Fl: IB000: Nekonečno a zastaven Ukázky kardinalit množin Uvedená definice kardinality množin funguje korektně i pro nekonečné množiny: * Například N a Z mají stejnou kardinalitu (jsou „stejně velké", tzv. spočetně nekonečné).n * Lze snadno ukázat, že i (Q je spočetně nekonečná, tj. existuje bijekce / : N Q, stejně jako bijekce h : N N2. 4/4 5/4 6/4 5 j 3/5 4/5 5/5 6/5 2/6 3/6 4/6 5/6 6/6 □ * Existují ale i nekonečné množiny, které jsou „striktně větší" než libovolná spočetná množina (příkladem je R ve Větě 11.2).c * Později dokážeme, že existuje nekonečná posloupnost nekonečných množin, z nichž každá je striktně větší než všechny předchozí. Petr Hliněný, Fl MU Brno, 2016 3/13 Fl: IB000: Nekonečno a zastaven Zjednodušeně místo bijekce Pro porovnávání velikostí množin někdy s výhodou využijeme následující přirozené, ale nelehké tvrzení (bez důkazu): Věta 11.1. Pro libovolné dvě množiny A, B platí, že pokud existuje injekce A —> B a zároveň i injekce B —> A, pak existuje bijekce mezi A a B. Petr Hliněný, Fl MU Brno, 2016 4/13 Fl: IB000: Nekonečno a zastaven Cantorova diagonála, aneb kolik je reálných čísel Věta 11.2. Neexistuje žádné surjektivní zobrazení g : N —> R. Důsledek 11.3. Neexistuje žádné injektivní(ani bijektivní) zobraz, h : R —> N. Neformálně řečeno, reálných čísel je striktně více než všech přirozených. Petr Hliněný, Fl MU Brno, 2016 5/13 Fl: IB000: Nekonečno a zastaven Věta. Neexistuje žádné surjektivní zobrazení g : N —> R. Důkaz (Věty 11.2 sporem): Nechť takové g existuje a pro zjednodušení se omezme jen na funkční hodnoty v intervalu [0,1). Podle hodnot zobrazení g si takto můžeme „uspořádat" dekadické zápisy všech reálných čísel v intervalu [0,1) po řádcích do tabulky: 5(0 5(1 5(2 5(3 5(4 0. 0. 0. 0. 0. 12 5 4 41 12 27578325 3-1 9-1 □ □ Nyní sestrojíme číslo a G [0,1) následovně; jeho í-tá číslice za desetinnou čárkou bude 1, pokud v i-tém řádku tabulky na diagonále není 1, jinak to bude 2. V našem příkladě ex. = 0.21211... Kde se naše číslo a v tabulce nachází? (Nezapomeňme, g byla surjektivní, takže a někde musí být.) Konstrukce však ukazuje, že a se od každého čísla v tabulce liší na aspoň jednom desetinném místě, a to je spor. (Až na drobný technický detail s rozvojem ... 9.) □ Petr Hliněný, Fl MU Brno, 2016 6/13 Fl: IB000: Nekonečno a zastaven ■r 11.2 „Naivní" množinové paradoxy Analogickým způsobem k Větě 11.2 lze dokázat následovné zobecnění. Věta 11.4. Necht M je libovolná množina. Pak existuje injektivní zobrazení f : M —> 2M, ale neexistuje žádné bijektivní zobrazení g : M —> 2M .c Důkaz: Dokážeme nejprve existenci /. Stačí ale položit f (x) = {x} pro každé x G M. Pak f : M —> 2M je zjevně injektivní.c Neexistenci g dokážeme sporem. Předpokládejme tedy naopak, že existuje bije kce g : M —> 2M. Uvažme množinu K C M definovanou takto: K = {x G M | x 0 g (x)}. Jelikož g je bijektivní a K G 2M, musí existovat y G M takové, že g (y) = K.c Nyní rozlišíme dvě možnosti: ~ V £ 5 (ž/)- TJ- V ^ K- Pak ale y 0 g (y) z definice K, což je spor. ~ y 0 5(ž/)- To podle definice if znamená, že y G Ír, tj. y G ^(y), spor. Petr Hliněný, Fl MU Brno, 2016 7/13 Fl: IB000: Nekonečno a zastaven Dvě navazující poznámky. • Technika použitá v důkazech Vět 11.2 a 11.4 se nazývá Cantorova diagonální metoda, nebo také zkráceně diagonalizace. □ Konstrukci množiny K lze znázornit pomocí následující tabulky: b c d g (o) i - v ... 9ÍP) — ■ ■ ■ ■■ ■ ■ Symbol y/ resp. — říká, že prvek uvedený v záhlaví sloupce patří resp. nepatří do množiny uvedené v záhlaví řádku. Tedy např. d G g(b) a a 0 g(d). • Z toho, že nekonečna mohou být „různě velká", lze lehce odvodit řadu dalších faktů. V jistém smyslu je např. množina všech problémů větší než množina všech algoritmů (obě množiny jsou nekonečné), a proto nutně existují problémy, které nejsou algoritmicky řešitelné. Petr Hliněný, Fl MU Brno, 2016 8/13 Fl: IB000: Nekonečno a zastaven Cantorův paradox Příklad 11.5. Uvážíme-li nyní nekonečnou posloupnost množin AuA2,A3,A4r-- kde A\ — N a Ai+i = 2Ai pro každé ígN, je vidět, že všechny množiny jsou nekonečné a každá je striktně větší než libovolná předchozí Kde však v tomto řazení kardinalit bude „množina všech množin"? ^Na tuto otázku, jak sami asi cítíte, nelze podat odpověď. Co to však znamená? □ * Takto se koncem 19. století objevil první Cantorův paradox teorie množin.c * Dnešní moderní vysvětlení paradoxu je jednoduché, prostě „množinu všech množin" nelze definovat, taková v matematice neexistuje.□ Brzy se však ukázalo, že je ještě mnohem hůř... Petr Hliněný, Fl MU Brno, 2016 9/13 Fl: IB000: Nekonečno a zastaven Russelův paradox Fakt: Není pravda, že každý soubor prvků lze považovat za množinu. • Nechť X = {M | M je množina taková, že M 0 M}. nPlatí X G X ?□ * Ano. Tj. X G X. Pak ale X splňuje X 0 X.n * Ne. Pak X splňuje vlastnost X 0 X, tedy X je prvkem X, tj., X G X.c • Obě možné odpovědi vedou ke sporu. X tedy nelze prohlásit za množinu. Jak je ale něco takového vůbec možné? Vidíte u Russelova paradoxu podobnost přístupu s Cantorovou diagonalizací? Russelův paradox se objevil začátkem 20. století a jeho „jednoduchost" zasahující úplné základy matematiky (teorie množin) si vynutila hledání seriózního rozřešení a rozvoj formální matematické logiky. □ * Pro ilustraci tohoto paradoxu, slyšeli jste už, že „v malém městečku žije holič, který holí právě ty muže městečka, kteří se sami neholí"? * Zmíněné paradoxy naivní teorie množin zatím v tomto kurzu nerozřešíme, ale zapamatujeme si, že většina matematických a informatických disciplín vystačíš „intuitivně bezpečnými" množinami. Petr Hliněný, Fl MU Brno, 2016 10/13 Fl: IB000: Nekonečno a zastaven 11.3 Algoritmická neřešitelnost problému zastavení Fakt: Uvědomme si (velmi neformálně) několik základních myšlenek. • Program v každém programovacím jazyce je konečná posloupnost složená z konečně mnoha symbolů (písmena, číslice, mezery, speciální znaky, apod.) Nechť S je množina všech těchto symbolů. Množina všech programuje tedy jistě podmnožinou množiny Uígn ^'» která je spočetně nekonečná. Existuje tedy bijekce / mezi množinou N a množinou všech programů. Pro každé j G N označme symbolem Pj program f(j). Pro každý program P tedy existuje i G N takové, že P = Pi x • Každý možný vstup každého možného programu lze zapsat jako konečnou posloupnost symbolů z konečné množiny I\ Množina všech možných vstupů je tedy spočetně nekonečná a existuje bijekce g mezi množinou N a množinou všech vstupů. Pro každé j G N označme symbolem Vj vstup g(j^p • Předpokládejme, že existuje program Halt, který pro dané i, j G N zastaví s výstupem ano/ne podle toho, zda Pí pro vstup Vj zastaví, nebo ne. • Tento předpoklad dále dovedeme ke sporu dokazujícímu, že problém zastavení nemá algoritmické řešení. Petr Hliněný, Fl MU Brno, 2016 11/13 Fl: IB000: Nekonečno a zastaven ■r Věta 11.6. Neexistuje program Halt, který by pro vstup (Pi,Vj) správně rozhodl, zda se program Pí zastaví na vstupu Vj. Důkaz: Sporem uvažme program Diag s následujícím kódem: input k; if Halt(k,k) = ano then while true do ; donee Fungování programu Diag lze znázornit za pomocí následující tabulky: Symbol y/ resp. — říká, že program uvedený v záhlaví sloupce zastaví resp. nezastaví pro vstup uvedený v záhlavířádku. Program Diag „zneguje" diagonálu této tabulky. V0 Petr Hliněný, Fl MU Brno, 2016 12/13 Fl: IB000: Nekonečno a zastaven if Halt (k, k) = ano then while true do ; done fi Po Pi p2 p3 ... Vo — — v ■■■ Vi V V — V ■■■ v2 — V V ■■■ Vs V *J ... Podle našeho předpokladu (Diag je program a posloupnost Pí zahrnuje všechny programy) existuje j G N takové, že Diag = Pj. Zastaví Diag pro vstup Vjlc - Ano. Podle kódu Diag pak ale tento program vstoupí do nekonečné smyčky, tedy nezastaví.c - Ne. Podle kódu Diag pak ale if test neuspěje, a tento program tedy zastaví. □ Předpoklad existence programu Halt tedy vede ke sporu. □ Otázkami algoritmické (ne)řešitelnosti problémů se zabývá teorie vyčíslitelnosti x Metoda diagonalizace se také často využívá v teorii složitosti k důkazu toho, že dané dvě složitostní třídy jsou různé. Petr Hliněný, Fl MU Brno, 2016 13/13 Fl: IB000: Nekonečno a zastaven