Co je to důkaz

Důkazy jsou základními kameny celé matematicky, díky důkazům můžete z několiky málo kamínků postavit celou pyramidu a to ještě vzhůru nohama.

Smysl důkazů

Důkazy mají v matematice smysl z několika důvodů. Hlavní důvod je ten, že bez pomoci důkazů nejsme schopni potvrdit žádnou myšlenku či hypotézu, která nás napadne. Mohli bychom například věřit, že prvočísel je konečný počet, ale pokud nemáme důkaz, stává se to pouze bezduchým výrokem. Na druhou stranu i nedokázané výroky mají v matematice (a jinde) smysl. Zkrátka se řekne, že pokud platí předpoklad, že prvočísel je konečně mnoho, potom platí… nějaká jiná teorie.

Potom se ale nesmíme divit, že někdo za čas dokáže, že prvočísel je nekonečně mnoho, jak si ukážeme dále, a celá naše teorie se zhroutí jako domeček z karet. Díky důkazům tak můžeme stavět domky z karet, které se nezhroutí nikdy.

Důvod, proč se důkazy učí na školách je ten, že kdo porozumí důkazu, porozumí i dané látce. Obvykle můžete jen těžko důkladně rozumět dané látce bez toho, aniž byste chápali důkazy. To slovo „chápali“ jsem zvýraznil naprosto záměrně, pokud se totiž důkazy naučíte nazpaměť den před zkouškou a další den to jen ze sebe vyblijete na papír, tak to neznamená, že jste blíže k porozumění dané problematiky.

Důkazy tak při učení nějaké látky odpovídají na otázku „proč to tak funguje?“ Pokud pochopíte, proč daná věc funguje, snadněji si ji zapamatujete a po čase budete dané látce rozumět rozhodně více než člověk, který se to učil stylem „nalejt — vylejt“. Otázkou je, jestli je toto váš cíl.

Co je to důkaz

Co je to důkaz se formálně definuje v matematické logice například pomocí syntaktického vyplývání, ale my si vystačíme s nějakou daleko jednodušší definicí.

Na začátku každého důkazu musíme mít tvrzení, které chceme dokázat. Toto tvrzení si označíme magickým symbolem $\phi$. Je to řecké písmeno, které čteme „fí“. Dále budeme potřebovat nějakou množinu axiomů a předpokladů, označíme Ax, pomoci kterých dokážeme tvrzení $\phi$. Množina axiomů je něco, co už víme, co předpokládáme, že platí. Mohou to být věci jako například „každé sudé číslo je zároveň dělitelné dvěma“. Dále může tato množina obsahovat například vzorce pro úpravy výrazů, které jsou dokázané někde bokem a už předpokládáme, že platí, například:

$$(a+b)^2=a^2+2ab+b^2;\qquad a,b\in\mathbb{R}$$

Nyní budeme postupně upravovat tvrzení v množině Ax tak, až dostaneme tvrzení $\phi$. Všechny úpravy musí být logicky správné, musí odpovídat základní výrokové logice. Například pokud bychom chtěli dokázat předchozí vzorec, budeme postupovat tak, že výraz

$$(a+b)^2$$

budeme upravovat ekvivalentními úpravami, až dostaneme výraz na pravé straně. Předvedu:

$$(a+b)^2=(a+b)\cdot(a+b)=a\cdot a+a\cdot b + b\cdot a + b\cdot b=$$

$$=a\cdot a+2ab+b\cdot b=a^2+2ab+b^2$$

V prvním kroku jsme mocninu rozepsali do součinu, ve druhém kroku jsme roznásobili závorky, ve třetím kroku jsme sečetli stejné výrazy a v posledním kroku jsme součin zapsali jako mocninu. Každý krok představoval nějakou elementární úpravu, kterou jsme si mohli dovolit, přičemž předpokládáme, že každá z těchto elementárních úprav je obsažena v množině Ax.

Důležité je, že každá úprava musí být platná, musí vycházet z něčeho, co už známe. Matematický důkaz je něco jako evoluce — postupnými malými úpravami dostaneme z jednoho výrazy výraz jiný.

Triviální důkazy

Triviální důkaz (nebo též zřejmý důkaz) je terminus technicus pro důkaz, který se nevejde na tabuli, takže se přeskočí a student se ho naučí ze skripta za domácí úkol. :-) Teď vážně — triviální důkazy jsou nějaké důkazy, které typicky vyplývají z nějaké definice v jednom triviálním kroku.

Zkusíme si to ukázat na příkladu: mějme množinu přirozených čísel, tj. množinu čísel ℕ = {1, 2, 3, …}. Můžeme nyní říci, že každý zlomek ve tvaru:

$$\frac{q}{p}; \qquad q,p\in\mathbb{N}$$

je platným zlomkem, tj. nenajdeme žádnou dvojici čísel q, p, pro které by zadaný zlomek neměl smysl. Jak bychom to dokázali? Nejprve potřebujeme přijít na to, kdy zlomek nemá smysl. Zlomek nemá smysl, když je ve jmenovateli nula (nemůžeme dělit nulou). Musíme tak dokázat, že p≠0 pro všechna možná p. My ale víme, že p bereme z přirozených čísel, která jsme si definovali jako ℕ = {1, 2, 3, …}. Množina přirozených čísel neobsahuje nulu, takže číslo p bude vždy různé od nuly.

$$\forall p\in\mathbb{N}: p\ne 0$$

A důkaz máme za sebou. Víme, že pokud bude čitatel i jmenovatel zlomku z přirozených čísel, bude zlomek platný.

Triviální důkazy obvykle opravdu triviální bývají, ale jen pokud znáte okolní kontext. Například pokud nerozumíte pojmu množina nebo nevíte co to znamená, že p je prvkem množiny ℕ, potom ani tento důkaz pro vás nebyl triviální. Triviální důkazy se tak nevyznačují ani tím, že jsou jednoduché, jako spíš tím, že jsou krátké a vyplývají jednoduše z nějakého (libovolně těžkého) kontextu.

Protipříklad

Protipříklad je asi nejjednodušší forma dokazování toho, že daný výraz není pravdivý. Důležité je to slovo není. Protipříklad totiž může poukázat na případ, kdy zadaný výrok neplatí, ale obecně ani sebevíc příkladů nestačí ve chvíli, kdy je ve hře nekonečně mnoho prvků, ze kterých můžeme testovat.

Příklad: „každé přirozené číslo je větší než deset“. Jakým způsobem dokážeme, že to není pravda? Protipříklad k našemu tvrzení je číslo pět, například. Číslo pět je číslo přirozené a není větší než deset. Tvrzení nemůžeme dokázat tak, že vyjmenujeme několik přirozených čísel, která jsou větší než deset. Nemůžete říct „přirozená čísla 11, 12, 13, 123 a 5345 jsou větší než 10, takže daný výrok je pravdivý“. To nejde. To jsme si pouze vybrali několik málo příkladů, pro které naše tvrzení platí, ale to nic neříká o ostatních číslech, o kterých jsme se nezmínili vůbec.

Druhý příklad: každý muž vyšší než dva metry má hnědé nebo modré oči. Předpokládám, že jen málokdo je schopen najít protipříklad. Co nám to říká o daném výroku? No, vůbec nic. Pokud nejsme schopni nalézt protipříklad, neznamená to nutně, že daný výrok je pravdivý. Protipříklad někde může existovat, jen ho zrovna nejsme schopni nalézt. Neschopnost nalézt protipříklad nedokazuje, že dané tvrzení je pravdivé.

Přímý důkaz

Základním typem důkazu je přímý důkaz. Suše postupujeme podle definice a upravujeme prvotní výrok, až dostaneme výrok, který chceme dostat. Typicky chceme dokázat výrok, který má tvar implikace $A\Rightarrow B$, kde A je nějaký výchozí bod, předpoklad a B je výrok, který chceme odvodit, dokázat. Jestliže platí výrok A, pak platí výrok B. Často máme zadaný jen výrok B, tj. to, co chceme dokázat, a výrok A si musíme vhodně zvolit sami.

Následuje postup, při kterém pomocí implikací odvozujeme další výroky a jako poslední výrok se nachází výrok B. Schematicky by se to dalo zapsat takto:

$$A\Rightarrow A_1\Rightarrow A_2\Rightarrow A_3\Rightarrow\ldots \Rightarrow A_n \Rightarrow B$$

Jako příklad si dokážeme, že platí výrok

$$a>1\Rightarrow a^2>1$$

Teď po krocích:

1. Protože a>1, jistě platí také a>0 a také a≠0 (vlastně jen zeslabíme podmínku).

• Protože a není rovno nule a je kladné, můžeme proměnnou a bez obav vynásobit celou nerovnici. Pokud by bylo a nulové, nemohli bychom násobit vůbec, pokud by bylo záporné, museli bychom obrátit nerovnost. Po vynásobení proměnnou a získáváme výraz a²>a.
• V tuto chvíli víme, že a>1 a zároveň víme, že a²>a. Pokud tyto dva výrazy složíme dohromady, získáme: a²>a>1.
• Odtud už jen odstraníme prostřední výraz a máme výraz a²>1. To jsme si mohli dovolit proto, že a je větší než jedna a a² je větší než a. Pokud je a² větší než a a a je zároveň větší než jedna, je jistě a² větší než jedna.

Symbolicky bychom to mohli napsat takto:

$$a>1\Rightarrow a>0 \Rightarrow a^2>a \Rightarrow a^2>a>1 \Rightarrow a^2>1.$$

Nepřímý důkaz

Nepřímý důkaz již více využívá vlastností implikace. Pokud máme dokázat tvrzení ve tvaru $A\Rightarrow B$, můžeme použít obměněnou implikaci a dokázat

$$\neg B \Rightarrow \neg A.$$

Tento postup může být někdy výhodnější než třeba přímý důkaz. Podobného postupu používá důkaz sporem, na který lze každý nepřímý důkaz převézt. Zkusíme si nepřímo dokázat tvrzení

$$a-b=0\Rightarrow a=b.$$

Nyní provedeme obměnu implikace:

$$\begin{eqnarray} \neg(a=b)&\Rightarrow&\neg(a-b=0)\\ a\ne b&\Rightarrow&a-b\ne0 \end{eqnarray}$$

Pokud se a≠ b, můžeme b rozložit na součet b = a + x, kde x představuje vzdálenost čísla b od čísla a. Výraz se změní takto:

$$a\ne (a+x)\Rightarrow a-(a+x)\ne0;\quad x\ne0$$

Odečteme ty proměnné a, které můžeme:

$$0\ne x\Rightarrow x\ne 0; \quad x\ne0$$

Vidíme, že všude máme, že x je různé od nuly, tvrzení je dokázáno, čímž platí i původní výrok

$$a-b=0\Rightarrow a=b.$$

Další dokazovací techniky jsou například již zmíněný důkaz sporem nebo důkaz indukcí.

Další zdroje

• Matematický důkaz na Wikipedii