9.3 Kontrapositiv og kontradiksjon

Å bevise baklengs

Nokre påstandar nektar å la seg bevise rett fram. Prøv å vise direkte at $\sqrt{2}$ ikkje kan skrivast som ein brøk – kvar byrjar du i det heile teke? Å vise at noko ikkje finst, at noko er umogleg, krev ein annan type åtak.

Heldigvis har logikken to elegante bakvegar. Den første kjenner du alt frå kapittel 9.1: implikasjonen $P \Rightarrow Q$ er logisk ekvivalent med sin kontrapositiv $\neg Q \Rightarrow \neg P$ – så når originalen er vrang, kan du bevise tvillingen i staden. Den andre er endå meir dristig: i eit kontradiksjonsbevis antar du at påstanden din er usann, og følgjer antakinga logisk til ho kollapsar i ei sjølvmotseiing. Då må antakinga ha vore feil – og påstanden er sann.

Med desse to metodane skal vi bevise to av dei mest berømte resultata i matematikkhistoria: at $\sqrt{2}$ er irrasjonell, og Euklids 2300 år gamle perle om at primtala aldri tek slutt.

Kontrapositivt bevis – tvillingen som er lettare å fange

Hugs frå 9.1: $P \Rightarrow Q$ og $\neg Q \Rightarrow \neg P$ er logisk ekvivalente – alltid begge sanne eller begge usanne. «Viss det regnar, er bakken våt» er nøyaktig same påstand som «viss bakken ikkje er våt, regnar det ikkje». Det tyder at du fritt kan velje kva av dei to du beviser.

Når løner det seg å byte? Når negasjonane er enklare å rekne med enn originalane. Klassisk eksempel: viss $n^2$ er partal, så er $n$ partal. Direkte åtak er klønete – «$n^2$ partal» er ein tung føresetnad å starte frå ($n = \sqrt{\text{partal}}$... og kva så?). Men kontrapositiven er: viss $n$ er odde, så er $n^2$ odde – og «$n$ er odde» er ein draumestart, for då er $n = 2k + 1$, og vi kan rekne!

$$n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$$

Sidan $2k^2 + 2k$ er eit heiltal, er $n^2$ odde. $\square$ Dermed er òg originalen bevist: vi har vist $\neg Q \Rightarrow \neg P$, som er ekvivalent med $P \Rightarrow Q$.

Mønsteret å sjå etter: føresetnaden i originalen seier lite å rekne med (her eit utsegn om $n^2$, eller «irrasjonell», «ikkje-deleleg»), medan negasjonen av konklusjonen gjev ei konkret form (her $n = 2k + 1$). Då gjev kontrapositiven deg ein handfast definisjon å starte frå i staden for eit tomrom. Merk dette vesle beviset, forresten – det blir ein byggjekloss i det store beviset i neste seksjon.

Kontradiksjon – og det berømte beviset for at $\sqrt{2}$ er irrasjonell

Kontradiksjonsbeviset (reductio ad absurdum) har tre akter. Anta at påstanden $P$ er usann. Utlei konsekvensar logisk, til du når ei sjølvmotseiing – noko openbert falskt, eller noko som motseier antakinga sjølv. Konkluder: antakinga $\neg P$ må vere feil, altså er $P$ sann. Metoden kviler på lova om det utelukka tredje: ein påstand er anten sann eller usann, noko tredje finst ikkje.

No, juvelen. Påstand: $\sqrt{2}$ er irrasjonell.

Anta det motsette: $\sqrt{2}$ er rasjonell, altså $\displaystyle \sqrt{2} = \frac{a}{b}$ for heiltal $a, b$ – og vi krev at brøken er maksimalt forkorta: $a$ og $b$ har ingen felles faktorar. Kvadrer begge sider:

$$2 = \frac{a^2}{b^2} \quad \Rightarrow \quad a^2 = 2b^2$$

Altså er $a^2$ partal. Og her gjenbrukar vi resultatet frå førre seksjon: er $a^2$ partal, må $a$ vere partal. Skriv $a = 2k$ og set inn: $4k^2 = 2b^2$, så $b^2 = 2k^2$. Men då er $b^2$ partal – og dermed er òg $b$ partal!

No har vi motseiinga: både $a$ og $b$ er partal, altså har dei felles faktor 2 – men brøken skulle vere maksimalt forkorta. Antakinga har øydelagt seg sjølv. Altså er $\sqrt{2}$ irrasjonell. $\square$

Dette beviset, kjent sidan antikkens Hellas, sjokkerte pytagorearane: det finst lengder – som diagonalen i eit einingskvadrat – som ingen brøk kan skildre. Legg òg merke til arkitekturen: eit lite kontrapositivt lemma bar det store kontradiksjonsbeviset. Slik vert matematikk bygd – resultat på resultat.

Euklids teorem – og kunsten å velje metode

Eit kontradiksjonsbevis til, kanskje det vakraste som finst. Euklids teorem (ca. 300 f.Kr.): det finst uendeleg mange primtal.

Anta det motsette: primtala er endeleg mange, og heile lista er $p_1, p_2, \ldots, p_n$. Konstruer no talet

$$N = p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1$$

– produktet av alle primtala, pluss éin. Sidan $N > 1$, har $N$ minst éin primfaktor $p$. Men kva for ein? Deler du $N$ på $p_1$, blir resten 1. På $p_2$? Rest 1. På kvart einaste primtal i lista gjev $N$ rest 1 – ingen av dei deler $N$. Så primfaktoren $p$ er eit primtal som ikkje står på lista. Men lista skulle innehalde alle primtal! Kontradiksjon – og dermed finst det uendeleg mange primtal. $\square$

To tusen tre hundre år gammalt, fire linjer langt, og framleis eit førebilete for kva eit bevis kan vere.

Du har no fire bevismetodar, og valet mellom dei følgjer ganske faste signal. Direkte bevis når vegen frå antaking til konklusjon er farbar – definisjonar inn, algebra, konklusjon ut. Kontrapositiv når negasjonane er meir konkrete å rekne med enn originalane. Kontradiksjon når påstanden handlar om umoglegheit eller ikkje-eksistens – «kan ikkje skrivast som», «finst ikkje», «er uendeleg mange» – for då gjev antakinga om det motsette deg noko handfast å rive ned. Induksjon når påstanden gjeld alle naturlege tal. Det fine er at metodane samarbeider, slik kontrapositiv-lemmaet bar $\sqrt{2}$-beviset: verktøykassa er éin heilskap.

Oppsummering: bakvegane til sanninga

Når den direkte vegen er stengd, går logikken bakvegar. Det kontrapositive beviset utnyttar at $P \Rightarrow Q$ og $\neg Q \Rightarrow \neg P$ er same påstand i to drakter: bevis den varianten der føresetnaden er konkret og reknbar – slik «$n$ odde $\Rightarrow n^2$ odde» med $n = 2k + 1$ var ein leik, medan originalen «$n^2$ partal $\Rightarrow n$ partal» var vrang.

Kontradiksjonsbeviset antar at påstanden er usann og utleier ei sjølvmotseiing: då må antakinga forkastast. Slik fall $\sqrt{2}$-beviset – antakinga om ein maksimalt forkorta brøk enda med at både teljar og nemnar var partal – og slik viste Euklid at primtala er uendeleg mange, ved å konstruere talet $N = p_1 \cdots p_n + 1$ som ingen av dei lista primtala deler.

Verktøykassa er no komplett: direkte bevis når vegen er open, kontrapositiv når negasjonane er enklast, kontradiksjon ved umoglegheit og ikkje-eksistens, induksjon for alle naturlege tal – og moteksempelet når påstanden skal fellast, ikkje bevisast. Desse metodane er meir enn pensum; dei er sjølve tenkjemåten som har bore matematikken frå Euklid til i dag.