Důkaz sporem

Důkaz sporem je oblíbená technika dokazování. Pokud chceme dokázat, že nějaký výrok platí, předpokládáme, že je pravdivý, pak ho znegujeme a pokusíme se dojít k nějakému sporu. Cílem je dokázat, že námi zvolený předpoklad vede k nějakému nesmyslu.

Triviální příklad

Mějme tvrzení „neexistuje nejmenší kladné racionální číslo“. Toto tvrzení dokážeme sporem tak, že tvrzení nejprve znegujeme: „existuje nejmenší kladné číslo“ a toto číslo si označme q. Pokud je q nejmenší kladné racionální číslo, pak nejsme schopni nalézt menší kladné racionální číslo — protože pak by číslo q nebylo nejmenší.

Toho využijeme při hledání sporu. Pokud přeci jen najdeme číslo, které je menší než q, které můžeme zvolit libovolně, pak jsme došli ke sporu a původní výrok neplatí. Pokud si za nejmenší číslo zvolíme například 0,1, tak vidíme, že číslo 0,01 je menší. Dále 0,001 je ještě menší, 0,0001 je zase menší a tak dále. Stačí dané číslo q vydělit desíti a dostaneme číslo menší. V podstatě ho stačí vydělit jakýmkoliv číslem, které je větší než jedna, třeba dvojkou — polovina čísla q bude jistě menší než celé číslo q.

Tedy číslo q/2 je jistě menší než q a zároveň je to číslo kladné. Tím jsme došli ke sporu se znegovaným tvrzením, tedy znegované tvrzení neplatí a tím pádem platí původní neznegované tvrzení.

Zajímavá čísla

Klasickým srandovním důkazem, který ilustruje princip sporu je následující příklad. Předpokládejme, že existují přirozená čísla, která jsou nějakým způsobem zajímavá. Například číslo 2 je zajímavé, protože platí, že 2 · 2 = 2 + 2, to je docela netypická vlastnost. Číslo 42 je zajímavé, protože je to odpověď na všechno. A podobně. Otázka zní — existuje nekonečně mnoho zajímavých čísel?

Předpokládejme opak, tj. že existuje pouze konečně mnoho zajímavých čísel a nějaká čísla jsou nezajímavá. Tato nezajímavá přirozená čísla uspořádáme do množiny nezajímavých čísel. Nyní vybereme nejmenší nezajímavé číslo. Moment, nejmenší nezajímavé číslo? To zní docela zajímavě, ne? :-)

Tím jsme došli ke sporu, protože nejmenší nezajímavé číslo je ve skutečnosti docela zajímavé, tedy nemůže existovat nejmenší nezajímavé číslo, tím pádem množina nezajímavých čísel musí být nutně prázdná.

Je to samozřejmě nesmysl, nemáme pořádně definované, co to je zajímavé číslo, ale samotný postup dokázání je v pořádku.

Důkaz nekonečnosti prvočísel

V tomto příkladě si ukážeme podobný postup jako v předchozí kapitole, ale tentokrát už to bude správné po všech stránkách.

Prvočíslo je číslo, které je dělitelné jen dvěma různými čísly — samo sebou a jedničkou. Všimněte si, že definici nevyhoví jednička a vyhoví dvojka.

Prvočíselný rozklad, neboli faktorizace, je rozložení přirozeného čísla, kromě jedničky, na součin prvočísel. Je to docela zajímavá vlastnost přirozených čísel. Ať si vezmete jakékoliv přirozené číslo (kromě té jedničky), pak platí, že ho lze rozložit na součin několika (i stejných) prvočísel. Příklady:

$$\begin{eqnarray} 8&=&2\cdot2\cdot2\\15&=&3\cdot5\\26&=&2\cdot13\\1800&=&2^3\cdot3^2\cdot5^2 \end{eqnarray}$$

Tvrzení o prvočíselném rozkladu se nazývá Základní věta aritmetiky. Mimo jiné nám říká, že takový rozklad je jedinečný, tj. nenajdeme dva různé prvočíselné rozklady jednoho přirozeného čísla. Dále pouze prvočísla mají prvočíselný rozklad tvořený pouze jedním číslem — sebou samými. Tedy prvočíselný rozklad sedmičky by bylo číslo sedm. Těchto faktů využijeme při konstrukci důkazu následujícího tvrzení.

Nyní dokážeme tvrzení, že „prvočísel je nekonečně mnoho“. Tvrzení si opět znegujeme: „prvočísel je konečný počet“. Předpokládejme, že posloupnost čísel

$$a_1, a_2, a_3,,\ldots,a_n$$

představuje všechna existující prvočísla. Pokud jsou v této posloupnosti všechna prvočísla, potom jistě platí, že už nebudeme schopni najít číslo, které by bylo prvočíslem a zároveň nebylo v této posloupnosti. Všechna prvočísla máme v posloupnosti, mimo posloupnost se už žádné prvočíslo vyskytovat nesmí.

Pokud chceme dojít ke sporu, musíme tak sestavit nějaké prvočíslo, které v této posloupnosti není. K tomu nám pomůže číslo q. To sestavíme tak, že vynásobíme všechna prvočísla v posloupnosti a přičteme jedničku:

$$q=a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n+1$$

Teď musíme ukázat, že toto číslo buď je prvočíslo, nebo nějak prvočíslo generuje. Víme, že q je přirozené číslo a že každé přirozené číslo lze vyjádřit jako součin prvočísel. Nicméně žádné prvočíslo a_i nedělí beze zbytku číslo q, vždy zbude po dělení jednička. Pokud bychom se pokusili číslo q vydělit například prvočíslem a₂, dopadli bychom takto:

$$\frac{a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n+1}{a_2}=\frac{a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n}{a_2}+\frac{1}{a_2}=$$

$$=a_1 \cdot a_3 \cdot a_4 \cdot \ldots \cdot a_n+\frac{1}{a_2}$$

Zlomek si nejdříve rozdělíme na dva. V prvním zlomku pokrátíme a₂ a zbude nám nějaký součin prvočísel, což je prostě nějaké jiné nepodstatné celé číslo. V druhém zlomku není co pokrátit, tento zlomek bude vždy nějaké necelé číslo (protože jmenovatel nemůže být jedna, jednička není prvočíslo). V součtu tak dostaneme číslo, které není celé, tedy prvočíslo a₂ nedělí číslo q.

Tím máme dokázáno, že žádné z prvočísel z posloupnosti a_n nedělí číslo q. (Poznámka: ukázali jsme to sice jen pro a₂, ale lze to jednoduše zobecnit pokud zaměníme a₂ za obecné a_i) Ale protože každé přirozené číslo lze rozložit na součin prvočísel, tak musí existovat jiná prvočísla, která nejsou v posloupnosti a_n, ale jsou faktorizací čísla q. Přitom samotné číslo q může být klidně prvočíslo a prvočíselný rozklad tak bude zahrnovat jen číslo q. Takže ještě jednou poslední myšlenkový pochod:

1. Každé přirozené číslo lze vyjádřit jako nějaký součin prvočísel.
2. Podle předpokladu obsahuje posloupnost a_n všechna existující prvočísla.
3. Upravíme první tvrzení tak, že každé přirozené číslo lze vyjádřit jako součin vybraných členů posloupnosti a_n, protože ta obsahuje všechna prvočísla.
4. Dokázali jsme, že žádné číslo z posloupnosti a_n nedělí číslo q.
5. Tím vznikl spor s předpokladem $\rightarrow$ pokud musíme být schopni rozložit každé přirozené číslo na součin prvočísel a posloupnost a_n neobsahuje žádné číslo, které dělí q, pak musí existovat jiná prvočísla, která dělí q a jsou prvočíselným rozkladem čísla q.

Tímto jsme došli ke sporu. Prvočíselný rozklad čísla q zahrnuje prvočísla, která nejsou obsažena v posloupnosti, o které jsme předpokládali, že obsahuje všechna prvočísla. Tedy neplatí znegované tvrzení, platí neznegované původní tvrzení. Prvočísel je nekonečně mnoho.