9.3 Kontrapositiv og kontradiksjon

Å bevise baklengs

Noen påstander nekter å la seg bevise rett fram. Prøv å vise direkte at $\sqrt{2}$ ikke kan skrives som en brøk – hvor begynner du i det hele tatt? Å vise at noe ikke finnes, at noe er umulig, krever en annen type angrep.

Heldigvis har logikken to elegante bakveier. Den første kjenner du allerede fra 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 stedet. Den andre er enda dristigere: i et kontradiksjonsbevis antar du at påstanden din er usann, og følger antagelsen logisk til den kollapser i en selvmotsigelse. Da må antagelsen ha vært feil – og påstanden er sann.

Med disse to metodene skal vi bevise to av matematikkhistoriens mest berømte resultater: at $\sqrt{2}$ er irrasjonell, og Euklids 2300 år gamle perle om at primtallene aldri tar slutt.

Kontrapositivt bevis – tvillingen som er lettere å fange

Husk fra 9.1: $P \Rightarrow Q$ og $\neg Q \Rightarrow \neg P$ er logisk ekvivalente – alltid begge sanne eller begge usanne. «Hvis det regner, er bakken våt» er nøyaktig samme påstand som «hvis bakken ikke er våt, regner det ikke». Det betyr at du fritt kan velge hvilken av de to du beviser.

Når lønner byttet seg? Når negasjonene er enklere å regne med enn originalene. Klassisk eksempel: hvis $n^2$ er odde, så er $n$ odde. Direkte angrep er klønete – «$n^2$ odde» er en tung forutsetning å starte fra ($n = \sqrt{\text{oddetall}}$... og hva så?). Men kontrapositiven er: hvis $n$ er partall, så er $n^2$ partall – og «$n$ er partall» er en drømmestart, for da er $n = 2k$, og vi kan regne!

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

Siden $2k^2$ er et heltall, er $n^2$ partall. $\square$ Dermed er også originalen bevist: vi har vist $\neg Q \Rightarrow \neg P$, som er ekvivalent med $P \Rightarrow Q$.

Mønsteret å se etter: forutsetningen i originalen er «negativ» eller strukturløs (odde, irrasjonell, ikke-delelig), mens dens negasjon er «positiv» og konkret (partall, brøk, delelig). Da gir kontrapositiven deg en håndfast definisjon å starte fra i stedet for et tomrom. Merk dette lille beviset, forresten – det blir en byggekloss i neste seksjons store bevis.

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. Utled konsekvenser logisk, til du når en selvmotsigelse – noe åpenbart falskt, eller noe som motsier antagelsen selv. Konkluder: antagelsen $\neg P$ må være feil, altså er $P$ sann. Metoden hviler på loven om det utelukkede tredje: en påstand er enten sann eller usann, noe tredje finnes ikke.

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

Anta det motsatte: $\sqrt{2}$ er rasjonell, altså $\displaystyle \sqrt{2} = \frac{a}{b}$ for heltall $a, b$ – og vi krever at brøken er maksimalt forkortet: $a$ og $b$ har ingen felles faktorer. Kvadrer begge sider:

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

Altså er $a^2$ partall. Og her gjenbruker vi resultatet fra forrige seksjon (i kontrapositiv form): er $a^2$ partall, må $a$ være partall. Skriv $a = 2k$ og sett inn: $4k^2 = 2b^2$, så $b^2 = 2k^2$. Men da er $b^2$ partall – og dermed er også $b$ partall!

Nå har vi motsigelsen: både $a$ og $b$ er partall, altså har de felles faktor 2 – men brøken skulle være maksimalt forkortet. Antagelsen har ødelagt seg selv. Altså er $\sqrt{2}$ irrasjonell. $\square$

Dette beviset, kjent siden antikkens Hellas, sjokkerte pytagoreerne: det finnes lengder – som diagonalen i et enhetskvadrat – som ingen brøk kan beskrive. Legg også merke til arkitekturen: et lite kontrapositivt lemma bar det store kontradiksjonsbeviset. Slik bygges matematikk – resultat på resultat.

Euklids teorem – og kunsten å velge metode

Et kontradiksjonsbevis til, kanskje det vakreste som finnes. Euklids teorem (ca. 300 f.Kr.): det finnes uendelig mange primtall.

Anta det motsatte: primtallene er endelig mange, og hele listen er $p_1, p_2, \ldots, p_n$. Konstruer nå tallet

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

– produktet av alle primtallene, pluss én. Siden $N > 1$, har $N$ minst én primfaktor $p$. Men hvilken? Deler du $N$ på $p_1$, blir resten 1. På $p_2$? Rest 1. På hvert eneste primtall i listen gir $N$ rest 1 – ingen av dem deler $N$. Så primfaktoren $p$ er et primtall som ikke står på listen. Men listen skulle inneholde alle primtall! Kontradiksjon – og dermed finnes det uendelig mange primtall. $\square$

To tusen tre hundre år gammelt, fire linjer langt, og fortsatt et forbilde for hva et bevis kan være.

Du har nå fire bevismetoder, og valget mellom dem følger ganske faste signaler. Direkte bevis når veien fra antagelse til konklusjon er farbar – definisjoner inn, algebra, konklusjon ut. Kontrapositiv når negasjonene er mer konkrete å regne med enn originalene. Kontradiksjon når påstanden handler om umulighet eller ikke-eksistens – «kan ikke skrives som», «finnes ikke», «er uendelig mange» – for da gir antagelsen om det motsatte deg noe håndfast å rive ned. Induksjon når påstanden gjelder alle naturlige tall. Det fine er at metodene samarbeider, slik kontrapositiv-lemmaet bar $\sqrt{2}$-beviset: verktøykassen er én helhet.

Oppsummering: bakveiene til sannheten

Når den direkte veien er stengt, går logikken bakveier. Det kontrapositive beviset utnytter at $P \Rightarrow Q$ og $\neg Q \Rightarrow \neg P$ er samme påstand i to drakter: bevis den varianten der forutsetningen er konkret og regnbar – slik «$n$ partall $\Rightarrow n^2$ partall» med $n = 2k$ var en lek, mens originalen «$n^2$ odde $\Rightarrow n$ odde» var vrang.

Kontradiksjonsbeviset antar at påstanden er usann og utleder en selvmotsigelse: da må antagelsen forkastes. Slik falt $\sqrt{2}$-beviset – antagelsen om en maksimalt forkortet brøk endte med at både teller og nevner var partall – og slik viste Euklid at primtallene er uendelig mange, ved å konstruere tallet $N = p_1 \cdots p_n + 1$ som ingen av de listede primtallene deler.

Verktøykassen er nå komplett: direkte bevis når veien er åpen, kontrapositiv når negasjonene er enklest, kontradiksjon ved umulighet og ikke-eksistens, induksjon for alle naturlige tall – og moteksempelet når påstanden skal felles, ikke bevises. Disse metodene er mer enn pensum; de er selve tenkemåten som har båret matematikken fra Euklid til i dag.