Wat is een bewijs

Bewijzen zijn de hoeksteen van de hele wiskunde. Dankzij bewijzen kun je uit een paar steentjes een hele piramide bouwen, en dan ook nog op zijn kop.

Waarom bewijzen

Bewijzen hebben in de wiskunde om meerdere redenen zin. De belangrijkste reden is dat we zonder bewijzen geen enkel idee of hypothese die ons te binnen schiet kunnen bevestigen. We zouden bijvoorbeeld kunnen geloven dat er een eindig aantal priemgetallen is, maar als we geen bewijs hebben, blijft het een loze bewering. Aan de andere kant hebben ook onbewezen uitspraken in de wiskunde (en elders) zin. Je zegt gewoon: als de aanname klopt dat er eindig veel priemgetallen zijn, dan geldt… een of andere theorie.

Dan moeten we ons niet verbazen als iemand na een tijdje bewijst dat er oneindig veel priemgetallen zijn, zoals we hierna zullen laten zien, en onze hele theorie instort als een kaartenhuis. Dankzij bewijzen kunnen we dus kaartenhuizen bouwen die nooit instorten.

De reden dat bewijzen op school worden geleerd, is dat wie een bewijs begrijpt, ook de stof begrijpt. Meestal kun je een stof moeilijk grondig begrijpen zonder de bewijzen te begrijpen. Het woord “begrijpen” heb ik helemaal met opzet benadrukt: als je de bewijzen de dag voor de toets uit je hoofd leert en de volgende dag alleen maar op papier uitspuugt, betekent dat niet dat je dichter bij het begrip van de stof bent.

Bewijzen beantwoorden bij het leren van een stof dus de vraag “waarom werkt het zo?” Als je begrijpt waarom iets werkt, onthoud je het gemakkelijker en na verloop van tijd begrijp je de stof zeker beter dan iemand die alleen heeft gestampt. De vraag is of dat jouw doel is.

Wat is een bewijs

Wat een bewijs is, wordt formeel in de wiskundige logica gedefinieerd, bijvoorbeeld met syntactische gevolgtrekking, maar wij kunnen volstaan met een veel eenvoudiger definitie.

Aan het begin van elk bewijs moeten we een bewering hebben die we willen bewijzen. Die bewering geven we aan met het magische symbool ϕ. Dat is een Griekse letter, die we “phi” lezen. Verder hebben we een verzameling axioma's en aannamen nodig, die we Ax noemen, waarmee we de bewering ϕ bewijzen. De verzameling axioma's is iets wat we al weten, waarvan we aannemen dat het geldt. Dat kunnen dingen zijn als “elk even getal is deelbaar door twee”. Verder kan deze verzameling bijvoorbeeld formules bevatten voor het omvormen van uitdrukkingen, die ergens anders zijn bewezen en waarvan we al aannemen dat ze gelden, bijvoorbeeld:

$$(a+b{)}^2=a^2+2ab+b^2;a,b\in \mathbb{R}$$

Nu vormen we stap voor stap de beweringen in de verzameling Ax om totdat we de bewering ϕ krijgen. Alle omvormingen moeten logisch correct zijn en moeten overeenkomen met de basisregels van de propositielogica. Als we bijvoorbeeld de vorige formule willen bewijzen, gaan we te werk door de uitdrukking

$$(a+b{)}^2$$

om te vormen met equivalente bewerkingen totdat we de uitdrukking aan de rechterkant krijgen. Ik laat het zien:

$$(a+b{)}^2=(a+b)\cdot (a+b)=a\cdot a+a\cdot b+b\cdot a+b\cdot b=$$

$$=a\cdot a+2ab+b\cdot b=a^2+2ab+b^2$$

In de eerste stap hebben we de macht uitgeschreven als een product, in de tweede stap hebben we de haakjes uitgewerkt, in de derde stap hebben we gelijksoortige termen opgeteld en in de laatste stap hebben we het product als macht geschreven. Elke stap was een elementaire omvorming die we ons konden veroorloven, waarbij we aannemen dat elk van deze elementaire omvormingen in de verzameling Ax zit.

Belangrijk is dat elke omvorming geldig moet zijn en moet uitgaan van iets wat we al kennen. Een wiskundig bewijs is een soort evolutie: met kleine stapjes krijgen we uit de ene uitdrukking een andere.

Triviale bewijzen

Een triviaal bewijs (ook wel vanzelfsprekend bewijs) is een vakterm voor een bewijs dat niet op het bord past, dus het wordt overgeslagen en de leerling leert het als huiswerk uit het boek. :-) Even serieus: triviale bewijzen zijn bewijzen die typisch in één triviale stap uit een definitie volgen.

We proberen het te laten zien aan de hand van een voorbeeld: neem de verzameling van de natuurlijke getallen, dus de verzameling getallen ℕ = {1, 2, 3, …}. We kunnen nu zeggen dat elke breuk van de vorm:

$$\frac{q}{p};q,p\in \mathbb{N}$$

een geldige breuk is, dus dat we geen paar getallen q, p vinden waarvoor de gegeven breuk geen betekenis heeft. Hoe zouden we dat bewijzen? Eerst moeten we uitzoeken wanneer een breuk geen betekenis heeft. Een breuk heeft geen betekenis als er nul in de noemer staat (we kunnen niet delen door nul). We moeten dus bewijzen dat p ≠ 0 voor alle mogelijke p. Maar we weten dat we p uit de natuurlijke getallen nemen, die we hebben gedefinieerd als ℕ = {1, 2, 3, …}. De verzameling van de natuurlijke getallen bevat geen nul, dus het getal p is altijd ongelijk aan nul.

$$\mathrm{\forall }p\in \mathbb{N}:p\ne 0$$

En het bewijs is geleverd. We weten dat als zowel de teller als de noemer van een breuk natuurlijke getallen zijn, de breuk geldig is.

Triviale bewijzen zijn meestal echt triviaal, maar alleen als je de omringende context kent. Als je bijvoorbeeld het begrip verzameling niet begrijpt of niet weet wat het betekent dat p een element is van de verzameling ℕ, dan was ook dit bewijs voor jou niet triviaal. Triviale bewijzen onderscheiden zich dus niet doordat ze eenvoudig zijn, maar doordat ze kort zijn en eenvoudig uit een (willekeurig moeilijke) context volgen.

Tegenvoorbeeld

Een tegenvoorbeeld is waarschijnlijk de eenvoudigste manier om te bewijzen dat een bepaalde uitdrukking niet waar is. Het woord niet is hier belangrijk. Een tegenvoorbeeld kan namelijk een geval aanwijzen waarin de gegeven uitspraak niet geldt, maar in het algemeen zijn zelfs heel veel voorbeelden niet genoeg als er oneindig veel elementen zijn die we zouden moeten testen.

Voorbeeld: “elk natuurlijk getal is groter dan tien”. Hoe bewijzen we dat dit niet waar is? Een tegenvoorbeeld bij onze bewering is bijvoorbeeld het getal vijf. Het getal vijf is een natuurlijk getal en niet groter dan tien. We kunnen de bewering niet bewijzen door een paar natuurlijke getallen op te noemen die groter zijn dan tien. Je kunt niet zeggen “de natuurlijke getallen 11, 12, 13, 123 en 5345 zijn groter dan 10, dus de uitspraak is waar”. Dat kan niet. We hebben dan alleen maar een paar voorbeelden gekozen waarvoor onze bewering geldt, maar dat zegt niets over de andere getallen, die we helemaal niet hebben genoemd.

Tweede voorbeeld: elke man die langer is dan twee meter heeft bruine of blauwe ogen. Ik neem aan dat maar weinig mensen een tegenvoorbeeld kunnen vinden. Wat zegt ons dat over de uitspraak? Nou, helemaal niets. Als we geen tegenvoorbeeld kunnen vinden, betekent dat niet noodzakelijk dat de uitspraak waar is. Er kan ergens een tegenvoorbeeld bestaan, we kunnen het alleen op dit moment niet vinden. Dat we geen tegenvoorbeeld kunnen vinden, bewijst niet dat de bewering waar is.

Direct bewijs

Het basistype bewijs is het directe bewijs. We gaan droog te werk volgens de definitie en vormen de eerste uitspraak om totdat we de uitspraak krijgen die we willen krijgen. Typisch willen we een uitspraak bewijzen die de vorm heeft van een implicatie A ⇒ B, waarbij A een beginpunt, een aanname is en B de uitspraak die we willen afleiden, bewijzen. Als uitspraak A geldt, dan geldt uitspraak B. Vaak krijgen we alleen de uitspraak B gegeven, dus wat we willen bewijzen, en de uitspraak A moeten we zelf op een geschikte manier kiezen.

Dan volgt een werkwijze waarbij we met implicaties verdere uitspraken afleiden en als laatste uitspraak staat de uitspraak B. Schematisch zou dat zo kunnen worden geschreven:

$$A\Rightarrow A_1\Rightarrow A_2\Rightarrow A_3\Rightarrow \dots \Rightarrow A_n\Rightarrow B$$

Als voorbeeld bewijzen we dat de uitspraak

$$a>1\Rightarrow a^2>1$$

geldt. Nu stap voor stap:

1. Omdat a>1, geldt zeker ook a>0 en ook a ≠ 0 (we verzwakken eigenlijk alleen de voorwaarde).
2. Omdat a niet gelijk is aan nul en positief is, kunnen we de hele ongelijkheid zonder zorgen met de variabele a vermenigvuldigen. Als a nul zou zijn, zou de strikte ongelijkheid niet behouden blijven (we zouden 0>0 krijgen), en als het negatief zou zijn, zouden we het ongelijkheidsteken moeten omdraaien. Na vermenigvuldiging met de variabele a krijgen we de uitdrukking a²>a.
3. Op dit moment weten we dat a>1 en tegelijk weten we dat a²>a. Als we deze twee uitdrukkingen samenvoegen, krijgen we: a²>a>1.
4. Hieruit laten we alleen de middelste uitdrukking weg en we hebben de uitdrukking a²>1. Dat mochten we doen omdat a groter is dan één en a² groter is dan a. Als a² groter is dan a en a tegelijk groter is dan één, is a² zeker groter dan één.

Symbolisch zouden we het zo kunnen schrijven:

$$a>1\Rightarrow a>0\Rightarrow a^2>a\Rightarrow a^2>a>1\Rightarrow a^2>1.$$

Indirect bewijs

Een indirect bewijs maakt meer gebruik van de eigenschappen van de implicatie. Als we een bewering van de vorm A ⇒ B moeten bewijzen, kunnen we de contrapositie gebruiken en bewijzen

$$\mathrm{\neg }B\Rightarrow \mathrm{\neg }A.$$

Deze werkwijze kan soms voordeliger zijn dan bijvoorbeeld een direct bewijs. Een soortgelijke werkwijze gebruikt het bewijs uit het ongerijmde, waartoe elk indirect bewijs kan worden herleid. We proberen indirect de volgende bewering te bewijzen:

$$a-b=0\Rightarrow a=b.$$

Nu nemen we de contrapositie van de implicatie:

$$\begin{array}{rcl}\mathrm{\neg }(a=b)& \Rightarrow & \mathrm{\neg }(a-b=0)\\ a\ne b& \Rightarrow & a-b\ne 0\end{array}$$

Als a ≠ b, kunnen we b schrijven als de som b = a + x, waarbij x de afstand van het getal b tot het getal a voorstelt. De uitdrukking verandert zo:

$$a\ne (a+x)\Rightarrow a-(a+x)\ne 0;x\ne 0$$

We laten de variabelen a tegen elkaar wegvallen waar dat kan:

$$0\ne x\Rightarrow -x\ne 0;x\ne 0$$

Omdat x ≠ 0, is ook −x ≠ 0, dus de implicatie geldt. De bewering is bewezen, waarmee ook de oorspronkelijke uitspraak

$$a-b=0\Rightarrow a=b.$$

geldt.

Andere bewijstechnieken zijn bijvoorbeeld het al genoemde bewijs uit het ongerijmde of het bewijs met volledige inductie.

Verdere bronnen

• Wiskundig bewijs op Wikipedia