Wiskundig bewijs

Bewijs uit de Elementen van Euclides, waarin wordt aangetoond dat er bij elk lijnstuk en gelijkzijdige driehoek bestaat waarvan het lijnstuk een zijde is. Het is een bewijs door constructie

Een wiskundig bewijs is het volgens formele regels aantonen dat, gegeven bepaalde axioma's, een bepaalde stelling waar is.

Algemeen

Het leveren van wiskundig bewijs gaat terug op de oude Grieken. Uit oudere beschavingen zijn geen bewijzen bekend, de wiskunde bestond voor de Grieken uit het oplossen van concrete problemen. Een belangrijke bron vormen de Elementen van Euclides waarin naast een axiomatische opbouw en definities ook ruim 400 stellingen staan met bewijzen. Vaak wordt daarbij vooral gedacht aan meetkunde, maar ook getaltheorie komt aan de orde. Zo staat de stelling van Euclides in de Elementen, die zegt dat het aantal priemgetallen oneindig is.

Voor het verkrijgen van het bewijs worden de regels van de logica gebruikt, meer in het bijzonder deductieve methodes en geen inductieve of empirische. Deze methode was al enige generaties in gebruik toen Aristoteles de eerste duidelijke definitie van een wiskundig bewijs gaf.

Het bewezen resultaat is een stelling. Een eenvoudige stelling die alleen als hulpmiddel voor het bewijs van een andere stelling dient, is een hulpstelling. Is een stelling eenmaal bewezen, dan kan een volgend bewijs gebruikmaken van de geldigheid van die stelling. Een stelling (meestal een toepassing) die meteen volgt uit een andere stelling is een gevolg of corollarium.

Het wiskundige bewijs is de manier waarop wiskundige kennis wordt verkregen. Nochtans zijn er beweringen waarvan wiskundigen denken dat zij correct zijn, maar waarvoor het bewijs niet is geleverd. Deze beweringen hebben de status van vermoeden en behoren (nog) niet tot de wiskundige kennis. De wil om vermoedens te bewijzen vormt wel een stimulans tot wiskundige ontwikkelingen.

Opzet van een bewijs

Een wiskundig bewijs begint met het vermelden van de stelling die bewezen moet worden. Soms is het nodig duidelijk te maken welke definities worden gehanteerd, maar veelal valt dit al uit de wiskundige context af te lezen. Door middel van logisch redeneren wordt uiteindelijk toegewerkt naar het verlangde resultaat.

Veelal wordt, zeker in complexere bewijzen, gebruikgemaakt van tussenresultaten (al dan niet in de vorm van een hulpstelling). Bewijzen hebben dan ook, als ze schematisch worden weergegeven, vaak een boomstructuur.

De bewijstheorie is de tak van wiskunde die zich bezighoudt met volledig formele bewijzen. In de regel worden bewijzen door wiskundigen echter niet volledig formeel beschreven, maar uiteengezet in min of meer informele taal. Dit komt de leesbaarheid ten goede, maar kan ook tot discussies leiden. Zelfs kan door de informele bewoordingen een gat of een fout in het bewijs verdoezeld worden. Het volledig formaliseren van een willekeurig wiskundig bewijs zou echter leiden tot een veel langer bewijs, vrijwel geheel in formuletaal geschreven, wat moeilijk te lezen en begrijpen is. Sommige bewijzen zijn van zichzelf toch al lang; zo bevatte het beroemde bewijs van de laatste stelling van Fermat door Andrew Wiles meer dan 100 pagina's, terwijl in een apart bewijs van bijna 20 pagina's nog een hulpstelling werd bewezen. Een extreem geval is de classificatie van eindige enkelvoudige groepen, waarvan het bewijs tot in de jaren 1980 verspreid was over 500 gespecialiseerde publicaties.

Als formeel einde van een bewijs schrijft de wiskundige Quod erat demonstrandum, afgekort QED, of het symbool ■ of □ om aan te geven dat het bewijs is geleverd.

Soorten bewijzen

Bewijstechnieken

Enkele gebruikelijke bewijsvoeringstechnieken zijn:

• Direct bewijs: In dit type bewijs wordt de stelling bewezen met gebruik van alleen de axioma's en definities, de logica en eerder op dezelfde wijze bewezen stellingen.
• Wiskundige inductie: deze techniek kan worden toegepast bij welgefundeerde verzamelingen, vaak voor natuurlijke getallen, rijen en reeksen. In een dergelijk bewijs laat men de geldigheid zien van een basisgeval of nulgeval, en bewijst men een inductie-regel, die bewijst dat als het gevraagde geldt voor een element, dan ook voor de volgende. Merk op dat, ondanks de naam, wiskundige inductie een deductieve en geen inductieve methode is.
• Bewijs door gevalsonderscheiding: Bij dit soort bewijs wordt hetgeen te bewijzen onderverdeeld in een aantal verschillende gevallen, die elk afzonderlijk worden bewezen.
• Bewijs uit het ongerijmde: Bij deze redeneerwijze wordt het omgekeerde van de stelling aangenomen en wordt aangetoond dat dit tot een tegenspraak leidt.
• Bewijs door contrapositie: Bij dit bewijstype wordt de stelling als het ware omgekeerd: de bewering als A dan B wordt bewezen via de equivalente bewering als niet B dan niet A.
• Bewijs door constructie: Deze bewijsvorm bewijst het bestaan van een wiskundig object door er een voorbeeld van te construeren. Deze bewijsvorm wordt veel gebruikt om de onjuistheid van een bewering aan te geven, men geeft dan een tegenvoorbeeld.
• Bewijs door oneindige afdaling: Deze techniek kan met name worden toegepast bij natuurlijke getallen of een andere aftelbare welgeordende verzamelingen. Men bewijst het niet bestaan van een element uit die verzameling met een bepaalde eigenschap, door aan te tonen dat als er zo'n element bestaat, er ook een kleiner element moet bestaan met die eigenschap. Zo ontstaat een oneindige keten van elementen kleiner dan het veronderstelde element, terwijl er maar een eindige hoeveelheid van dergelijke elementen is.

Elementair bewijs

Bij een elementair bewijs worden alleen basistechnieken gebruikt. Het begrip is niet formeel omschreven, maar wordt desalniettemin veel gebruikt. In de getaltheorie wordt meestal vrij specifiek bedoeld dat het resultaat verkregen is op basis van alleen de axioma's van Peano, dus bijvoorbeeld zonder gebruik te maken van complexe getallen. Een beroemde stelling waarvan gedacht werd dat zij niet elementair kon worden bewezen, is de priemgetalstelling, maar Atle Selberg en Paul Erdős gaven in 1949 een elementair bewijs van deze stelling. Een veelgemaakte vergissing is dat met een elementair bewijs een eenvoudig bewijs wordt bedoeld, elementaire bewijzen kunnen razend ingewikkeld zijn.

Computers

Gebruik van computers om een stelling te bewijzen

Tot halverwege de twintigste eeuw was het de bedoeling dat ieder bewijs gecontroleerd moest kunnen worden door een competente wiskundige. Sindsdien heeft echter de computer de intrede gedaan die berekeningen kan doen van een omvang en een complexiteit die voor mensen niet haalbaar is. Het eerste bewijs met computerondersteuning dat bekendheid genoot, was het bewijs van de vierkleurenstelling door Appel en Haken in 1976. Het bewijs reduceerde het probleem tot 1936 te controleren gevallen, waarvan de kleurbaarheid met vier kleuren vervolgens werd aangetoond.

Sommige wiskundigen zijn bezorgd over de mogelijkheid van onvolkomenheden in de gebruikte software of hardware, waardoor incorrecte bewijzen ongemerkt hun intrede zouden kunnen doen. Daartegen is in te brengen dat ook mensen geen feilloze bewijzen afleveren en dat het op verschillende manieren proberen te bewijzen van een stelling of het op verschillende manieren inzetten (bijvoorbeeld gebruikmakend van verschillende software) van de rekenkracht van een computer de kans op fouten flink reduceert.

Een ander nadeel van een computerbewijs is dat het de waarheid van een bewering aantoont, maar in tegenstelling tot een uitgeschreven bewijs weinig inzicht verschaft in de onderliggende redenering of aanleiding geeft tot de ontdekking van vernieuwende concepten.

Ook op een ander vlak heeft de computer het werk van de wiskundige en het bewijzen van karakter doen veranderen. Vroeger bestond het werk van een wiskundige uit het schrijven van bewijzen. De gereedschappen waren potlood en papier, soms passer en liniaal en nog zeldzamer een rekenmachine. Dat veranderde echter met de opkomst van de computer. Hierdoor is het veel eenvoudiger om wiskundig te experimenteren. Om berekeningen uit te voeren die kunnen helpen bij het bewijzen van een stelling is de computeralgebra nuttig. Dit zijn computerprogramma's die zowel kunnen helpen bij lineaire algebra, analyse en meetkunde. Chaostheorie en fractals zijn voorbeelden van wiskunde die meer uit experimenten zijn voortgekomen dan uit deductie. De werkelijke kennis is echter uiteindelijk in het klassieke raamwerk van het wiskundig bewijs geplaatst.

Bewijzen van stellingen over computerprogramma's

In de theoretische informatica worden beweringen onderzocht over het al dan niet berekenbaar zijn van bepaalde functies. De meest gebruikelijke vorm van een berekenbaarheidsbewijs is een (geannoteerd) computerprogramma.

Anderzijds wordt de correctheid van een computerprogramma (ten opzichte van een specificatie) geleverd aan de hand van semantische regels voor de individuele programma-instructies (toekenning, voorwaardelijke opdracht, lus,...)

Bewijs zonder woorden

Bewijs zonder woorden van de stelling van Pythagoras

Een bewijs zonder woorden is eigenlijk geen bewijs, maar een schets van hoe een stelling zou kunnen worden bewezen in de vorm van een visuele presentatie. De bedoeling is dat de presentatie de geldigheid van de stelling duidelijk maakt, zonder dat daarvoor woorden nodig zijn. Vaak is het bewijs zonder woorden elegant en blijft het sterker hangen dan het werkelijke formele bewijs. In wiskunde-onderwijs en populair-wetenschappelijke literatuur wordt daarom graag gebruikgemaakt van dit type demonstraties. Niet alleen meetkunde, maar ook eenvoudige getaltheorie kan met een bewijs zonder woorden worden geadstrueerd.

Onbeslisbare beweringen

Soms kan aangetoond worden dat een bewering niet bewezen kan worden uitgaande van een bepaald stelsel van axioma's. Een voorbeeld hiervan is de continuümhypothese. In de meeste axiomastelsels zijn er beweringen die noch bewezen noch ontkracht kunnen worden, zoals volgt uit de onvolledigheidsstellingen van Gödel. Het bewijs van deze stelling laat zien dat in voldoend ingewikkelde axiomastelsels een wiskundige stelling geformuleerd kan worden die eigenlijk een codering is van de paradox Er is geen bewijs voor deze stelling. Dergelijke beweringen zijn onbeslisbaar.

Een beroemd voorbeeld is het parallellenpostulaat van Euclides dat als vijfde axioma werd opgenomen. Vaak is geprobeerd om dit postulaat te bewijzen uit de vier eerdere postulaten. Dit lukte echter niet. Later werd aangetoond dat er, ingebed in de euclidische ruimte, niet-euclidische meetkundes te ontwerpen zijn waarin dit parallellenpostulaat niet geldt, maar de overige vier wel: de hyperbolische en elliptische meetkunde. Daarmee werd aangetoond dat het parallellenpostulaat niet beslisbaar is in een axiomastelsel met alleen de eerste vier postulaten.

Recenter noemde David Hilbert in zijn programma voor de grondslagen van de wiskunde het bewijs van de consistentie van de leer der natuurlijke getallen een belangrijke opgave voor de wiskundigen van de twintigste eeuw. In 1931 toonde Kurt Gödel met zijn Tweede Onvolledigheidsstelling aan dat een dergelijk bewijs niet kan geleverd worden.

Voetnoten