V minulém Matykání jsme se pokusili k nekonečnu prokousat počítáním oveček. Zjistili jsme však, ž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 Euklid 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í: Prezident Zeman není orel. Jeho pravdivost je, myslím, celkem zřejmá (pan prezident 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ď konkrétně.
1. Prezident Zeman je orel (to je opak našeho tvrzení).
2. Každý orel létá, a tudíž prezident Zeman létá taky (a hned to v praxi otestujeme).
3. Pozveme pana prezidenta na nádvoří a ouha! Zjistíme, že on nelétá.
A protože prezident nelétá (to je spor s realitou, ve které orlové létají), je jasné, že náš předpoklad (1) byl špatný a pan prezident 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 prezident je sice orel, ale přitom 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 orlím příkladu jsem si dovolil apelovat 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 nemusejí 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.
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 = 2 x 3 x 5 x 5. Není potřeba zabíhat do algebraických detailů toho procesu – jak se to konkrétně 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 = 5 x 7. Číslo následující je 36 a ani 5, ani 7 ho nedělí.
(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.)
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 čí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.)
Fakta máme po kupě.
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 čí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. Čí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.
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. Číslo K+1 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.
Článek je redakčně upravenou verzí blogového příspěvku na serveru
iDNES.cz. Publikováno s laskavým svolením autora.
Další díly a původní texty jsou dostupné na blogu Jana Řeháčka.
