V minulém matykání jsme se pokusili prokousat se k nekonečnu počítáním oveček, ale zjistili jsme, že pokud jsou ovečky vrtošivé a zamíchají se do davu vlků, je těžké je systematicky evidovat. Příkladem nám byla prvočísla.
Je to množina, kterou je sice snadné definovat - zvládnou to i školáci - ale její struktura je natolik komplikovaná, že se dá jen těžko předvídat, kde přesně bude další prvočíslo. To samozřejmě počítání oveček moc neprospívá. Nakonec jsme na základě empirických dat sice pojali podezření, že prvočísel bude nejspíš nekonečně mnoho, ale sestrojit algoritmus na počítání oveček se nám nepodařilo. Budeme je tedy muset nějak oblafnout.
To, že je prvočísel nekonečně mnoho věděli už staří Řekové a pan Euklid na to konto vymyslel skvělý blafák. Nebojte, počítat dnes nebudeme nic. Jen si trochu pohrajeme s logikou. Metodě, kterou použil, se říká "důkaz sporem" a je to jeden z klasických způsobů jak matematicky dokázat nějaké tvrzení. V podstatě předpokládáte, že tvrzení neplatí (respektive platí jeho opak) a z toho zkusíte odvodit nějaký spor s platnými matematickými zákony.
Abychom nezačali moc zhurta, ukážu Vám nejdřív jeho princip na následujícím jednoduchém tvrzení: "President Zeman není orel". Jeho pravdivost je myslím celkem zřejmá (pan president ve skutečnosti náleží k druhu homo sapiens), ale přesto si ho dokážeme sporem. Udělá se to ve třech krocích. V prvním si sestrojíme tvrzení, které je opakem toho, co se snažíme dokázat (a tiše doufáme, že to otočené tvrzení neplatí a že někde něco rupne). Ve druhém z tohoto opaku něco logicky vyvodíme a ve třetím tento vývod dovedeme ke kýženému sporu (tedy k něčemu, co odporuje realitě). A teď konkretně.
1. President Zeman je orel (to je opak našeho tvrzení)
2. Každý orel létá a tudíž president Zeman létá taky (a hned to v praxi otestujeme)
3. Pozveme pana presidenta na nádvoří a ouha! - zjistíme, že on nelétá.
A protože nelétá (to je spor s realitou, že orlové létají), je jasné, že náš předpoklad (1) byl špatný a pan president tedy žádný orel není (což znalci jistě tušili i bez tohoto důkazu).
Důkaz sporem je v podstatě testovací mechanismus. Představte si matematiku jako starý televizní přístroj se spoustou vzájemně propojených elektronek. Když do jejích útrob našroubujete vadnou součástku a televizi spustíte, uvnitř to bouchne, někde se zajiskří a možná se vyvalí i kouř. Při důkazu sporem postupujete podobně. Jenom do toho vzájemně propojeného logického aparátu matematiky nenašroubujete vadnou elektronku, ale vložíte do něj nové tvrzení, o kterém doufáte, že je vadné (protože je to opak toho, co chcete dokázat). A pokud z toho nového tvrzení skutečně vyvodíte nějaký spor (pan president je sice orel, ale při tom si klidně nelétá), jinými slovy pokud někde něco krachne, tak jste doma. Vaše otočené tvrzení (1) je skutečně špatně a platí tedy tvrzení původní.
A nebo ještě jinak - v podstatě se snažíte vyvrátit opak tvrzení, které dokazujete. V krystalické podobě je to vidět třeba na konstatování: "Venku neprší, protože kdyby pršelo, bylo by mokrý zápraží".
A teď naostro.
V tom orlím příkladu jsem si dovolil zaapelovat na něco, co všichni známe - totiž fakt, že orlové létají. V matematice je většinou dobré si fakta, která budeme v důkazu používat nějak označit. Jednak proto, že nemusí být všeobecně známá a jednak proto, abychom se na ně mohli ve vhodnou chvíli odvolat. Takže než se pustíme do logického kuchtění, dáme si malé opáčko z elementární teorie čísel (ďábelský smích v pozadí).
Fakt A: každé přirozené číslo se dá rozložit na součin prvočísel (tzv. prvočinitele). Tohle je myslím známo ze školy - např. 150 = 2x3x5x5. Není potřeba zabíhat do algebraických detailů toho procesu - jak se to konkretně provede nás v tuto chvíli nemusí zajímat. Důležité je, že se takový rozklad dá udělat pro každé číslo.
Fakt B: prvočíslo, které dělí dané číslo K nikdy nedělí číslo následující, tedy K+1. Třeba v tom předcházejícím příkladu (K=150) je číslo následující 151 a je jasně vidět, že žádný z prvočíselných dělitelů čísla 150 ho nedělí. Ani 2, ani 3 a ani 5. Pro jistotu ještě jeden příklad: řekněme, že dané číslo K je 35 = 5x7. Číslo následující je 36 a ani 5 ani 7 ho nedělí.
(ono dokonce platí silnější tvrzení: dvě po sobě jdoucí přirozená čísla nemají žádné společné dělitele - ale nám to bude stačit pro prvočísla)
Ten fakt B je o něco komplikovanější než fakt A, ale žádná vysoká matematika to není. Jen je třeba si to rozmyslet. Vezměte si třeba to číslo 35 z minulého příkladu. Protože je dělitelné 5, tak nejbližší další číslo, které má šanci být dělitelné 5 leží o 5 kroků dál - tedy 40. 36 to tedy určitě nebude. A stejně tak pro 7. Nejbližší další číslo, které by mohlo být dělitelné 7 leží o 7 kroků dál - tedy 42. 36 je z obliga.
(Příznivci algebry se na fakt B mohou dívat i takto: pokud by nějaké prvočíslo p dělilo jak číslo K, tak K+1, tak by muselo dělit také jejich rozdíl, což je 1. A to není možné. Žádné prvočíslo nedělí jedničku. Ani v Sovětském svazu za Vlastenecké války.)
Dobrý. Fakta máme pokupě.
Pokud jste stále při vědomí, tak se konečně pustíme do důkazu našeho tvrzení, že prvočísel je nekonečně mnoho. Nejdřív si vytvoříme opak tohoto tvrzení (1), pak z něho zkusíme něco zajímavého uvařit (2) a nakonec si ukážeme, že to, co jsme si uklohnili, způsobí kraťas v televizi - tedy očekávaný logický spor (3). Tak s chutí do toho a půl je hotovo.
(1) prvočísel je pouze konečně mnoho (to je celkem jasný opak našeho tvrzení)
(2) A teď z toho něco zajímavého vyvodíme. Protože prvočísel je (podle našeho nového předpokladu) jen konečně mnoho, tak je spolu můžeme všechna vynásobit a výsledné číslo označíme K. Zdůrazňuji, že toto číslo vzniklo jako součin všech prvočísel, takže každé prvočíslo to číslo K dělí. A teď (pro spor) začneme zkoumat vlastnosti čísla následujícího - tedy K+1
(3) A tady se nám něco rozsype - sledujte. To číslo K+1 musí mít prvočíselný rozklad (podle faktu A). Tudíž nějaké prvočíslo p ho dělí. Jenže ouha - to samé číslo p dělí i K (protože K je součinem všech prvočísel). A to je spor, protože jsme nalezli prvočíslo, které dělí jak K, tak K+1 a to není možné podle faktu B.
Když si to rozmyslíte, tak ten spor vlastně vyplývá ze skutečnosti, že jsme při definici čísla K vyplýtvali doslova všechna možná prvočísla (a to se nám povedlo jen díky tomu, že jsme předpokládali, že je jich jen konečně mnoho), takže na číslo K+1 už žádná nezbyla. To číslo K+1 na jedné straně sice nějaké prvočinitele mít musí (podle faktu A), jenže není kde je vzít. Všechna prvočísla už dělí K a tudíž jeho následovník má smůlu. Žádné prvočíslo ho dělit nemůže - podle faktu B.
Naše pracně otočené tvrzení z bodu (1) tedy neplatí - dospěli jsme k jasnému výbuchu televize - a musí tedy platit tvrzení původní: prvočísel je nekonečně mnoho.
A je to.
Možná se Vám takový důkaz nekonečnosti jeví jako pouhý trik. A on to svým způsobem trik je. V příštím matykání se podíváme na jiný způsob jak se dopracovat do nekonečna a tam si konečně (vlastně nekonečně) trochu započítáme. Ale dám Vám dva měsíce na oddech.
A na uklidněnou si dnes dáme jednu retro pilulku: "Downtown" s Petulou Clark.
Ostatní díly Matykání.
