Modstridsbevis

Modstridsbevis er en populær bevisteknik. Hvis vi vil bevise, at et udsagn gælder, negerer vi det, antager, at dets negation er sand, og prøver at nå frem til en modstrid. Målet er at bevise, at den forudsætning, vi har valgt, fører til noget meningsløst.

Et trivielt eksempel

Lad os tage påstanden »der findes ikke noget mindste positivt rationalt tal«. Denne påstand beviser vi ved modstrid på den måde, at vi først negerer påstanden: »der findes et mindste positivt rationalt tal«, og dette tal kalder vi q. Hvis q er det mindste positive rationale tal, kan vi ikke finde et mindre positivt rationalt tal — for så ville tallet q ikke være det mindste.

Det udnytter vi, når vi leder efter en modstrid. Hvis vi alligevel finder et tal, der er mindre end q, som vi må vælge frit, så er vi nået frem til en modstrid, og det negerede udsagn gælder ikke. Hvis vi for eksempel vælger 0,1 som det mindste tal, ser vi, at tallet 0,01 er mindre. Og 0,001 er endnu mindre, 0,0001 er igen mindre og så videre. Det er nok at dividere det givne tal q med ti, så får vi et mindre tal. Faktisk er det nok at dividere det med et hvilket som helst tal, der er større end en, for eksempel to — halvdelen af tallet q er helt sikkert mindre end hele tallet q.

Tallet q/2 er altså helt sikkert mindre end q, og samtidig er det et positivt rationalt tal. Dermed er vi nået frem til en modstrid med den negerede påstand, altså gælder den negerede påstand ikke, og derfor gælder den oprindelige, ikke-negerede påstand.

Interessante tal

Et klassisk morsomt bevis, der illustrerer princippet om modstrid, er det følgende eksempel. Lad os antage, at der findes naturlige tal, som på en eller anden måde er interessante. For eksempel er tallet 2 interessant, fordi der gælder, at 2 · 2 = 2 + 2, og det er en ret utypisk egenskab. Tallet 42 er interessant, fordi det er svaret på alt. Og tilsvarende. Spørgsmålet lyder — findes der uendeligt mange interessante tal?

Lad os antage det modsatte, altså at der kun findes endeligt mange interessante tal, og nogle tal er uinteressante. Disse uinteressante naturlige tal samler vi i en mængde af uinteressante tal. Nu vælger vi det mindste uinteressante tal. Et øjeblik, det mindste uinteressante tal? Det lyder ret interessant, ikke? :-)

Dermed er vi nået frem til en modstrid, for det mindste uinteressante tal er i virkeligheden ret interessant, altså kan der ikke findes et mindste uinteressant tal, og derfor må mængden af uinteressante tal nødvendigvis være tom.

Det er selvfølgelig noget sludder, vi har ikke ordentligt defineret, hvad et interessant tal er, men selve fremgangsmåden i beviset er i orden.

Bevis for, at der er uendeligt mange primtal

I dette eksempel viser vi en lignende fremgangsmåde som i det foregående afsnit, men denne gang er det korrekt på alle måder.

Et primtal er et tal, der kun er deleligt med to forskellige tal — sig selv og en. Læg mærke til, at definitionen ikke opfyldes af tallet et, og at den opfyldes af tallet to.

Primfaktoropløsning, eller faktorisering, er opløsningen af et naturligt tal, undtagen tallet et, i et produkt af primtal. Det er en ret interessant egenskab ved de naturlige tal. Uanset hvilket naturligt tal du tager (undtagen tallet et), gælder det, at det kan opløses i et produkt af nogle (også ens) primtal. 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 primfaktoropløsning kaldes aritmetikkens fundamentalsætning. Den fortæller os blandt andet, at en sådan opløsning er entydig, altså vi finder ikke to forskellige primfaktoropløsninger af ét naturligt tal. Desuden er det kun primtal, der har en primfaktoropløsning bestående af kun ét tal — dem selv. Altså primfaktoropløsningen af syv ville være tallet syv. Disse fakta udnytter vi, når vi konstruerer beviset for den følgende påstand.

Nu beviser vi påstanden »der er uendeligt mange primtal«. Påstanden negerer vi igen: »der er et endeligt antal primtal«. Lad os antage, at talfølgen

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

udgør alle de eksisterende primtal. Hvis alle primtal er i denne talfølge, så gælder det helt sikkert, at vi ikke længere kan finde et tal, der både er et primtal og ikke er i denne talfølge. Vi har alle primtal i talfølgen, uden for talfølgen må der ikke længere optræde noget primtal.

Hvis vi vil nå frem til en modstrid, skal vi altså konstruere et primtal, som ikke er i denne talfølge. Det hjælper tallet q os med. Det konstruerer vi ved at gange alle primtallene i talfølgen og lægge en til:

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

Nu skal vi vise, at dette tal enten er et primtal eller på en eller anden måde frembringer et primtal. Vi ved, at q er et naturligt tal, og at ethvert naturligt tal kan udtrykkes som et produkt af primtal. Men intet primtal a_i går op i tallet q, der bliver altid en til rest efter divisionen. Hvis vi for eksempel prøvede at dividere tallet q med primtallet a₂, ville det gå sådan:

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

Brøken deler vi først i to. I den første brøk forkorter vi a₂, og tilbage er et produkt af primtal, som simpelthen er et eller andet andet ligegyldigt helt tal. I den anden brøk er der ikke noget at forkorte, denne brøk bliver altid et tal, der ikke er et helt tal (fordi nævneren ikke kan være en, tallet et er ikke et primtal). I summen får vi derfor et tal, der ikke er et helt tal, altså går primtallet a₂ ikke op i tallet q.

Dermed har vi bevist, at ingen af primtallene fra talfølgen a_n går op i tallet q. (Bemærkning: vi har det rigtignok kun vist for a₂, men det kan enkelt generaliseres, hvis vi erstatter a₂ med et generelt a_i.) Men fordi ethvert naturligt tal kan opløses i et produkt af primtal, må der findes andre primtal, som ikke er i talfølgen a_n, men er faktoriseringen af tallet q. Selve tallet q kan samtidig godt være et primtal, og primfaktoropløsningen vil så kun omfatte tallet q. Så endnu en gang den sidste tankerække:

1. Ethvert naturligt tal kan udtrykkes som et produkt af primtal.
2. Ifølge forudsætningen indeholder talfølgen a_n alle eksisterende primtal.
3. Vi omformulerer den første påstand, så ethvert naturligt tal kan udtrykkes som et produkt af udvalgte led i talfølgen a_n, fordi den indeholder alle primtal.
4. Vi har bevist, at intet tal fra talfølgen a_n går op i tallet q.
5. Dermed opstod der en modstrid med forudsætningen → hvis vi skal kunne opløse ethvert naturligt tal i et produkt af primtal, og talfølgen a_n ikke indeholder noget tal, der går op i q, så må der findes andre primtal, der går op i q og er primfaktoropløsningen af tallet q.

Dermed er vi nået frem til en modstrid. Primfaktoropløsningen af tallet q omfatter primtal, som ikke er indeholdt i talfølgen, som vi antog indeholdt alle primtal. Altså gælder den negerede påstand ikke, den oprindelige ikke-negerede påstand gælder. Der er uendeligt mange primtal.