12 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, 2020 1/13 Fl: IB000: Nekonečno a zastaven 1~12.1 O 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 12.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, 2020 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ě 12.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, 2020 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 12.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, 2020 4/13 Fl: IB000: Nekonečno a zastaven Cantorova diagonála, aneb kolik je reálných čísel Věta 12.2. Neexistuje žádné surjektivní zobrazení g : N —> R. Důsledek 12.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, 2020 5/13 Fl: IB000: Nekonečno a zastaven ■r Věta. Neexistuje žádné surjektivní zobrazení g : N —> R. Důkaz (Věty 12.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: Nyní sestrojíme číslo a £ (0,1) následovně; jeho i-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ě a = 0.21211... Kde se naše číslo a v tabulce nachází? Nezapomeňme, že 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.) □ 5(0 5(1 5(2 5(3 5(4 0. 12 5427578325 0. 41 0. Í2 0. 3-1 0. 9-1 □ □ Petr Hliněný, Fl MU Brno, 2020 6/13 Fl: IB000: Nekonečno a zastaven ■r 12.2 „Naivní" množinové paradoxy Analogickým způsobem k Větě 12.2 lze dokázat následovné zobecnění. Věta 12.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, 2020 7/13 Fl: IB000: Nekonečno a zastaven Dvě navazující poznámky. • Technika použitá v důkazech Vět 12.2 a 12.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 sr - V ••• 9(P) Ar V — g(d) ■ ■ ■ II ■ ■ 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, 2020 8/13 Fl: IB000: Nekonečno a zastaven Cantorův paradox Příklad 12.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, 2020 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, 2020 10/13 Fl: IB000: Nekonečno a zastaven 12.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, 2020 11/13 Fl: IB000: Nekonečno a zastaven Věta 12.6. Neexistuje program Halt, který by pro vstup (P^, 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: Po Pl p2 p3 ... - v ••• Vi \/^\ — v2 v3 ■ ■ ^ 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. Petr Hliněný, Fl MU Brno, 2020 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, 2020 13/13 Fl: IB000: Nekonečno a zastaven