Wiskundige bewijstechnieken

In de wiskunde wordt elke bewering, propositie of stelling bewezen voor men aanvaardt dat hij waar is. Het is zowat het hoofdkenmerk van de wiskunde. De gewoonte om alles rigoureus te bewijzen, dateert van de oude Grieken. Zij zijn begonnen met het leveren van bewijzen voor elke stelling die ze ontdekten, met als belangrijkste bron de Elementen van Euclides, waarin ruim 400 stellingen inclusief bewijs staan. Nu bestaan er veel verschillende soorten van bewijzen: een direct bewijs, een bewijs door volledige inductie, een bewijs uit het ongerijmde... Het is voor een wiskundige handig om verschillende technieken voor de hand te hebben, maar hij of zij moet ook juist kunnen inschatten welke techniek hij of zij kan gebruiken.

Direct bewijs

Een direct bewijs is het meest ‘klassieke’ bewijs: je vertrekt van het gegeven en door logisch te redeneren en eventueel vorige resultaten te gebruiken, werk je naar het te bewijzen toe.

Voorbeeld

Beschouw volgende bewering: 'Zij n een natuurlijk getal. Als n even is, is n² ook even'.

Het getal n is even, dus het is te schrijven als 2k. Nu is het kwadraat van n = 2k gelijk aan n² = 4k². Aangezien 4k² deelbaar is door 4, is het even en dus is n² even.

Contrapositie

Een bewijs door contrapositie steunt op het feit dat de uitspraak 'Als P, dan Q' equivalent is met 'Als niet-Q, dan niet-P'.

Hierbij zijn P en Q uitspraken, zoals 'n is even'. Equivalent wil zeggen dat als de ene uitspraak waar is, dat de andere dan ook waar is en omgekeerd. Een voorbeeldje om de equivalentie 'aan te tonen'. neem weer de uitspraak 'Als n even is, is n² ook even'. Hier is P ’n is even’ en Q is ‘n² is even’. De contrapositie van die uitspraak is dus ‘Als n² oneven is, is n oneven’. Stel namelijk dat n² oneven is maar n even. Eerder was al bewezen dat dan n² even is. Maar dat is in tegenspraak met het feit dat n² oneven is. Dus moet n oneven zijn.

Voorbeeld

Een bewijs met behulp van contrapositie van de volgende uitspraak: ‘Als n² even is, is ook n even.’ De contrapositie hiervan is ‘Als n oneven is, is n² oneven.’

Aangezien n oneven is, is n = 2k + 1. Dan is n² = 4k² + 4k + 1 = 2(2k² + 2k) +1. Bijgevolg is n² een oneven getal.

Bewijs uit het ongerijmde

Bij het ‘bewijs’ dat ‘Als P, dan Q’ equivalent is met ‘Als niet-Q, dan niet-P’, was er een bewijs uit het ongerijmde gegeven. Bij zo’n bewijs veronderstel je dat wat je moet bewijzen niet waar is, en je probeert dan een tegenspraak te bekomen.

Voorbeeld

Het voorbeeld bij uitstek is het bewijs dat √2 een irrationaal getal is. Stel namelijk dat √2 een rationaal getal is. Dan valt het te schrijven als m/n, waarbij m en n geen gemeenschappelijke delers hebben. Beide leden kwadrateren geeft 2 = m²/n². Hieruit volgt dat 2n² = m². Dus is m² even. Eerder was al bewezen dat dit impliceert dat m even is. Bijgevolg is m = 2k en is dus 2n² = 4k². Links en recht 2 wegdelen geeft n² = 2k². Hieruit volgt dan dat n² en dus n ook even moet zijn. Maar dan hebben zowel m als n een factor 2, wat in tegenspraak is met het feit dat m en n geen gemeenschappelijke delers hebben. De veronderstelling dat √2 rationaal is, is dus fout.

Bewijs door gevalsonderscheid

Het is soms moeilijk om voor alle mogelijke gevallen van een stelling hetzelfde bewijs te geven. Vandaar dat er soms gevalsonderscheid gemaakt wordt.

Voorbeeld

Volgende bewering kan bewezen worden met behulp van gevalsonderscheid: 'Voor elk natuurlijk getal n is n² + n even.' Merk eerst en vooral op dat n² + n te schrijven valt als n(n + 1). Stel nu dat n even is. Dan volgt meteen dat n(n + 1) even is. Stel nu dat n oneven is. Dan is n + 1 even, en bijgevolg is ook n(n + 1) even.

Bewijs door volledige inductie

Deze techniek kun je vergelijken met een rij dominosteentjes: als je het eerste omver gooit, zal de rest ook vallen. Dat is precies wat er bij volledige inductie gedaan wordt: eerst toont men aan dat het eerste steentje valt. Dan toont men aan dat, als het n-de steentje gevallen is, dan ook het (n + 1)-ste steentje zal vallen. Er bestaan (lichte) varianten op deze techniek, maar het basisidee is altijd hetzelfde. In eerste instantie wordt vaak aan stellingen met getallen gedacht, maar er zijn resultaten uit bijvoorbeeld de abstracte algebra of de informatica die met volledige inductie worden bewezen. Het is dus echt een wijd gebruikte techniek.

Voorbeeld

• Bewijs van volgende formule: 1 + 2 + 3 + ... + n = n(n+1)/2.
• Voor n = 1 staat er in het rechterlid 1 en in het linkerlid 1 * 2 / 2 = 1. Voor n = 1 klopt de formule. Stel nu dat ze klopt voor n, dus dat 1 + 2 + 3 + ... + n = n(n+1)/2. Er rest te bewijzen dat de formule klopt voor n + 1. Tel bij beide leden n + 1 op, dan staat er: 1 + 2 + 3 + ... + n + n + 1 = n(n+1)/2 + n + 1.
• Herschrijf het rechterlid als volgt: n(n + 1)/2 + n + 1 = (n + 1)(n/2 + 1) = (n + 1)(n + 2)/2.
• Alles tezamen geeft dit: 1 + 2 + 3 + ... + n + n + 1 = (n + 1)(n + 2)/2 = (n + 1)( (n + 1) + 1)/2
• en dus klopt de formule ook voor n + 1.