Ristiriitatodistus

Ristiriitatodistus on suosittu todistustekniikka. Jos haluamme todistaa, että jokin väite pätee, kiellämme sen, oletamme, että sen negaatio on tosi, ja yritämme päätyä ristiriitaan. Tavoitteena on todistaa, että valitsemamme oletus johtaa johonkin mahdottomaan.

Triviaali esimerkki

Olkoon väite ”pienintä positiivista rationaalilukua ei ole olemassa”. Todistamme tämän väitteen ristiriidan avulla niin, että kiellämme väitteen ensin: ”pienin positiivinen rationaaliluku on olemassa”, ja merkitsemme tätä lukua q:lla. Jos q on pienin positiivinen rationaaliluku, emme pysty löytämään sitä pienempää positiivista rationaalilukua, koska silloin luku q ei olisi pienin.

Tätä hyödynnämme ristiriitaa etsiessämme. Jos löydämme kuitenkin luvun, joka on pienempi kuin q, jonka voimme valita vapaasti, olemme päätyneet ristiriitaan ja kielletty väite ei päde. Jos valitsemme pienimmäksi luvuksi esimerkiksi 0,1, näemme, että luku 0,01 on pienempi. Edelleen 0,001 on vielä pienempi, 0,0001 on taas pienempi ja niin edelleen. Riittää jakaa annettu luku q kymmenellä, ja saamme pienemmän luvun. Itse asiassa riittää jakaa se millä tahansa ykköstä suuremmalla luvulla, vaikka kahdella: luvun q puolikas on varmasti pienempi kuin koko luku q.

Luku q/2 on siis varmasti pienempi kuin q ja samalla se on positiivinen rationaaliluku. Näin päädyimme ristiriitaan kielletyn väitteen kanssa, eli kielletty väite ei päde, ja siksi alkuperäinen kieltämätön väite pätee.

Mielenkiintoiset luvut

Klassinen hauska todistus, joka havainnollistaa ristiriidan periaatetta, on seuraava esimerkki. Oletetaan, että on olemassa luonnollisia lukuja, jotka ovat jollakin tavalla mielenkiintoisia. Esimerkiksi luku 2 on mielenkiintoinen, koska pätee 2 · 2 = 2 + 2, mikä on melko epätyypillinen ominaisuus. Luku 42 on mielenkiintoinen, koska se on ”vastaus kaikkeen”. Ja niin edelleen. Kysymys kuuluu: onko mielenkiintoisia lukuja äärettömän monta?

Oletetaan päinvastaista, eli että mielenkiintoisia lukuja on vain äärellisen monta ja jotkin luvut ovat mielenkiinnottomia. Nämä mielenkiinnottomat luonnolliset luvut kerätään mielenkiinnottomien lukujen joukkoon. Nyt valitsemme pienimmän mielenkiinnottoman luvun. Hetkinen, pienin mielenkiinnoton luku? Se kuulostaa aika mielenkiintoiselta, eikö? :-)

Näin päädyimme ristiriitaan, koska pienin mielenkiinnoton luku on itse asiassa melko mielenkiintoinen, eli pienintä mielenkiinnotonta lukua ei voi olla olemassa, joten mielenkiinnottomien lukujen joukon täytyy välttämättä olla tyhjä.

Tämä on tietenkin hölynpölyä, koska emme ole kunnolla määritelleet, mikä mielenkiintoinen luku on, mutta itse todistustapa on kunnossa.

Todistus alkulukujen äärettömyydestä

Tässä esimerkissä näytämme samanlaisen menettelyn kuin edellisessä luvussa, mutta tällä kertaa se on oikein joka suhteessa.

Alkuluku on luku, joka on jaollinen vain kahdella eri luvulla: itsellään ja ykkösellä. Huomaa, ettei ykkönen täytä määritelmää, mutta kakkonen täyttää.

Alkutekijähajotelma eli tekijöihin jako on positiivisen kokonaisluvun, ykköstä lukuun ottamatta, esittäminen alkulukujen tulona. Se on melko mielenkiintoinen positiivisten kokonaislukujen ominaisuus. Minkä tahansa positiivisen kokonaisluvun (ykköstä lukuun ottamatta) otatkin, sen voi hajottaa useiden (myös samojen) alkulukujen tuloksi. Esimerkkejä:

$$\begin{array}{rcl}8& =& 2\cdot 2\cdot 2\\ 15& =& 3\cdot 5\\ 26& =& 2\cdot 13\\ 1800& =& 2^3\cdot 3^2\cdot 5^2\end{array}$$

Väitettä alkutekijähajotelmasta kutsutaan aritmetiikan peruslauseeksi. Se kertoo muun muassa, että tällainen hajotelma on yksikäsitteinen, eli emme löydä kahta eri alkutekijähajotelmaa samalle positiiviselle kokonaisluvulle. Lisäksi vain alkuluvuilla on alkutekijähajotelma, joka koostuu vain yhdestä luvusta, eli niistä itsestään. Seitsemän alkutekijähajotelma olisi siis luku seitsemän. Näitä tosiasioita käytämme seuraavan väitteen todistuksen rakentamisessa.

Todistamme nyt väitteen ”alkulukuja on äärettömän monta”. Kiellämme väitteen jälleen: ”alkulukuja on äärellinen määrä”. Oletetaan, että lukujen jono

$$a_1,a_2,a_3,\dots ,a_n$$

sisältää kaikki olemassa olevat alkuluvut. Jos tässä jonossa ovat kaikki alkuluvut, niin varmasti emme enää pysty löytämään lukua, joka olisi alkuluku mutta ei olisi tässä jonossa. Kaikki alkuluvut ovat jonossa, eikä jonon ulkopuolella saa esiintyä yhtään alkulukua.

Jos haluamme päätyä ristiriitaan, meidän täytyy siis muodostaa jokin alkuluku, joka ei ole tässä jonossa. Siihen auttaa luku q. Muodostamme sen kertomalla jonon kaikki alkuluvut keskenään ja lisäämällä ykkösen:

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

Nyt meidän täytyy osoittaa, että tämä luku joko on alkuluku tai tuottaa jollain tavalla alkuluvun. Tiedämme, että q on positiivinen kokonaisluku ja että jokainen positiivinen kokonaisluku voidaan esittää alkulukujen tulona. Yksikään alkuluku a_i ei kuitenkaan jaa lukua q tasan, jakojäännökseksi jää aina yksi. Jos yrittäisimme jakaa luvun q esimerkiksi alkuluvulla a₂, kävisi näin:

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

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

Jaamme murtoluvun ensin kahteen osaan. Ensimmäisessä murtoluvussa supistamme a₂:n pois, ja jäljelle jää jokin alkulukujen tulo, joka on yksinkertaisesti jokin toinen epäolennainen kokonaisluku. Toisessa murtoluvussa ei ole mitään supistettavaa, ja tämä murtoluku on aina jokin ei-kokonaisluku (koska nimittäjä ei voi olla yksi, ykkönen ei ole alkuluku). Summana saamme siis luvun, joka ei ole kokonaisluku, eli alkuluku a₂ ei jaa lukua q.

Näin olemme todistaneet, ettei mikään jonon a_n alkuluvuista jaa lukua q. (Huomautus: osoitimme sen vain luvulle a₂, mutta sen voi helposti yleistää vaihtamalla a₂:n tilalle yleisen a_i:n.) Mutta koska jokainen positiivinen kokonaisluku voidaan hajottaa alkulukujen tuloksi, täytyy olla olemassa muita alkulukuja, jotka eivät ole jonossa a_n mutta ovat luvun q tekijöitä. Samalla itse luku q voi hyvin olla alkuluku, jolloin alkutekijähajotelma sisältää vain luvun q. Käydään siis vielä kerran läpi viimeinen päättelyketju:

1. Jokainen luonnollinen luku voidaan esittää alkulukujen tulona.
2. Oletuksen mukaan jono a_n sisältää kaikki olemassa olevat alkuluvut.
3. Muokkaamme ensimmäistä väitettä niin, että jokainen positiivinen kokonaisluku voidaan esittää jonon a_n valittujen jäsenten tulona, koska jono sisältää kaikki alkuluvut.
4. Olemme todistaneet, ettei mikään jonon a_n luku jaa lukua q.
5. Näin syntyi ristiriita oletuksen kanssa → jos meidän täytyy pystyä hajottamaan jokainen positiivinen kokonaisluku alkulukujen tuloksi ja jono a_n ei sisällä yhtään lukua, joka jakaa luvun q, niin täytyy olla olemassa muita alkulukuja, jotka jakavat luvun q ja ovat luvun q alkutekijähajotelma.

Näin päädyimme ristiriitaan. Luvun q alkutekijähajotelma sisältää alkulukuja, jotka eivät ole jonossa, jonka oletimme sisältävän kaikki alkuluvut. Kielletty väite ei siis päde, vaan alkuperäinen kieltämätön väite pätee. Alkulukuja on äärettömän monta.