Motsägelsebevis

Motsägelsebevis är en omtyckt bevisteknik. Om vi vill bevisa att ett påstående gäller, negerar vi det, antar att dess negation är sann och försöker komma fram till någon motsägelse. Målet är att visa att vårt antagande leder till något orimligt.

Ett trivialt exempel

Vi tar påståendet ”det finns inget minsta positivt rationellt tal”. Det bevisar vi med motsägelse genom att först negera påståendet: ”det finns ett minsta positivt rationellt tal”, och det talet kallar vi q. Om q är det minsta positiva rationella talet, kan vi inte hitta något mindre positivt rationellt tal — för då skulle q inte vara det minsta.

Det utnyttjar vi när vi söker motsägelsen. Om vi trots allt hittar ett tal som är mindre än q, som vi får välja fritt, har vi kommit fram till en motsägelse och det negerade påståendet gäller inte. Om vi till exempel väljer 0,1 som det minsta talet, ser vi att 0,01 är mindre. Sedan är 0,001 ännu mindre, 0,0001 är återigen mindre och så vidare. Det räcker att dividera talet q med tio så får vi ett mindre tal. Egentligen räcker det att dividera det med vilket tal som helst som är större än ett, till exempel två — hälften av talet q är säkert mindre än hela talet q.

Talet q/2 är alltså säkert mindre än q och är samtidigt ett positivt rationellt tal. Därmed har vi kommit fram till en motsägelse med det negerade påståendet, alltså gäller inte det negerade påståendet, och därför gäller det ursprungliga, onegerade påståendet.

Intressanta tal

Ett klassiskt skämtsamt bevis som illustrerar principen bakom motsägelsebevis är följande exempel. Anta att det finns positiva heltal som på något sätt är intressanta. Talet 2 är till exempel intressant, eftersom 2 · 2 = 2 + 2, vilket är en ganska ovanlig egenskap. Talet 42 är intressant eftersom det är svaret på allt. Och så vidare. Frågan är — finns det oändligt många intressanta tal?

Anta motsatsen, alltså att det bara finns ändligt många intressanta tal och att några tal är ointressanta. De ointressanta positiva heltalen samlar vi i en mängd av ointressanta tal. Nu väljer vi ut det minsta ointressanta talet. Vänta, det minsta ointressanta talet? Det låter ju ganska intressant, eller hur? :-)

Därmed har vi kommit fram till en motsägelse, eftersom det minsta ointressanta talet i själva verket är ganska intressant, alltså kan det inte finnas något minsta ointressant tal, och därmed måste mängden av ointressanta tal vara tom.

Det är förstås struntprat, vi har inte ordentligt definierat vad ett intressant tal är, men själva sättet att bevisa är i sin ordning.

Bevis för att det finns oändligt många primtal

I det här exemplet visar vi ett liknande tillvägagångssätt som i föregående avsnitt, men nu blir det riktigt i alla avseenden.

Ett primtal är ett tal som är delbart med bara två olika tal — sig självt och ettan. Lägg märke till att ettan inte uppfyller definitionen medan tvåan gör det.

Primtalsfaktorisering är en uppdelning av ett positivt heltal, utom ettan, i en produkt av primtal. Det är en ganska intressant egenskap hos de positiva heltalen. Vilket positivt heltal du än tar (utom ettan) gäller att det kan delas upp i en produkt av flera (eventuellt lika) primtal. Exempel:

$$\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åståendet om primtalsfaktorisering kallas aritmetikens fundamentalsats. Bland annat säger den att en sådan uppdelning är entydig, alltså att vi inte hittar två olika primtalsfaktoriseringar av samma positiva heltal. Vidare är det bara primtalen som har en primtalsfaktorisering som består av bara ett tal — de själva. Primtalsfaktoriseringen av sjuan skulle alltså vara talet sju. De här fakta utnyttjar vi när vi konstruerar beviset för följande påstående.

Nu bevisar vi påståendet ”det finns oändligt många primtal”. Vi negerar påståendet igen: ”det finns ändligt många primtal”. Anta att talföljden

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

består av alla existerande primtal. Om alla primtal finns i den här talföljden gäller säkert att vi inte kan hitta något tal som är ett primtal och samtidigt inte finns i talföljden. Alla primtal har vi i talföljden, och utanför talföljden får inget primtal förekomma.

Om vi vill komma fram till en motsägelse måste vi alltså konstruera något primtal som inte finns i den här talföljden. Till hjälp har vi talet q. Det konstruerar vi genom att multiplicera alla primtal i talföljden och lägga till ett:

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

Nu måste vi visa att det här talet antingen är ett primtal eller på något sätt ger upphov till ett primtal. Vi vet att q är ett positivt heltal och att varje positivt heltal kan uttryckas som en produkt av primtal. Däremot delar inget primtal a_i talet q utan rest, det blir alltid ett över vid divisionen. Om vi försökte dividera talet q till exempel med primtalet a₂, skulle det gå så här:

$$\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 delar vi upp bråket i två. I det första bråket förkortar vi bort a₂ och kvar blir någon produkt av primtal, vilket helt enkelt är något annat oviktigt heltal. I det andra bråket finns inget att förkorta, det bråket blir alltid ett tal som inte är ett heltal (eftersom nämnaren inte kan vara ett, ettan är inte ett primtal). Summan blir alltså ett tal som inte är ett heltal, så primtalet a₂ delar inte talet q.

Därmed har vi bevisat att inget av primtalen i talföljden a_n delar talet q. (Anmärkning: vi visade det bara för a₂, men det går enkelt att generalisera om vi byter ut a₂ mot ett allmänt a_i.) Men eftersom varje positivt heltal kan delas upp i en produkt av primtal, måste det finnas andra primtal, som inte finns i talföljden a_n, men som ingår i faktoriseringen av talet q. Själva talet q kan för övrigt gott vara ett primtal, och då består primtalsfaktoriseringen bara av talet q. Här är alltså tankegången en sista gång:

1. Varje positivt heltal kan uttryckas som någon produkt av primtal.
2. Enligt antagandet innehåller talföljden a_n alla existerande primtal.
3. Vi skriver om det första påståendet så att varje positivt heltal kan uttryckas som en produkt av utvalda termer i talföljden a_n, eftersom den innehåller alla primtal.
4. Vi har bevisat att inget tal i talföljden a_n delar talet q.
5. Därmed uppstod en motsägelse med antagandet → om vi måste kunna dela upp varje positivt heltal i en produkt av primtal och talföljden a_n inte innehåller något tal som delar q, då måste det finnas andra primtal som delar q och som utgör primtalsfaktoriseringen av q.

Därmed har vi kommit fram till en motsägelse. Primtalsfaktoriseringen av talet q innehåller primtal som inte ingår i talföljden som vi antog innehöll alla primtal. Alltså gäller inte det negerade påståendet, utan det ursprungliga, onegerade påståendet gäller. Det finns oändligt många primtal.