Bewijs uit het ongerijmde

Het bewijs uit het ongerijmde is een geliefde bewijstechniek. Als we willen bewijzen dat een uitspraak geldt, ontkennen we haar, nemen we aan dat de negatie waar is en proberen we tot een tegenspraak te komen. Het doel is te bewijzen dat de door ons gekozen aanname tot onzin leidt.

Een triviaal voorbeeld

Neem de bewering “er bestaat geen kleinste positief rationaal getal”. Deze bewering bewijzen we uit het ongerijmde door de bewering eerst te ontkennen: “er bestaat een kleinste positief rationaal getal” en dit getal noemen we q. Als q het kleinste positieve rationale getal is, dan kunnen we geen kleiner positief rationaal getal vinden, want dan zou het getal q niet het kleinste zijn.

Dat gebruiken we bij het zoeken naar de tegenspraak. Als we toch een getal vinden dat kleiner is dan q, dat we willekeurig kunnen kiezen, dan zijn we tot een tegenspraak gekomen en geldt de ontkende uitspraak niet. Als we bijvoorbeeld 0,1 als kleinste getal kiezen, zien we dat het getal 0,01 kleiner is. Verder is 0,001 nog kleiner, 0,0001 weer kleiner enzovoort. Het is genoeg het getal q door tien te delen en we krijgen een kleiner getal. In feite is het genoeg het te delen door elk getal dat groter is dan één, bijvoorbeeld twee: de helft van het getal q is zeker kleiner dan het hele getal q.

Het getal q/2 is dus zeker kleiner dan q en tegelijk een positief rationaal getal. Zo zijn we tot een tegenspraak gekomen met de ontkende bewering, dus de ontkende bewering geldt niet en daarmee geldt de oorspronkelijke, niet-ontkende bewering.

Interessante getallen

Een klassiek grappig bewijs dat het principe van de tegenspraak illustreert, is het volgende voorbeeld. Stel dat er natuurlijke getallen zijn die op de een of andere manier interessant zijn. Het getal 2 is bijvoorbeeld interessant, want er geldt 2 · 2 = 2 + 2, en dat is een vrij ongewone eigenschap. Het getal 42 is interessant, want het is het antwoord op alles. En zo verder. De vraag is: bestaan er oneindig veel interessante getallen?

Stel dat het omgekeerde waar is, dus dat er maar eindig veel interessante getallen zijn en dat sommige getallen oninteressant zijn. Deze oninteressante natuurlijke getallen ordenen we in een verzameling van oninteressante getallen. Nu kiezen we het kleinste oninteressante getal. Wacht even, het kleinste oninteressante getal? Dat klinkt toch best interessant, of niet? :-)

Zo zijn we tot een tegenspraak gekomen, want het kleinste oninteressante getal is in werkelijkheid best interessant, dus er kan geen kleinste oninteressante getal bestaan, en daarmee moet de verzameling van oninteressante getallen noodzakelijk leeg zijn.

Dit is natuurlijk onzin, want we hebben niet goed gedefinieerd wat een interessant getal is, maar de werkwijze van het bewijs zelf is in orde.

Bewijs dat er oneindig veel priemgetallen zijn

In dit voorbeeld laten we een soortgelijke werkwijze zien als in het vorige hoofdstuk, maar nu is het in alle opzichten correct.

Een priemgetal is een getal dat alleen deelbaar is door twee verschillende getallen: door zichzelf en door één. Merk op dat één niet aan de definitie voldoet en twee wel.

Ontbinden in priemfactoren, oftewel factoriseren, is het ontbinden van een natuurlijk getal, behalve één, in een product van priemgetallen. Het is een vrij interessante eigenschap van natuurlijke getallen. Welk natuurlijk getal je ook neemt (behalve die één), er geldt dat je het kunt ontbinden in een product van een aantal (ook gelijke) priemgetallen. Voorbeelden:

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

De bewering over de priemfactorontbinding heet de hoofdstelling van de rekenkunde. Ze zegt ons onder andere dat zo'n ontbinding uniek is, dus dat we geen twee verschillende priemfactorontbindingen van één natuurlijk getal vinden. Verder hebben alleen priemgetallen een priemfactorontbinding die uit slechts één getal bestaat, namelijk zijzelf. De priemfactorontbinding van zeven is dus het getal zeven. Deze feiten gebruiken we bij de constructie van het bewijs van de volgende bewering.

Nu bewijzen we de bewering dat “er oneindig veel priemgetallen zijn”. We ontkennen de bewering weer: “er is een eindig aantal priemgetallen”. Stel dat de rij getallen

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

alle bestaande priemgetallen voorstelt. Als in deze rij alle priemgetallen staan, dan geldt zeker dat we geen getal meer kunnen vinden dat een priemgetal is en niet in deze rij staat. Alle priemgetallen staan in de rij, buiten de rij mag geen enkel priemgetal meer voorkomen.

Als we tot een tegenspraak willen komen, moeten we dus een priemgetal construeren dat niet in deze rij staat. Daarbij helpt ons het getal q. Dat construeren we door alle priemgetallen in de rij te vermenigvuldigen en er één bij op te tellen:

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

Nu moeten we laten zien dat dit getal ofwel een priemgetal is, ofwel op de een of andere manier een priemgetal oplevert. We weten dat q een natuurlijk getal is en dat elk natuurlijk getal kan worden geschreven als een product van priemgetallen. Maar geen enkel priemgetal a_i deelt het getal q zonder rest, na het delen blijft altijd één over. Als we zouden proberen het getal q bijvoorbeeld door het priemgetal a₂ te delen, zou het zo uitpakken:

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

We splitsen de breuk eerst in tweeën. In de eerste breuk vereenvoudigen we a₂ weg en blijft er een product van priemgetallen over, dat gewoon een of ander onbelangrijk geheel getal is. In de tweede breuk valt niets weg te strepen, deze breuk is altijd een niet-geheel getal (omdat de noemer niet één kan zijn, want één is geen priemgetal). In de som krijgen we dus een getal dat niet geheel is, dus het priemgetal a₂ deelt het getal q niet.

Hiermee hebben we bewezen dat geen enkel priemgetal uit de rij a_n het getal q deelt. (Opmerking: we hebben het weliswaar alleen voor a₂ laten zien, maar dat kan eenvoudig worden veralgemeend als we a₂ vervangen door een willekeurig a_i.) Maar omdat elk natuurlijk getal kan worden ontbonden in een product van priemgetallen, moeten er andere priemgetallen bestaan die niet in de rij a_n staan maar wel de ontbinding van het getal q vormen. Het getal q zelf kan daarbij gerust een priemgetal zijn en de priemfactorontbinding bestaat dan alleen uit het getal q. Nog één keer de laatste gedachtegang:

1. Elk natuurlijk getal kan worden geschreven als een product van priemgetallen.
2. Volgens de aanname bevat de rij a_n alle bestaande priemgetallen.
3. We herformuleren de eerste bewering zo dat elk natuurlijk getal kan worden geschreven als een product van gekozen termen van de rij a_n, omdat die alle priemgetallen bevat.
4. We hebben bewezen dat geen enkel getal uit de rij a_n het getal q deelt.
5. Zo ontstond een tegenspraak met de aanname → als we elk natuurlijk getal in een product van priemgetallen moeten kunnen ontbinden en de rij a_n geen enkel getal bevat dat q deelt, dan moeten er andere priemgetallen bestaan die q delen en de priemfactorontbinding van het getal q vormen.

Hiermee zijn we tot een tegenspraak gekomen. De priemfactorontbinding van het getal q bevat priemgetallen die niet in de rij staan waarvan we aannamen dat die alle priemgetallen bevat. De ontkende bewering geldt dus niet, de oorspronkelijke, niet-ontkende bewering geldt. Er zijn oneindig veel priemgetallen.