Hoe Wiskunde Werkt: Bewijzen Bewijzen

Hoe Wiskunde Werkt: Bewijzen

1

3. Bewijzen

Wat is een bewijs, hoe vind je een bewijs, en waarvoor dient het? Deze vragen raken aan de kern van de vraag wat wiskunde is — een emotioneel punt voor wiskundigen! Sommigen zien het als het enige wezenlijke van de wiskunde, andere beweren dat de relatie van bewijzen tot de wiskunde is, als die van de spelling tot de poëzie. Een ding is duidelijk. Er is geen ander wetenschapsgebied waar het “harde bewijs” zo’n belangrijke rol speelt. Van de juridische tot de natuurwetenschappelijke wereld, nergens een bewijs zo absoluut. In dit college zal ik voornamelijk aan de hand van (eenvoudige) voorbeelden proberen te illustreren hoe bewijzen werken in de praktijk, en wat zo al de verschillende stijlvormen zijn die door de jaren ontwikkeld zijn. In het college van Johan van Benthem zal dieper worden ingegaan op de formele structuren achter de bewijsvoering. Vergelijk het met een college over muziek: ik zal wat muziekstukken en frases laten horen, terwijl in het tweede college de compositieleer wordt behandeld.

3.1. Wiskunde versus mens en natuur Het geven van een wiskundig bewijs is natuurlijk in de eerste plaats een typsich menselijke handeling. (Ook al kan daar best een computer bij gebruikt worden, of kan de taakverdeling over vele personen en lange tijd worden verdeeld.) Het is het “aha” of “eureka” gevoel. Een moderne machine analogie is het gevoel dat er ergens iets in ons brein “klik” zegt. Er gaat een schakelaar over in onze neuronen en ineens “zien” we dat de bewering waar is. Een bewijs is een alles of niets proces. Of de redenering is correct, óf deze is niet correct, er is geen middenweg. In het eerste geval hebben we een universele waarheid gevonden, die ook waar is in de Andromeda-nevel, of over een biljoen jaar. Daarbij doet er niet toe hoe we aan de overkant zijn gekomen, misschien kan het eleganter, korter, diper, maar het resultaat is daar en blijft staan. Daarentegen als de redenering niet klopt is het resultaat absoluut nihil. De bewering kan nog steeds goed of fout zijn. We kunnen natuurlijk altijd leren van onze fouten, en misschien hebben we onderweg een goed beeld gekregen van de context en meer inspiratie opgedaan ... Maar het is toch een beetje als een vakantiereis die niet is doorgegaan. Een bewijs kan niet voor 99% correct zijn. Als er een klein foutje in is geslopen, een detail is overzien, dan stort het bouwwerk volledig in. Dit “klik” gevoel raakt aan de merwaardige relatie tussen de drie hoofdrolspelers van deze collegereeks: de wiskunde, de natuur en de mens (geest, cognitie). Hierbij past een mooi beeld bedacht door de Britse mathematisch fysicus Roger Penrose. Penrose is de bedenker van allerlei onmogelijke figuren. Na in 1954 kennisgemaakt te hebben met M.C. Escher, publiceerde hij met zijn vader, de bekende psycholoog Lionel Penrose, een artikel over de onmogelijke driehoek, die uiteindelijk door Escher weer in vele vormen beroemd gemaakt zou worden. Ik gebruik hem hier om de “magische driehoek” wiskunde-natuur-

2

Robbert Dijkgraaf

mens te illustreren:

Deze driehoek staat symbolisch voor de relatie tussen de drie ingredienten. Onze wiskunde is bedacht door mensen. De definities en bewijzen worden gegeven door wiskundigen. Wiskunde is het kennisgebied dat door wiskundigen wordt uitgebreid. Het is een activiteit in onze hersenen. Maar de mens is onderdeel van de natuur. We zijn zeer complexe fysisch/chemische systemen. Onze gedachten zijn slechts Phosphorreactionen. Daarom is de wiskunde ook een onderdeel van de fysische realiteit. Maar (tot onze verbazing) kunnen de natuurwetten met akelige precisie beschreven worden door wiskundige formules. Dit is bekende uitspraak van Galilei, dat het boek van de natuur geschreven is in de taal van de wiskunde, de befaamde unreasonable effectiveness of mathematics in the natural sciences van de mathematisch fysicus Eugene Wigner. Dus diezelfde natuur, die de mens en daarmee de wiskunde bevat, is zelfs slecht een onderdeel van de wiskunde! Maar we kunnen ons ook andere, wiskundige correcte, realiteiten voorstellen (met meer of minder dimensies bijvoorbeeld). Onze wereld is dus slechts één van de vele imaginaire werelden die de wiskunde bevat. Deze situatie wordt goed weergegeven door Eschers onmogelijke trap.


3

3.2. Mooie bewijzen: het BOEK Er is voor wiskundigen een belangrijk estethisch aspect aan een bewijs. De legendarische wiskundige Paul Erdös dacht graag dat er ergens Het Boek1 is, waar van ieder probleem het ultieme elegante bewijs wordt opgeschreven en bijgehouden.

3.3. Geschiedenis In de geschiedenis zien we vele voorbeelden waar het niet vinden van een bewijs uiteindelijk een belangrijke ontwikkeling heeft geleid. In het college Symmetrie noemden we al hoe de onmogelijkheid van het vinden van een oplossing van de algemene vijdfegraads vergelijking via Abel en Galois tot de geboorte van de groepentheorie heeft geleid. Ook was lange tijd de vraag of het zogenaamde parallelenpostulaat van Euclides (de uitspraak dat door een punt dat niet op een lijn ligt precies een lijn gaat die de eerste lijn niet snijdt) volgt uit de vier andere postulaten van de Euclidische meetkunde. Deze vraag werd pas in de negentiende eeuw beantwoord, toen niet-Euclidische meetkundes werden geconstrueerd, zoals de meetkunde op een bol (waar iedere tweetal lijnen elkaar snijdt) of op een hyperboloide (waar er oneindig vaal lijnen zijnen die de gegeven lijn niet snijden). Een tweede belangrijk voorbeeld in de ontwikkeling van de wiskunde was de paradox van Russell (begin 20ste eeuw), vaak ook bekend als de kappersparadox: In een stad wordt iedere man geschoren door de kapper tenzij hij zichzelf scheert. Wie scheert de kapper? Russell beschouwde de verzameling V van alle verzamelingen. Dit is een vreemde verzameling, omdat V een element is van V zelf, V ∈V Laten we alle verzamelingen verdelen in twee categorieen: verzamelingen X met de eigenschap dat ze element van zichzelf (X ∈ X), en verzamelingen die de eigenschap niet hebben (X 6∈ X). Vele voorbeelden vallen natuurlijk in de laatste categorie. Laat W nu de verzameling zijn van alle verzamelingen die niet in zichzelf zitten W = {verzamelingen X met X 6∈ X} In welke van de twee categorieen valt W ? Als we aannemen dat W ∈ W dan moeten we concluderen dat W 6∈ W . Vice versa, als we aannemen dat W 6∈ W dan zit W in de categorie van verzamelingen die wel in zichzelf zitten. We concluderen dus W 6∈ W ⇒ W ∈ W W ∈ W ⇒ W 6∈ W Maar in de wiskunde kunnen niet tegelijkertijd een bewering en de negatie waar zijn. Dan kunnen we namelijk alles concluderen. Als zowel A als ¬A (“niet A”) waar zijn dan 1 Zie Proofs from THE BOOK, Martin Aigner en Gnter M. Ziegler. Springer-Verlag Berlin Heidelberg, 1998.

4

Robbert Dijkgraaf

volgt iedere andere uitspraak B volgens de logische regels. Immers, ten eerste volgt uit A dat ook A ∨ B (“A of B”) waar is. A ⇒ A ∨ B. (Als ik thuis ben, dan ben ik ook thuis of op college.) Ten tweede volgt uit (A ∨ B) gecombineerd met niet A dat B waar is. (A ∨ B) ∧ ¬A ⇒ B. (Als ik gezegd heb dat ik thuis ben of op college ben, en het wordt ook duidelijk dat ik niet thuis ben, dan moet ik op college zijn.) Russells paradox leidt dus tot een grote crisis in de wiskunde. Deze is uiteindelijk opgelost door de verzamelingen van het type V of W niet langer toe te staan.

3.4. Getaltheorie De getaltheorie is de koningin van de wiskunde, en geeft aanleiding tot vele eenvoudige uitspraken die in vele voorbeelden lijken op te gaan. Deze uitspraken zijn soms zeer gemakkelijk maar vaak ook zeer moeilijk op te lossen. Een gemakkelijk te bewijzen voorbeeld is de bewering dat er oneindig veel gehele getallen x, y, z zijn die aan de Pythagoras relatie voldoen x2 + y 2 = z 2 (zijden zijn van een rechthoekige driehoek) Een goed voorbeeld van een moeilijk resultaat is de befaamde Laatste Stelling van Fermat (1630), die zegt dat dit niet langer het geval is als we hogere machten dan de tweede macht beschouwen. Fermat. De vergelijking xn + y n = z n heeft voor n > 2 geen niet-triviale oplossingen (d.w.z. met x, y, z 6= 0) Dit bewijs heeft zeer lang op zich laten wachten. Pas in 1994 heeft Andrew Wiles uiteindelijk het bewijs gegeven, na er zeven jaar in stilte aan gewerkt te hebben. Zijn bewijs maakte gebruik van de allermodernste technieken (arithmetische meetkunde, Galois theorie, elliptische krommen, modulaire vormen) en is zeker niet het bewijs waarvan Pierre de Fermat in de kantlijn beweerde het gevonden te hebben. Zulke vermoedens kunnen ook anders beslecht worden. In 1769 generaliseerde Euler de stelling van Fermat, door in plaats van drie getallen vier of meer getallen te nemen. Een eenvoudige specialisatie van zijn vermoeden is bijvoorbeeld Euler. De vergelijking x4 + y 4 + z 4 = w4 heeft geen (niet-triviale) oplossingen. Ook dit resultaat bleef lang staan tot Noam Elkies in 1988 (op 22-jarige leeftijd) liet zien dat 26824404 + 153656394 + 187967604 = 206156734 . Dit tegenvoorbeeld was het einde van het vermoeden van Euler. Een ander gemakkelijk voorbeeld uit de getaltheorie.


5

Er zijn oneindig veel priemgetallen. Bewijs uit het ongerijmde. Stel er zijn een eindig aantal priemgetallen p1 , . . . , p n Vorm het getal q = p1 p2 · · · pn + 1 Dit getal heeft de eigenschap dat bij deling door het priemgetal p1 de rest 1 is, idem voor deling door p2 , p3 tot en met pn . Het is dus slechts alleen deelbaar door 1 en zichzelf, en dus een nieuw priemgetal wat niet in de oorspronkelijke lijst stond. Daarmee is het uitgangspunt tot een tegenspraak geleid. Weer een moeilijk geval: het vermoeden van Goldbach (1742) Goldbach. Ieder even getal is te schrijven als de som van twee priemgetallen. Dit vermoeden is nog wijd open. Er was zelfs een miljoen dollar mee te verdienen, in een publiciteitsstunt van de uitgever van de roman Uncle Petros and Goldbach’s Conjecture van Apostolos Doxiadis. (Niet te verwarren met de zeven Clay-prijzen, die te verdienen zijn met de oplossing van zeven (nog diepere) wiskundige problemen zoals bijvoorbeeld de Riemann hypothese.

3.5. Stijlfiguren Een bekende anecdote over Gauss is dat hij op zevenjarige op school aan het werk werd gezet met de opgave alle getallen van 1 tot en met 100 optellen. Gauss zag onmiddellijk dat het antwoord 5050 was. Waarom: 1 + 100 = 101, zo ook 2 + 99 = 101, etc tot aan 50 + 51 = 101. In totaal vinden we daarmee 50 · 101 = 5050. Dit laat zich formaliseren tot n X 1 k = n(n + 1) 2 k=0 Laten we deze uitspraak p(n) noemen. We kunnen dit ook met volledige inductie bewijzen. Volledige inductie stelt ons in staat de uitspraak p(n) te bewijzen voor alle n ∈ N uitgaande van twee stappen. 1. Toon aan dat p(0) waar is. 2. Leidt p(n + 1) af, uitgaande dat p(n) waar is. In dit geval reduceert stap 1 tot de uitspraak 0 = 0. In stap 2 moeten we bewijzen dat 1 1 n(n + 1) + n = 1 = (n + 1)(n + 2) 2 2 hetgeen eenvoudig volgt. Er zijn ook andere bewijzen mogelijk die meer een “aha” gevoel geven. Bijvoorbeeld

6

Robbert Dijkgraaf

grafisch:

2×

=

De eerste figuur is duidelijk de som 1 + 2 + . . . + n. De tweede figuur heeft oppervlak n × (n + 1).

3.6. De duiventil Er zijn altijd minstens twee Nederlanders met evenveel haren op hun hoofd. Dit volgt uit het duiventil (pidgeon hole) principe. Als er vijf duiven zijn, maar slecht drie hokjes in de duiventil, dan zullen er minstens twee duiven een hokje moeten delen. Dit geeft aanleiding tot het volgende principe: Als we p objecten in q dozen doen met p > q, dan is er minstens één doos met twee objecten. Meer formeel gezegd: als we een afbeelding f : X→Y hebben tussen twee (zeg, eindige) verzamelingen X en Y , en als |X| > |Y |, dan kan de afbeelding f niet alle elementen van X naar verschillende elementen van Y sturen. Er is dus een y ∈ Y met de eigenschap dat f (xi ) = f (x2 ) = y met x1 en x2 twee verschillende elementen van X. We zeggen dat de afbeelding f niet injectief is. In het eerste voorbeeld is X de verzameling van alle Nederlanders, Y = {0, 1, 2, . . . , N }, waarbij N het maximaal aantal mogelijke haren dat biologisch gesproken op een mens kan groeien. X bevat zo’n 16 miljoen elementen. Een zeer conservatieve schatting (uitgaande van het model Neanderthaler) geeft dat N niet groter kan zijn dan zo’n 5 miljoen.

3.7. Tegen de intuitie Een omgeving waar een bewijs zeer nodig is, is als de te bewijzen bewering tegen onze intuitie gaat. Hier zijn een aantal voorbeelden van zulke beweringen uit de topologie (rubber-meetkunde). Hierbij is een wiskundige “bal” is een opgevulde bol, technisch gesproken de deelverzameling x2 + y 2 + z 2 ≤ 1 in R3 . Banch-Tarski: Het is mogelijk een bal in vijf stukken te snijden die in elkaar geplakt kunnen worden tot twee ballen van dezelfde grootte. Natuurlijk zijn de stukken zeer vreemd van vorm. Zo hebben ze bijvoorbeeld geen gedefinieerd volume of massa. (Deze paradox is afhankelijk van het keuzeaxioma.)


7

Brouwer dekpuntstelling: Een continue afbeelding van een bal naar een bal laat op z’n minst een punt vast. Deze laatste bewering kan als volgt worden toegepast: als u in een kopje koffie roert, zal uiteindelijk op z’n minst een koffiemolecuul op z’n oorspronkelijke plaats terugkeren. Een ander voorbeeld: neem twee identieke vellen papier. Verfrommel de eerste en leg deze boven op de tweede. Er is nu minstens een punt op het eerste vel dat precies boven het corresponderende punt op het tweede vel ligt. Een eenvoudig (eendimensionaal) voorbeeld van een topologische stelling is het volgende. Stel we hebben een lijn die begint in punt A en eindigt in punt B. Ergens middenin ligt punt C. Op tijdstip t = 0 staan we in A, op tijdstip t = 1 zijn we in B aangekomen. Toon aan dat er een tijdstip t is tussen 0 en 1 waarbij we punt C passeren.

3.8. Blikwisseling Soms wordt een bewijs ineens duidelijk als we van perspektief veranderen. Een voorbeeld. Het getal 12 heeft zes delers, te weten 1,2,3,4,6, en 12. Laten we het aantal delers van n schrijven als d(n). Dus er geldt d(12) = 6. Als we n varieren zal het getal d(n) zeer onregelmatig springen. Zo is d(13) = 2 omdat 13 een priemgetal is met alleen de delers 1 en 13. Wat is het gemiddelde n 1X d(k) n k=1 van het aantal delers van de eerste n getallen? Dit lijkt geen mooi patroon te hebben, totdat we het in een tabel weergeven:

1 2 3 4 5 6 7 8 9 10 11 12

1 •

2 3 • • • •

4 5 • • •

6 7 • • • •

•

8 9 • • • • •

• •

10 11 12 • • • • • • • • •

• • • • • •

Om het gemiddelde aantal delers van de eerste 12 getallen te berekenen tellen we gewoon het aantal • en delen door 12. De kolommen zijn inderdaad niet regelmatig, maar de rijen zijn perfect regelmatig. In de nde rij herhalen de delers zich precies na n plaatsen. We moeten het plaatje dus over 90 graden draaien. Door nu over de rijen te sommeren in

8

Robbert Dijkgraaf

plaats van de kolommen krijgen we n

n

1 X hni 1X d(k) = n k=1 n k=1 k waarbij [·] afronden naar een geheel getal voorstelt. Voor grote n kunnen we dit benaderen als Z n n n 1 X hni X 1 dx = ∼ = log n n k=1 k k x 1 k=1

3.9. Het nut van bewijzen en definities Bill Thurston (Fieldsmedaille 1984) heeft een zeer interessant en tegendraadse analyse gegeven van het nut van bewijzen in de wiskunde2 . Hij voert daarin aan dat een exacte oplossing in de wiskunde niet altijd het enige doel is. Om verdere vooruitgang te stimuleren is het ook van belang dat de context en de nieuwe ideeën goed worden uitgedragen. Hij illustreert deze gedachte met het begrip definitie. In de wiskunde worden objecten precies gedefinieerd. Maar vaak mist zo’n definitie de vele andere aspecten, associaties. Een goed voorbeeld is het begrip afgeleide van een functie f (x), zeg van R naar R. De technische definitie, zoals je die in een standaard college analyse leert is niet erg verhelderend op eerste gezicht 1. Formeel. De afgeleide f 0 (x) in x voldoet aan: f (x + ∆x) − f (x) 0 ∀ > 0, ∃δ > 0 : 0 < |∆x| < 0 ⇒ − f (x) < . ∆x Maar er zijn nog andere gezichtspunten die enerzijds het begrip groter maken en anderzijds nieuwe generalisaties suggereren. 2. Snelheid. De afgeleide f 0 (t) is de instantane snelheid van f (t) waarbij t nu de tijd is. Dit geeft direct een goede intuitie wat te verwachten als we een functie f : R → Rn verwachten. De afgeleide is dan een vector. 3. Meetkunde. De afgeleide als tangens van de hoek die de raaklijn van de grafiek van de functie maakt. Dit suggereert hoe de afgeleide te definieren als we een functie van meer veranderlijke hebben. In dat geval krijgen we een raakvlak. 4. Infinitesimaal. De afgeleide is de infinitesimale verandering in de functiewaarde f (x) als we de variable x infinitesimaal veranderen. Dit is natuurlijk dicht bij de oorspronkelijke definitie van Leibnitz en Newton. De afgeleide als ratio df dx van de infinitesimale df en dx. In dit geval wordt het duidelijk dat als we een discrete functie f (n) hebben (met n een geheel getal) de discrete variant het verschil f (n+1)−f (n) is. f0 =

2 W.P. Thurston, On proof and progress in mathematics, Bull. Amer. Math. Soc. (NS) 30 (1994), 161–177.


9

5. Symbolisch. Van speciale functies is de afgeleide gemakkelijk. Bijvoorbeeld als f (x) = xn dan is f 0 (x) = nxn−1 . De afgeleide nemen is dus de symbolische operatie op veeltermen xn → nxn−1 Dit stelt ons in staat om de afgeleide ook te definieren als x helemaal geen getal is, maar wel een vermenigvuldiging heeft. Deze kijk heeft geleid tot bijvoorbeeld een goede definite van de afgeleide van een knoop! 6. Benadering. In de buurt van het punt x kunnen we de functie y = f (x) benaderen door een lineare functie y = ax + b met a = f 0 (x). f (x + z) ∼ f (x) + f 0 (x)z. 7. Microscopisch. Als we onbeperkt inzomen op het punt x dan kunnen we f (x) door de lineaire benadering vervangen. Alles wordt lineair in deze limiet. Daarom leren we lineaire algebra. Zo gaat de rij nog een lange tijd door. Ieder perspektief geeft een nieuwe benadering. Uiteindelijk moest Thurston zelf wel eens de volgende definitie gebruiken. 37. Thurston. De afgeleide is de Lagrangiaanse sectie van de coraakbundel welke aanleiding geeft tot de connectievorm voor de unieke vlakke connectie op de triviale Rbundel waarvoor de grafiek van f parallel is.

10

Robbert Dijkgraaf

3.10. Opgave 1. Vind een formule voor de som van de eerste n kwadraten, d.w.z. de som 1 + 22 + 32 + . . . + n2 . 2. Probeer een ander voorbeeld van het Thurston-effect te geven, d.w.z. een wiskundig begrip dat meer dan een definities of interpretaties heeft.

Hoe Wiskunde Werkt: Bewijzen Bewijzen

Recommend Documents