Motsigelsesbevis

Motsigelsesbevis er en populær bevisteknikk. Hvis vi vil bevise at et utsagn gjelder, negerer vi det, antar at negasjonen er sann, og prøver å komme frem til en selvmotsigelse. Målet er å bevise at antakelsen vi har valgt, fører til noe meningsløst.

Et trivielt eksempel

La oss ta påstanden «det finnes ikke noe minste positive rasjonale tall». Denne påstanden beviser vi ved selvmotsigelse ved først å negere den: «det finnes et minste positivt rasjonalt tall», og dette tallet kaller vi q. Hvis q er det minste positive rasjonale tallet, kan vi ikke finne noe mindre positivt rasjonalt tall, for da ville ikke tallet q vært det minste.

Det bruker vi når vi leter etter selvmotsigelsen. Hvis vi likevel finner et tall som er mindre enn q, som vi kan velge fritt, har vi kommet frem til en selvmotsigelse, og det negerte utsagnet gjelder ikke. Hvis vi velger 0,1 som det minste tallet, ser vi at tallet 0,01 er mindre. Videre er 0,001 enda mindre, 0,0001 er igjen mindre, og så videre. Det er nok å dele tallet q på ti, så får vi et mindre tall. Egentlig er det nok å dele det på et hvilket som helst tall som er større enn én, for eksempel to. Halvparten av tallet q er helt sikkert mindre enn hele tallet q.

Tallet q/2 er altså helt sikkert mindre enn q, og samtidig er det et positivt rasjonalt tall. Dermed har vi kommet frem til en selvmotsigelse med den negerte påstanden, altså gjelder ikke den negerte påstanden, og dermed gjelder den opprinnelige, ikke-negerte påstanden.

Interessante tall

Et klassisk morsomt bevis som illustrerer prinsippet om selvmotsigelse, er følgende eksempel. Anta at det finnes naturlige tall som på en eller annen måte er interessante. For eksempel er tallet 2 interessant, fordi 2 · 2 = 2 + 2, og det er en ganske uvanlig egenskap. Tallet 42 er interessant fordi det er svaret på alt. Og så videre. Spørsmålet er: Finnes det uendelig mange interessante tall?

Anta det motsatte, altså at det bare finnes endelig mange interessante tall, og at noen tall er uinteressante. Disse uinteressante naturlige tallene samler vi i en mengde av uinteressante tall. Nå velger vi det minste uinteressante tallet. Vent litt, det minste uinteressante tallet? Det høres ganske interessant ut, ikke sant? :-)

Dermed har vi kommet frem til en selvmotsigelse, for det minste uinteressante tallet er i virkeligheten ganske interessant. Det kan altså ikke finnes noe minste uinteressant tall, og da må mengden av uinteressante tall nødvendigvis være tom.

Dette er selvfølgelig tull, for vi har ikke definert ordentlig hva et interessant tall er, men selve fremgangsmåten for beviset er i orden.

Bevis for at det finnes uendelig mange primtall

I dette eksemplet viser vi en lignende fremgangsmåte som i det forrige kapittelet, men denne gangen blir den riktig i alle henseender.

Et primtall er et tall som er delelig med bare to ulike tall, seg selv og én. Legg merke til at én ikke oppfyller definisjonen, mens to gjør det.

Primtallsfaktorisering er oppdelingen av et naturlig tall, unntatt én, i et produkt av primtall. Det er en ganske interessant egenskap ved de naturlige tallene. Uansett hvilket naturlig tall du tar (unntatt én), kan det skrives som et produkt av flere (også like) primtall. Eksempler:

$$\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}$$

Påstanden om primtallsfaktorisering kalles aritmetikkens fundamentalteorem. Blant annet sier den at en slik faktorisering er entydig, altså at vi ikke finner to ulike primtallsfaktoriseringer av ett naturlig tall. Videre er det bare primtall som har en primtallsfaktorisering som består av bare ett tall, nemlig seg selv. Primtallsfaktoriseringen av sju er altså tallet sju. Disse faktaene bruker vi når vi konstruerer beviset for den følgende påstanden.

Nå beviser vi påstanden «det finnes uendelig mange primtall». Vi negerer igjen påstanden: «det finnes et endelig antall primtall». Anta at følgen av tall

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

representerer alle primtall som finnes. Hvis alle primtallene står i denne følgen, gjelder det helt sikkert at vi ikke lenger kan finne et tall som er et primtall og samtidig ikke står i denne følgen. Vi har alle primtallene i følgen, og utenfor følgen kan det ikke forekomme noe primtall.

Hvis vi vil komme frem til en selvmotsigelse, må vi altså konstruere et primtall som ikke står i denne følgen. Til det hjelper tallet q oss. Det konstruerer vi ved å multiplisere alle primtallene i følgen og legge til én:

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

Nå må vi vise at dette tallet enten er et primtall eller på en eller annen måte gir opphav til et primtall. Vi vet at q er et naturlig tall og at hvert naturlig tall kan skrives som et produkt av primtall. Men ingen av primtallene a_i går opp i tallet q, det blir alltid én til rest ved divisjonen. Hvis vi prøvde å dele tallet q for eksempel på primtallet a₂, ville det gå slik:

$$\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}$$

Først deler vi brøken i to. I den første brøken forkorter vi a₂, og det blir igjen et produkt av primtall, som rett og slett er et annet, uvesentlig heltall. I den andre brøken er det ingenting å forkorte, og denne brøken er alltid et tall som ikke er et heltall (fordi nevneren ikke kan være én, siden én ikke er et primtall). I summen får vi dermed et tall som ikke er et heltall, altså går ikke primtallet a₂ opp i tallet q.

Dermed har vi bevist at ingen av primtallene i følgen a_n går opp i tallet q. (Merk: Vi viste det bare for a₂, men det kan lett generaliseres hvis vi bytter a₂ med et generelt a_i.) Men siden hvert naturlig tall kan faktoriseres i primtall, må det finnes andre primtall, som ikke står i følgen a_n, men som inngår i faktoriseringen av tallet q. Selve tallet q kan godt være et primtall, og da inneholder primtallsfaktoriseringen bare tallet q. Så her er tankegangen en gang til:

1. Hvert naturlig tall kan skrives som et produkt av primtall.
2. Etter antakelsen inneholder følgen a_n alle primtall som finnes.
3. Vi omformer den første påstanden slik at hvert naturlig tall kan skrives som et produkt av utvalgte ledd i følgen a_n, fordi den inneholder alle primtallene.
4. Vi har bevist at ingen tall i følgen a_n går opp i tallet q.
5. Dermed oppstod det en selvmotsigelse med antakelsen → hvis vi må kunne faktorisere hvert naturlig tall i primtall, og følgen a_n ikke inneholder noe tall som går opp i q, må det finnes andre primtall som går opp i q og inngår i primtallsfaktoriseringen av q.

Dermed har vi kommet frem til en selvmotsigelse. Primtallsfaktoriseringen av tallet q inneholder primtall som ikke står i følgen som vi antok inneholdt alle primtallene. Altså gjelder ikke den negerte påstanden, men den opprinnelige, ikke-negerte påstanden. Det finnes uendelig mange primtall.