Mikä on todistus

Todistukset ovat koko matematiikan peruskiviä. Todistusten avulla voit rakentaa muutamasta pikkukivestä koko pyramidin, ja vielä ylösalaisin.

Todistusten tarkoitus

Todistuksilla on matematiikassa useita tarkoituksia. Pääsyy on se, ettemme ilman todistuksia pysty vahvistamaan mitään mieleemme tulevaa ajatusta tai hypoteesia. Voisimme esimerkiksi uskoa, että alkulukuja on äärellinen määrä, mutta jos meillä ei ole todistusta, siitä tulee pelkkä tyhjä väite. Toisaalta myös todistamattomilla väitteillä on matematiikassa (ja muualla) merkitystä. Sanotaan yksinkertaisesti, että jos pätee oletus, että alkulukuja on äärellisen monta, niin pätee… jokin toinen teoria.

Sitten emme saa ihmetellä, jos joku todistaa aikanaan, että alkulukuja on äärettömän monta, kuten näemme myöhemmin, ja koko teoriamme romahtaa kuin korttitalo. Todistusten ansiosta voimme siis rakentaa korttitaloja, jotka eivät romahda koskaan.

Syy siihen, miksi todistuksia opetetaan kouluissa, on se, että joka ymmärtää todistuksen, ymmärtää myös kyseisen asian. Yleensä on vaikea ymmärtää asiaa kunnolla ilman, että ymmärtää todistuksia. Korostin sanaa ”ymmärtää” aivan tarkoituksella: jos nimittäin opettelet todistukset ulkoa päivää ennen koetta ja oksennat ne seuraavana päivänä paperille, se ei tarkoita, että olisit lähempänä asian ymmärtämistä.

Todistukset vastaavat siis jonkin asian oppimisessa kysymykseen ”miksi se toimii näin?” Kun ymmärrät, miksi asia toimii, muistat sen helpommin, ja ajan kuluessa ymmärrät asian ehdottomasti paremmin kuin se, joka opiskeli pänttäämällä. Kysymys kuuluu, onko tämä tavoitteesi.

Mikä todistus on

Se, mikä todistus on, määritellään muodollisesti matemaattisessa logiikassa esimerkiksi syntaktisen seurauksen avulla, mutta me tulemme toimeen paljon yksinkertaisemmalla määritelmällä.

Jokaisen todistuksen alussa meillä täytyy olla väite, jonka haluamme todistaa. Merkitsemme tätä väitettä taianomaisella symbolilla ϕ. Se on kreikkalainen kirjain, joka luetaan ”fii”. Lisäksi tarvitsemme jonkin aksioomien ja oletusten joukon, jota merkitsemme Ax ja jonka avulla todistamme väitteen ϕ. Aksioomien joukko on jotain, minkä jo tiedämme, minkä oletamme pätevän. Niitä voivat olla esimerkiksi asiat kuten ”jokainen parillinen luku on samalla jaollinen kahdella”. Lisäksi tämä joukko voi sisältää esimerkiksi lausekkeiden muokkauskaavoja, jotka on todistettu jossain muualla ja joiden oletamme jo pätevän, esimerkiksi:

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

Nyt muokkaamme joukon Ax väitteitä vähitellen, kunnes saamme väitteen ϕ. Kaikkien muokkausten täytyy olla loogisesti oikeita, niiden täytyy vastata perustason propositiologiikkaa. Jos haluaisimme esimerkiksi todistaa edellisen kaavan, etenisimme niin, että lauseketta

$$(a+b{)}^2$$

muokataan yhtäpitävillä muunnoksilla, kunnes saamme oikean puolen lausekkeen. Näytän:

$$(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$$

Ensimmäisessä vaiheessa kirjoitimme potenssin tuloksi, toisessa vaiheessa kerroimme sulut auki, kolmannessa vaiheessa laskimme yhteen samanlaiset termit ja viimeisessä vaiheessa kirjoitimme tulon potenssina. Jokainen vaihe oli jokin alkeismuunnos, jonka saimme tehdä, ja oletamme, että jokainen näistä alkeismuunnoksista sisältyy joukkoon Ax.

Tärkeää on, että jokaisen muunnoksen täytyy olla pätevä, sen täytyy perustua johonkin, minkä jo tunnemme. Matemaattinen todistus on jotain evoluution kaltaista: pienten vaiheittaisten muutosten avulla saamme yhdestä lausekkeesta toisen.

Triviaalit todistukset

Triviaali todistus (tai ilmeinen todistus) on terminus technicus todistukselle, joka ei mahdu taululle, joten se ohitetaan ja opiskelija opettelee sen kotitehtävänä monisteesta. :-) Vakavasti puhuen: triviaalit todistukset ovat todistuksia, jotka seuraavat tyypillisesti jostakin määritelmästä yhdellä triviaalilla askeleella.

Kokeillaan esimerkillä: olkoon meillä positiivisten kokonaislukujen joukko eli lukujen joukko ℤ⁺ = {1, 2, 3, …}. Voimme nyt sanoa, että jokainen murtoluku, jonka muoto on

$$\frac{q}{p};q,p\in {\mathbb{Z}}^{+}$$

on kelvollinen murtoluku, eli emme löydä yhtään lukuparia q, p, jolle annetulla murtoluvulla ei olisi merkitystä. Miten todistaisimme sen? Ensin täytyy keksiä, milloin murtoluvulla ei ole merkitystä. Murtoluvulla ei ole merkitystä, kun nimittäjässä on nolla (nollalla ei voi jakaa). Meidän täytyy siis todistaa, että p ≠ 0 kaikilla mahdollisilla p:n arvoilla. Me kuitenkin tiedämme, että p otetaan positiivisista kokonaisluvuista, jotka olemme määritelleet ℤ⁺ = {1, 2, 3, …}. Positiivisten kokonaislukujen joukko ei sisällä nollaa, joten luku p on aina nollasta poikkeava.

$$\mathrm{\forall }p\in {\mathbb{Z}}^{+}:p\ne 0$$

Ja todistus on valmis. Tiedämme, että jos murtoluvun sekä osoittaja että nimittäjä ovat positiivisia kokonaislukuja, murtoluku on kelvollinen.

Triviaalit todistukset ovat yleensä todella triviaaleja, mutta vain jos tunnet ympäröivän asiayhteyden. Jos esimerkiksi et ymmärrä käsitettä joukko tai et tiedä, mitä tarkoittaa, että p on joukon ℤ⁺ alkio, tämäkään todistus ei ollut sinulle triviaali. Triviaaleille todistuksille on siis ominaista pikemminkin se, että ne ovat lyhyitä ja seuraavat helposti jostakin (mielivaltaisen vaikeasta) asiayhteydestä, kuin se, että ne olisivat yksinkertaisia.

Vastaesimerkki

Vastaesimerkki on luultavasti yksinkertaisin tapa todistaa, ettei annettu väite ole tosi. Tärkeä sana on tässä ei. Vastaesimerkki voi nimittäin osoittaa tapauksen, jossa annettu väite ei päde, mutta yleensä ei riitä edes kuinka monta esimerkkiä tahansa silloin, kun testattavia alkioita on äärettömän monta.

Esimerkki: ”jokainen luonnollinen luku on suurempi kuin kymmenen”. Miten todistamme, ettei se ole totta? Vastaesimerkki väitteellemme on esimerkiksi luku viisi. Luku viisi on luonnollinen luku, eikä se ole suurempi kuin kymmenen. Väitettä emme voi todistaa luettelemalla muutamia luonnollisia lukuja, jotka ovat suurempia kuin kymmenen. Et voi sanoa ”luonnolliset luvut 11, 12, 13, 123 ja 5345 ovat suurempia kuin 10, joten väite on tosi”. Se ei käy. Valitsimme vain muutaman esimerkin, joille väitteemme pätee, mutta se ei kerro mitään muista luvuista, joista emme maininneet mitään.

Toinen esimerkki: jokaisella yli kaksi metriä pitkällä miehellä on ruskeat tai siniset silmät. Oletan, että vain harva pystyy löytämään vastaesimerkin. Mitä se kertoo meille väitteestä? Ei yhtään mitään. Jos emme pysty löytämään vastaesimerkkiä, se ei välttämättä tarkoita, että väite on tosi. Vastaesimerkki voi jossain olla olemassa, emme vain satu löytämään sitä. Kyvyttömyys löytää vastaesimerkki ei todista, että väite on tosi.

Suora todistus

Todistuksen perustyyppi on suora todistus. Etenemme kuivasti määritelmän mukaan ja muokkaamme alkuperäistä väitettä, kunnes saamme väitteen, jonka halusimme saada. Tyypillisesti haluamme todistaa väitteen, jonka muoto on implikaatio A ⇒ B, missä A on jokin lähtökohta eli oletus ja B on väite, jonka haluamme johtaa eli todistaa. Jos väite A pätee, niin väite B pätee. Usein meillä on annettuna vain väite B eli se, mitä haluamme todistaa, ja väitteen A meidän täytyy valita itse sopivasti.

Seuraa menettely, jossa implikaatioiden avulla johdamme uusia väitteitä, ja viimeisenä väitteenä on väite B. Kaaviona sen voisi kirjoittaa näin:

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

Esimerkkinä todistamme, että väite

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

pätee. Nyt vaihe vaiheelta:

1. Koska a>1, varmasti pätee myös a>0 ja myös a ≠ 0 (itse asiassa vain heikennämme ehtoa).
2. Koska a ei ole nolla ja on positiivinen, voimme huoletta kertoa koko epäyhtälön muuttujalla a. Jos a olisi nolla, aito epäyhtälö ei säilyisi (saisimme 0>0), ja jos se olisi negatiivinen, meidän pitäisi kääntää epäyhtälön suunta. Kun kerromme muuttujalla a, saamme lausekkeen a²>a.
3. Nyt tiedämme, että a>1, ja samalla tiedämme, että a²>a. Kun yhdistämme nämä kaksi lauseketta, saamme: a²>a>1.
4. Tästä poistamme vain keskimmäisen lausekkeen, ja meillä on lauseke a²>1. Sen saimme tehdä, koska a on suurempi kuin yksi ja a² on suurempi kuin a. Jos a² on suurempi kuin a ja a on samalla suurempi kuin yksi, niin a² on varmasti suurempi kuin yksi.

Symbolisesti voisimme kirjoittaa sen näin:

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

Epäsuora todistus

Epäsuora todistus hyödyntää enemmän implikaation ominaisuuksia. Jos meidän pitää todistaa väite muodossa A ⇒ B, voimme käyttää kontrapositiota ja todistaa

$$\mathrm{\neg }B\Rightarrow \mathrm{\neg }A.$$

Tämä menettely voi olla joskus edullisempi kuin esimerkiksi suora todistus. Samankaltaista menettelyä käyttää ristiriitatodistus, jonka muotoon jokaisen epäsuoran todistuksen voi muuttaa. Kokeillaan todistaa epäsuorasti väite

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

Muodostetaan nyt implikaation kontrapositio:

$$\begin{array}{rcl}\mathrm{\neg }(a=b)& \Rightarrow & \mathrm{\neg }(a-b=0)\\ a\ne b& \Rightarrow & a-b\ne 0\end{array}$$

Jos a ≠ b, voimme jakaa b:n summaksi b = a + x, missä x kuvaa luvun b etäisyyttä luvusta a. Lauseke muuttuu näin:

$$a\ne (a+x)\Rightarrow a-(a+x)\ne 0;x\ne 0$$

Vähennämme ne muuttujat a, jotka voimme:

$$0\ne x\Rightarrow -x\ne 0;x\ne 0$$

Koska x ≠ 0, myös −x ≠ 0, joten implikaatio pätee. Väite on todistettu, joten myös alkuperäinen väite

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

pätee.

Muita todistustekniikoita ovat esimerkiksi jo mainittu ristiriitatodistus tai induktiotodistus.

Lisälähteitä

• Matemaattinen todistus Wikipediassa