Logika v matematice

Začneme nástinem, jak je matematika vystavěna, a představíme jazyk matematiky, zejména ukážeme několik konvencí, kterým je třeba rozumět. Pak se podíváme na důkazy.

Jazyk matematiky

Matematika je studium umělých světů myšlenky, které mají jeden důležitý prvek: Vše je tam bílé něbo černé, proto lze aplikovat formální logiku, což také znamená, že výsledky jsou zcela spolehlivé, protože je jejich pravdivost dokázána. Abychom viděli, jak se k tomu dospěje, musíme na to jít od začátku. Matematika studuje objekty, ale ne skutečné (kameny, žáby, hvězdy), ale objekty ideální, či lépe řeeno kategorie ideálních objektů. Jednou takovou kategorií mohou být reálná čísla, jinou sudá čísla, další třeba reálné funkce a podobně.

Pokud chceme spolehlivé odpovědi, je potřeba mít ty kategorie zcela jasné, bez nějakých šedí. Pokud si například vezmeme nějaké číslo, tak musí být jasné, jestli je sudé či ne. Jinými slovy, musí existovat nějaký test, který dává jasné odpovědi. V tomto případě je test jasný, zkusíte si dané číslo vyjádřit jako dvojnásobek nějakého celého čísla. Pokud to lze udělat, máte sudé číslo, jinak ne. Nejlepší na tom je, že si všichni na celém světě mohou udělat stejný test a dojdou k přesne stejné odpovědi.

Teď již asi dokážete docenit, jak zásadní takováto jasná vymezenost situací je. Je to velký rozdíl ve srovnání například s uměním (žádný test nepomůže rozhodnout, jestli je něco krásné či ne), psychologií (žádná jistota, jestli je někdo normální či ne), filosofií atd. Právě tento nedostatek přesnosti nedovolí těmto oborům dosahovat spolehlivých výsledků.

Zpět k matematice. Je zjevné, že než něco začneme zkoumat, tak si musíme vyjasnit, o čem vlastně mluvíme, čili je třeba definovat přesně, jaké objekty zkoumáme. Matematická pojednání tedy tradičně začínají definicemi. Definice je kus textu, kde uvedeme na scénu novou kategorii (jméno pro objekt či vlastnost) a test, podle kterého můžeme poznat, zda libovolný objekt, na který se podíváme, patří do této nové kategorie či ne.

Bylo by možné napsat takovou definici (či kterékoliv jiné matematické tvrzení) čistě pomocí logických symbolů, ale pak by se to obtížně dešifrovalo. Proto v matematických knihách a článcích najdete ony krásné logické spojky jen zřídka, matematici dávají přednost lidským slovům, pokud je to možné. Matematika si proto vyvinula vlastní jazyk, který logické výroky vyjadřuje způsobem bližším tomu, jak mluví normální lidé, přičemž zachovává přesnost myšlenek. Cestou také přibrala pár zvláštností, které by měl člověk znát, aby věcem správně rozuměl.

Například definice sudého čísla by mohla vypadat takto.

Nechť n je celé číslo. Řekneme, že je sudé, jestliže existuje celé číslo k takové, že n = 2⋅k.

První věta nás uvádí do situace, soustřeďuje naši pozornost na určitý typ objektu, který je už znám (byl definován). Ve druhé větě vytvoříme speciální skupinu celých čísel (sudá) pomocí podmínky, která rozhodnuje, zda má jisté celé číslo tuto vlastnost či ne. Poznamenejme, že uvozovací věta není zcela nutná, popřípadě tam můžeme použít jinou kategorii, například můžeme povolit n z množiny reálných čísel či dokonce použít ještě obecnější kategorii. Když si tam dovolíme víc objektů, tak nic nezkazíme, protože čísla jiná než celá stejně nemají šanci projít dotyčným testem. Jenže bychom tím mohli ztížit pro čtenáře porozumění, takže využíváme první větu na to, abychom čtenáře dopředu nasměrovali tam, kde má nový pojem smysl.

Obecně má typická definice následující formát.

Řekneme, že objekt x splňuje vlastnost V (nebo že jej nazýváme V), jestliže splňuje následující podmínku P.

Myšlenka je jednoduchá. Je nám dán nějaký objekt, my aplikujeme určený test a podle toho, jak vyjde, tak onen dotyčný objekt buď nazveme nebo nenazveme V. Všimněte si, že je zde obousměrný vztah, což znamená logickou ekvivalenci. Naše definice výše je ale psána jako implikace! Může za to tradice, z nějakého důvodu se před dávnými časy matematici rozhodli psát definice jako implikace a už to zůstalo. Ačkoliv to není technicky korektní, všichni matematici vědí, že ve skutečnosti jsou definice ekvivalence, takže necítí potřebu tuto tradici měnit, konec konců, pokud se něco dělá už pár set let ve většině jazyků, tak je to těžké změnit. Můžete to považovat za cechovní tajemství, definice jsou ekvivalence, i když se píšou jinak.

Toto je v zásadě jediný otevřený spor mezi jazykem matematiky a formální logikou. Posuňme se dále. Když už jsme si definovali nějaké typy objektů, tak je začneme zkoumat a objevíme o nich nějaká fakta, tedy výroky, které jsou ve světě matematiky vždy pravdivé, často jim říkáme věty. I u nich dáváme přednost poněkud lidštějšímu jazyku.

Abychom to ukázali, budeme uvažovat typický matematický výrok (větu ve formě implikace) a podíváme se na rozličné způsoby, kterými jej matematici mohou vyjádřit. Protože zde nejsou žádná striktní pravidla, bude se názor na to, co je ještě správné a co už ne, lišit podle toho, jak moc je ten který matematik upjatý. Někteří hodně dají na formální správnost (v době svého promarněného mládí jsem dokonce zacházel tak daleko, že jsem i definice psal jako ekvivalence, ale už jsem od té doby zmoudřel), jiné matematiky spíše zajímá, jak dobře se takový výrok čte. Typická věta v knize může vypadat následovně.

Věta.
Nechť f je funkce definovaná na nějakém otevřeném intervalu I. Jestliže je f diferencovatelná na I, pak je také spojitá na I.

Zase jsme začali s preambulí, říká, o jakých objektech v této větě budeme mluvit. Tato forma je sice asi nejpoužívanější, ale zase není z logického pohledu úplně korektní tak, jak je napsána. Jmenovitě tam na dvou místech chybí slovo "libovolný". Chceme, aby tato věta platila pro všechny funkce na všech intervalech. Lepší verze by tedy byla tato.

Věta.
Nechť f je libovolná funkce definovaná na libovolném otevřeném intervalu I. Jestliže je f diferencovatelná na I, pak je také spojitá na I.

Málokterý matematik je ale natolik formální, aby to tak psal. Máme tedy další konvenci k zapamatování: Slovo "nechť" v preambuli v sobě skrývá i "pro každé", pokud není řečeno jinak (kdyby třeba věta začínala "Nechť existuje nějaká věc", pak už je tam existenční kvantifikátor). Správný překlad naší věty do logického jazyka by tedy byl následující:

Věta.
Pro každý otevřený interval I a pro každou funkci f definovanou na I platí následující:  Jestliže je f diferencovatelná na I, pak je také spojitá na I.

Teď už je to zapsáno logicky správně, takže to dokonce můžeme přepsat pomocí kvantifikátorů:

Věta.
∀ a < b ∈ ℝ^*   ∀ f funkci na I = (a,b):  ( f je diferencovatelná na I  =>  f je spojitá na I ).

S trochou praxe se dají tvrzení napsané matematičtinou snadno překládat do korektních logických výroků s kvantifikátory. Většinou je to zjevné.

Začali jsme s obvyklým jazykem matematiky a posunuli jsme se směrem k formálnějšímu tvaru. Někdy se ovšem pohybyjeme opačným směrem, zejména když o matematice jen mluvíme. Velmi kompaktní formulace může vvypadat takto:

Věta.
Diferencovatelné funkce jsou spojité.

Tohle už je na hranici, použilo by se to spíš neformálně, dost matematiků už by významně pozdvihlo obočí, kdyby tohle vidělo vytištěno. Hlavním problémem je, že se v tomto vyjádření neříká, jaké funkce jsou uvažovány, což je - z formálního hlediska - docela vážný prohřešek proti slušnému vychování (a většina matematiků je na tohle háklivá). Je nicméně pravdou, že zkušený matematik si chybějící části hravě sám doplní a ocení stručné vyjádření podstaty, což je užitečné při přednášce nebo když jen chceme odkázat na známý fakt.

Jedna z věcí, na kterou jsou matematici hrdí, je to, že všechna tvrzení jsou 100% spolehlivá, protože všechno je dokázáno (dobře, skoro všechno, s výjimkou axiomů, viz níže). Vzhledem k tomu, že většina tvrzení jsou implikace, budeme se zde soustředit hlavně (ale ne výhradně) na rozličné způsoby dokazování implikací. Uvažujme tedy jednu konkrétní implikaci p => q. Jak bychom ji mohli dokázat?

Každá implikace je splněna, když je předpoklad nepravdivý, takže tento případ je irelevantní při rozhodování, zda je nějaká implikace pravdivá či ne. Klíčovou situací je ta, kdy je předpoklad splněn. Pak se musíme zeptat, zda platí i závěr. Pokud tomu tak opravdu je ve všech případech, pak je dotyčná implikace vždy pravdivá. Pokud nastane případ, kdy předpoklad platí a závěr ne, pak implikace selhala. Jinými slovy, je třeba ukázat, že případ "předpoklad platí—závěr neplatí" nikdy nemůže nastat.

To nás přivádí k zajímavému rozcestí. Když máme tvrzení, pak jsou dvě možnosti, o které se můžeme pokusit: Buď jej dokázat, nebo dokázat, že neplatí, tomu říkáme, že jsme tvrzení "vyvrátili". Abychom tedy vyvrátili implikaci, stačí ukázat jediný případ, kdy je její předpoklad splněn a závěr nesplněn. Typický případ: Implikace "Jestliže je číslo prvočíslem, tak je liché" je nepravdivá, což dokážeme poukázáním na protipříklad, jmenovitě číslo 2. Na druhou stranu implikace "Jestliže je číslo větší než 2 prvočíslem, pak je liché" je pravdivá. Jedna možnost, jak to dokázat, by byla projít všechna prvočísla větší než 2, ale těch je nekonečně mnoho a většina z nás nemá tolik času. Je tedy třeba zkusit jiné metody, takové, které nám umožní pracovat s nekonečně mnoha čísly najednou. Tato situace je typická. Většina matematických tvrzení začíná obecným kvantifikátorem, což ve většině případů znamená, že máme ukázat, že něco funguje pro nekonečně mnoho případů. Abychom ale obecný kvantifikátor vyvrátili, stačí najít jen jeden protipříklad.

Tato dualita je v jistém směru univerzální. Některá dokazovaná matematická tvrzení obsahují existenční kvantifikátor, například "pro takovou a takovou rovnici existuje řešení." Pak jsou role obráceny. Abychom takové tvrzení dokázali, stačí ukázat jedno řešení, které funguje. Naopak k vyvrácení takového tvrzení potřebujeme ukázat, že žádný potenionální kandidát nefunguje, což znamená ukázat něco o nekonečně mnoha objektech.

Teď už se ale vraťme k problému dokazování implikací.

Přímý důkaz funguje následovně. Protože nás zajímá jen co se stane, když je předpoklad splněn, tak prostě předpokládáme, že se tak stalo, a pak tento předpoklad použijeme k vystavění nějakého argumentu, který ukáže, že musí platit i závěr. Protože krok od předpokladu k závěru většinou nebývá jednoduchý (snadným věcem neříkáme Věta), snažíme se to většinou rozložit na mnoho malých krůčků, které už jsou zjevné. Namísto ospravedlňování velkého skoku p => q se tedy ukáže spousta malých:

p => p₁ => p₂ => ... => p_n => q.

Každá z těchto malých implikací musí být buď něco tak jednoduchého, že je platnost zjevná, nebo něco, co již bylo dokázáno dříve, dá se také čekat, že v některém kroku musíme použít předpoklad dokazované implikace.

Mnoho důkazů spadá to kategorie přímého důkazu, takováto přímá cesta ale není vždy možná. Někdy se důkaz vine klikatějšími cestami, které se dokonce mohou rozdvojovat a zase spojovat, ale dokud to funguje tak, že začneme s p a po čase skončíme s q, tak je to přímý důkaz.

Příklad: Dokažte následující tvrzení:

Nechť x je reálné číslo. Jestliže je kladné, tak je také x⋅(x + 1) kladné.

Pomocí definice kladného čísla si to můžeme přepsat v následující logický výrok.

Pro každé reálné číslo x:  [jestliže x > 0, pak také x⋅(x + 1) > 0].

Pro ono konkrétní reálné číslo x (ať už je jakékoliv) potřebujeme ukázat, že splňuje dotyčnou impikaci. Zkusíme přímý důkaz, takže vezmeme předpoklad implikace jako daný a uvidíme, co z něj půjde odvodit. Máme teď tedy číslo x, o kterém víme, že je reálné a také že je kladné. Jako první mezikrok ukážeme, že pak také x + 1 > 0. Začneme tím, že vezmeme danou nerovnost x > 0 a přičteme 1 k oběma stranám, což je platná operace pro všechny nerovnosti s reálnými čísly, proto je to korektní krok. Dostaneme x + 1 > 1. Máme tedy řetěz nerovností x + 1 > 1 > 0 a proto x + 1 > 0, přesně jak jsme tvrdili.

Teď důkaz dokončíme druhým krokem. Víme, že každou nerovnost je možné vynásobit kladným číslem a ona zůstane pravdivou. Můžeme tedy x + 1 > 0 vynásobit číslem x (předpokládali jsme jeho kladnost, tudíž to lze považovat za platné) a dostaneme x⋅(x + 1) > 0, čímž je důkaz hotov.

Poněkud komplikovanější, ale také více poučný přímý důkaz lze nalézt zde. Doporučujeme se na něj podívat.

Nepřímý důkaz funguje tak, že namísto dokazování kýžené implikace dokážeme její obměnu. To má smysl, protože víme, že implikace a její obměna mají přesně stejnou pravdivost, takže cokoliv dokážeme o obměně (pravdivá, nepravdivá), bude to platit i pro původní implikaci. Protože tato obměna je výrok, který je také implikace, můžeme ji dokázat například přímým důkazem, jak bylo vysvětleno výše.

Příklad: Dokážeme, že každé prvočíslo větší než 2 je liché. Jedno možné formální vyjádření vypadá takto:

∀n∈{x∈ℕ; x > 2}: [jestliže je n prvočíslo, pak je n liché].

Toto tvrzení zase začíná obecným kvantifikátorem, takže začneme tím, že si vezmeme libovolné přirozené číslo n, které je větší než 2. To znamená, že když začneme náš důkaz, budeme moci použít všechno, co je známo o přirozených číslech, a také fakt, že n > 2. Musíme dokázat, že pro toto n platí následující implikace:

n je prvočíslo  =>  n je liché.

Zde by ale byl přímý důkaz poněkud nešikovný. Měli bychom začít předpokladem, že je n prvočíslo, ale definice prvočísla není příliš pohodlná na práci (říká, že n nelze napsat jistým způsobem, což je negativní tvrzení) a není jasné, kam by se z toho dalo vyjít. Proto se rozhodneme raději dokázat obměnu:

n není liché  =>  n není prvočíslo.

Jinými slovy,

n je sudé  =>  n není prvočíslo.

Dokazování této implikace vypadá snadněji, protože začíná určitou konkrétní informací: n je sudé. Teď tedy předpokládáme, že máme přirozené číslo n větší než 2, které je navíc sudé. To znamená, že existuje celé číslo k takové, že n = 2k. Vše teď záleží na k, co o něm víme? Protože n > 2, musí být nutně k > 1. Dokázali jsme rozložit n jako součin dvou přirozených čísel různých od 1, takže n není prvočíslo a obměna je dokázána. Proto je pravdivá také původní implikace.

Tento příklad ukazuje, proč by mohlo být užitečné přejít k obměně: Vlastnosti použité v původní implikaci se mohou po negaci vylepšit. V typickém případě to bývají vlastnosti, které zahrnují relaci "není rovno", pak ji negace změní v rovnost, což je z praktického pohledu mnohem příjemnější relace. To je třeba případ definice prosté funkce. Další dobrý důvod může být, že negace změní kvantifikátor z obecného na existenční a naopak, což také někdy pomůže. Někdy se nám prostě víc líbí začít na "druhém konci" implikace.

Poznámka: Tvrzení o prvočíslech se dá formálně vyjádřit i jinými způsoby, například takto:

∀n∈ℕ: [jestliže je (n prvočíslo a n > 2), pak je n liché].

Toto je stejně dobrý způsob vyjádření našeho faktu, ale když pak přejdeme k obměně, museli bychom negovat tu konjunkci nalevo, což se zdá jako víc práce, než co jsme dělali v našem důkazu výše. Toto je v jistém smyslu typické. Často existuje více způsobů, jak formálně vyjádřit jistou myšlenku, a podle toho, jaký si zvolíme, se důkaz může pohybovat od relativně snadného k docela dlouhému.

Uvažujme nějaký výrok r (ne nutně implikaci). Jedna možnost, jak dokázat jeho pravdivost, je udělat důkaz sporem. Předpokládáme, že r není pravdivý, a pak ukážeme, že to je v nějakém konfliktu se známými fakty. To pak ukazuje, že r musí být pravda. Stojí za to podívat se na tuto úvahu blíže. Formálně vypadá důkaz sporem tak, že dokážeme platnost následující implikace:

¬ r => F.

Co nám to dává? Závěrem této implikace je nepravdivý výrok, a jediná možnost, jak taková implikace může být pravdivá, je mít také nepravdivý předpoklad. Ale ¬ r nepravdivé znamená, že r platí, přesně jak jsme potřebovali.

Důkaz sporem je užitečný, když se dokazuje, že se něco nemůže stát. To je "negativní" informace, což se obvykle těžce dokazuje. Důkaz sporem začíná negací, tedy předpokladem, že se něco stane, což nám dá něco určitého do začátku.

Teď to aplikujeme na případ implikace. Potřebujeme ji znegovat, důkaz implikace p => q sporem znamená, že máme ukázat platnost

(p a non q) =>  F.

Takže předpokládáme, že p platí, zatímco q neplatí, a pak ukážeme, že tyto dva předpoklady dohromady dávají nějaký nesmysl.

Příklad: Zkusíme znovu dokázat tvrzení výše o prvočíslech, tentokráte sporem. Vezměme si tedy libovolné přirozené číslo n větší než 2. Potřebujeme ukázat, že když je to prvočíslo, pak je liché.

Protože chceme dělat důkaz sporem, budeme předpokládat, že toto číslo je prvočíslo, ale není liché. Pak ovšem musí být sudé, tudíž jej můžeme zapsat jako n = 2k pro nějaké přirozené číslo k. Protože předpokládáme, že n je prvočíslo, tak musíme mít k = 1 a proto n = 2. My ale také předpokládáme, že n > 2, což nás přivádí k závěru, že 2 > 2, rozhodně nepravdivé tvrzení. Důkaz sporem je tedy hotov.

V praxi málokdy docházíme až k nějakému explicitnímu nepravdivému tvrzení, obvykle skončíme trochu dříve, jakmile dojdeme ke konfliktu. V tom důkazu výše by to vypadalo takto: "...a proto n = 2, ale to je ve sporu s naším předpokladem n > 2. Důkaz hotov." Abychom to lépe ilustrovali, ukážeme ještě jeden důkaz sporem.

Příklad: Dokážeme, že neexistuje nejmenší kladné racionální číslo, což mimo jiné znamená, že racionální čísla nelze seřadit podle velikosti. Vyjádříme to přesně.

Množina kladných racionálních čísel nemá nejmenší prvek (minimum).

Záporná tvrzení je často prakticky nemožné dokázat přímo, takže negace — tedy důkaz sporem — se nabízí jako přirozený začátek. Předpokládejme tedy, že je tvrzení výše nepravdivé, tedy předpokládejme, že množina kladných racionálních čísel má nejmenší prvek, své minimum (viz Topologe reálných čísel v části Funkce - Teorie - Reálné funkce), nazvěme jej r. Protože je to racionální číslo, je také číslo r/2 racionální, k tomu je kladné. Proto je r/2 prvkem množiny kladných racionálních čísel a také r/2 < r, což je ve sporu s předpokladem, že r je minimum dotyčné množiny. Důkaz je hotov.

Všimněte si, že jsme nedošli až k nepravdivému výroku, ale zastavili jsme se u první konfliktní situace, přesně jak jsme to inzerovali výše. Pokud by někdo opravdu chtěl vidět, jak se dojde do konce, má to tady: Protože je r/2 kladné racionální číslo a r je minimum dotyčné množiny, musíme mít r/2 ≥ r. Vydělíme číslem r (kladné číslo, takže vydělením se nerovnost nezmění) a trochu to přeorganizujeme, čímž dospějeme k nerovnosti 1 ≥ 2, což je onen kýžený nesmysl.

Tímto uzavíráme sekci o důkazech.

Další důkaz nabízíme zde. Je to přímý důkaz, ale poněkud složitější, takže pro vás může být zajímavou výzvou si jej projít a snažit se mu porozumět.

Apendix: Axiomy a věci, na které se lze spolehnout.

Možná jste si všimli, že se v důkazech spoléháme na věci, které jsou již známé, ale ty bylo také třeba dokázat a ony důkazy musely použít něco spolehlivého a tak dále, kde to všechno skončí? Matematické teorie jsou jako stromy, ze známých tvrzení a vlastností se větví nahoru k dalším a dalším tvrzením, každé je dokázáno pomocí věcí, které jsou na stromě níže. Ale co jsou kořeny, co je na začátku? Popravdě řečeno, nic. V matematice neexistují žádná základní fakta, která by byla pravdivá sama od sebe.

To může čtenáře silně znejistět, podívejme se tedy na to blíže. Matematici strávili spoustu času procházením důkazů a přišli s relativně krátkým seznamem věcí, které jsou třeba, aby už šlo vybudovat celý zbytek. Rozhodli se ony klíčové věci akceptovat, těmto základním faktům se říká axiomy. Definují základní pravidla a celý zbytek matematiky z nich vyplývá. Když tedy matematik řekne, že je něco pravdivé, tak to vlastně znamená, že je to pravda za předpokladu, že jsou coby pravdivé akceptovány také všechny standardní axiomy. Kde se vzaly ty axiomy? Protože chceme, aby byla matika užitečná, axiomy jsou zvoleny tak, aby souhlasily s tím, jak se nám jeví okolní svět (něco jako "1 + 1 = 2"). Zatím se zdá, že ony základní axiomy byly vybrány dobře, protože výsledky získané na jejich základě fungují.

To nicméně neznamená, že v ně matematici musí věřit. Dokonce si mnozí matematici rádi hrají a jen tak ze zvědavosti zkouší, co by se stalo, kdyby zkusili začít s jinou množinou axiomů. Dostávají tak alternativní matematické teorie, popisy světů, kde věci fungují jinak než v tom našem, dokonce i malá změna v základních axiomech může mít dalekosáhlé dopady. Některé z těchto světů jsou fascinující a zaslouží si další studium, některé jsou srandovní a další podivné. Asi nejúžasnější ovšem je, že se některé z těchto odlišných světů ukazují jako užitečné. V 19. století se například matematici snažili vykoumat, jak by věci fungovaly ve světě geometrie (přímky, úhly, rovnoběžky atd.), který není úplně jako ten, na který jsme zvyklí (změnili si jeden axiom). K všeobecnému překvapení byly tyto výsledky přesně tím, co později Einstein potřeboval k popisu vesmíru. Podobně byli matematici zvědaví, co se stane s prostory, když se jejich dimenze zvětší do nekonečna. Takové nekonečně-dimenzionální prostory se pak staly klíčovým nástrojem pro fyziky, když si začali hrát s atomy (kvantová teorie).

Abychom to shrnuli, je také možné se na matematiku dívat následovně: Vytvoříme svět tím, že specifikujeme jeho objekty a nějaká základní pravidla, kterými se řídí (to jsou definice), matematika pak odvodí o takovém světě spolehlivé informace. Zkoumání světa, který není zcela jako náš, je dost těžké. Nemůžeme se opřít o své zkušenosti s fungováním věcí, nemůžeme dělat pokusy, nemůžeme používat naše smysly. Neustále hrozí nebezpečí, že podlehneme svodu a použijeme automaticky něco, co nám přijde samozřejmé, protože to známe z našeho světa. Jedinou obranou proti takové chybě je logika, ta nám zaručí, že vše, co o takovém světě tvrdíme, plyne jen z jeho základních pravidel. Její role coby anděla strážného korektnosti je kritická také při zkoumání světa našeho pomocí standardních axiomů, tam nás to zase chrání proti chybným předpokladům a dalším chybám úsudku. Tím končíme tuto poznámku a celou sekci.