De fraaiste wiskundige bewijzen #1

_{Bron: Wikimedia Commons. Maker: Hamilton Richards.
Licentie: CC-BY-SA. Edsger Dijkstra in 2002}
Nóg een bewijs van de stelling van Pythagoras, door de Nederlandse Wiskundige en Informaticus Edsger Dijkstra. Hij is vooral bekend, nu ja, bekend – menigeen zal nooit van hem gehoord hebben, vanwege zijn werk in de informatica en zijn kortste pad algoritme: een algoritme dat je b.v. kunt gebruiken om in een applicatie als Google Maps de korste weg te vinden van A naar B. Op zich ook een elegant algoritme.

Hij was verder bekend omdat hij alles met zijn vulpen schreef. De stukjes die hij schreef worden EWD’s genoemd, en deze zijn allemaal gescand en te lezen op de universiteit waar hij lange tijd heeft gezeten: De universiteit van Austin, in Texas. In 2002 is hij in Nuenen overleden.

Dit bewijs betreft EWD 975, daarin is zijn handschrift te zien. Een HTML-versie vind je hier. Het origineel is in het Engels, maar hieronder volgt de uitwerking in het Nederlands.

Het vereist op zich alleen middelbare school kennis van wiskunde, maar is denk ik wel iets lastiger dan het vorige Pythagorasbewijs.

Stelling van Pythagoras: In een rechthoekige driehoek is het kwadraat van de lengte van de schuine zijde gelijk aan de som van de kwadraten van de twee andere zijden.

We beginnen met een willekeurige driehoek:



We weten dat de som van de hoeken α, β, γ 180°C is. Of, in radialen, π. We zouden de stelling van Pythagoras dus kunnen uitdrukken als:

γ = π/2 ⇒ a² + b² = c²

In woorden: Als γ een rechte hoek is, dan geldt de stelling van Pythagoras. Echter, we weten ook dat α + β + γ = π, dus als we dat invullen krijgen we:

γ = (α + β + γ) / 2 ⇔ 2γ = α + β + γ ⇔ γ = α + β

Dat is niet zo’n vreemde uitdrukking, want inderdaad als γ een rechte hoek is moet α + β ook wel 90° of π/2 zijn. We kunnen dus zeggen:

γ = α + β ⇒ a² + b² = c²

Dijkstra vraagt zich nu af ook geldt:

γ = α + β ≡ a² + b² = c²

Wat dan equivalent is aan:

γ ≠ α + β ≡ a² + b² ≠ c²

Hij merkt nu op dat als als x ≠ y dat dan geldt: x < y óf x > y. (Maar niet beide natuurlijk.) Zijn hypothese is nu dat je zelfs kunt zeggen dat:

α + β < γ ≡ a² + b² < c²
α + β > γ ≡ a² + b² > c²

Beschouw nu de variant van bovenstaande driehoek, we hebben twee punten H en K toegevoegd:



Dit is dus duidelijk een driehoek waarin geldt dat α + β < γ. Maar het bewijs is dus algemener, dit is alleen ter visualisatie. Maar in dit geval zien we dus dat de oppervlakte van ΔCKB en ΔAHC, die niet overlappen, kleiner is dan de oppervlakte van ΔABC. We duiden de oppervlakte van ΔCKB simpelweg aan met ‘CKB’ en van ΔAHC met ‘AHC’, enz., dan geldt voor de driehoek hierboven:

CKB + AHC < ABC

Het moge duidelijk zijn dat als α + β = γ dat H en K dan precies samenvallen (immers α + β = π/2 in dat geval) en dus geldt dan ook:

CKB + AHC = ABC.

En dat als α + β > γ, dat dan (merk trouwens op dat dit heel veel mogelijke plaatjes geeft in de relatieve positie van A, B, H, en K, dus daarom tekenen we die plaatjes ook niet ) geldt:

CKB + AHC > ABC.

Door nu gebruik te maken van de signum functie kunnen we heel eenvoudig schrijven:

signum(α + β - γ) = signum(CKB + AHC - ABC).

Verder valt op dat ΔABC, ΔAHC en ΔCKB gelijkvormig zijn, immers, ze hebben alle drie de hoeken α, β en γ. Omdat ze gelijkvormig zijn geldt:

CKB/a² = AHC/b² = ABC/c².

Dus de oppervlakte gedeeld door het kwadraat van de langste zijde is gelijk (*), en in het bijzonder geldt dat dit positief is. We merken daarom op:

signum(CKB + AHC - ABC) = signum(a² + b² - c²).

Dus:

signum(α + β - γ) = signum(a² + b² - c²)

Deze stelling zegt, in Dijkstra’s woorden eigenlijk ‘vier keer zoveel als de stelling van Pythagoras’.

<sub>* Over die gelijkvormigheid: Neem een driehoek met basis a en hoogte h, en neem een geschaalde driehoek met basis ca en dus hoogte ch. De oppervlakte van de eerste is 1/2·a·h, en van de tweede is 1/2·a·h·c². Hun oppervlaktes verhouden zich dus als c², wat inderdaad ook voor de kwadraten van die zijdes geldt

Plaatjes van de driehoeken zijn eigen werk.</sub>

Merk trouwens op dat Dijkstra’s bewijs nog wel wat nuttige opmerkingen op het laatst heeft, die ik niet heb overgenomen.

quote:

Op dinsdag 6 oktober 2009 01:30 schreef Dennis_enzo het volgende:
Dijkstra is een held, maar ik denk niet dat navigatie systemen het Dijkstra algoritme gebruiken Eerder een algoritme dat heuristische schattingen doet.

Klopt. Een variant van A* kunnen ze wel mogelijk eens gebruiken, bovendien kun je heel goed gebruik maken van het gegeven dat er snelwegen zijn en bepaalde ‘markers’ op een landkaart en het feit dat afstanden euclidisch zijn, en nog wat informatie, maar voor het idee.

quote:

Op dinsdag 6 oktober 2009 17:55 schreef Pietverdriet het volgende:
Kan iemand me het bewijs voor de laatste stelling van Fermat uitleggen?

Vanaf waar volg je het niet helemaal meer?

quote:

Op dinsdag 6 oktober 2009 18:06 schreef thabit het volgende:

[..]

Ik kan dit kort beantwoorden: Nee. Het bewijs bevat hele zware wiskunde waarvoor je jaren moet studeren om ze je eigen te maken. Er is wel een Horizon-documentaire van de BBC over het bewijs. Als je een hele kleine indruk wilt krijgen van wat erbij komt kijken, dan raad ik je aan om die te kijken, is vast wel te vinden op YouTube. Wil je meer dan alleen een kleine indruk krijgen, dan vrees ik dat je een aantal jaar flink moet studeren.

Deze:

Het begin is het aangrijpendst, als hij zo geëmotioneerd raakt.

quote:

Op dinsdag 6 oktober 2009 19:54 schreef ReWout het volgende:
Even een vraagje over fermat... het is destijds bewezen. Maar wat zijn we ermee verder gekomen ?

Nou, tja, er zijn veel wiskundige vakgebieden ontgonnen en met elkaar verbonden. Dat is eigenlijk het grootste gedeelte. Wiskunde is veel verbanden leggen. Numerieke berekeningen en voorgaande deelbewijzen hadden eigenlijk al wel de meesten doen vermoeden dat de stelling waar was. Dus in die zin is de uitkomst niet schokkend.

Maar de weg ernaartoe wél. Het is een beetje te vergelijken misschien met ‘oké nu zijn de Amerikanen naar de maan geweest en staat daar een vlag’, wat hebben we aan die vlag? Nu ja, die vlag is nog het minst interessante, maar alle technieken en kennis die zijn ontwikkeld om dat haalbaar te maken, díé zijn natuurlijk superbelangrijk.

Een oude bekende van de middelbare school. De kwadratische vergelijking. Je weet wel, je hebt , en om één of andere reden geldt:



Waarom? Hoe komen ze daarop… We bekijken eerst eens een wat simpeler geval: x² + bx = c. Dit kan heel aardig gevisualiseerd worden. Bedenk dat ‘kwadraat’ van het Latijnse ‘quadratus’ komt, dat vierkant betekent.

We kunnen daarom de formule:



Ook visualiseren als een vierkant met oppervlakte x², een rechthoek met oppervlakte bx en nog een constante term c.



De rechthoek met oppervlakte bx splitsen we nu in twee gelijke rechthoeken:



Dit komt overeen met:



Nu ‘herordenen’ we de vergelijking:



Dit is alleen als visueel hulpmiddel, aan de niet-visuele vergelijking verandert niets. We kunnen nu echter de linkerkant van de vierkant volledig maken, er een vierkant van maken. Dat is waarom deze methode ‘completing the square’ heet in het Engels. Daartoe tellen we (b/2)² op aan beide zijden:



Of, als vergelijking:



We zien nu al, visueel, dat we nu links een vierkant hebben:



Of als vergelijking:



Dit is eigenlijk het idee achter het bewijs. Door nu wortel te trekken is zo op te lossen wat x is. De rest is af te maken door relatief eenvoudig formule manipuleren. Eigenlijk is dat saai, en niet eens heel fraai. Daarom staat het in een spoiler.

SPOILER

Om spoilers te kunnen lezen moet je zijn ingelogd. Je moet je daarvoor eerst gratis Registreren. Ook kun je spoilers niet lezen als je een ban hebt.

quote:

Op dinsdag 6 oktober 2009 23:48 schreef alsem het volgende:
deze is pas echt fraai:
[ afbeelding ]


en dan krijg je dit soort ongein:
[ afbeelding ]

met oneindig veel vormen die allemaal oneindig verschillend zijn.. ik heb er even over moeten nadenken, maar na een dag lang onzoomen op de mandelbrot fractal kon ik geen 2 de zelfde vinden

Ja, maar, ja, maar, ik wil niet vervelend doen, maar kun je ook vertellen hoe die verzameling tot stand komt? Want die kleuren zitten natuurlijk niet per se in die vergelijking.

Alsem, volgens mij snap je toch niet heel veel van fractals. Ik zal het t.z.t. – nu is het te laat – eens proberen uit te leggen. Merk ook op dat je formule niet juist was, jij gaf de formule voor de Tricorn-fractal waarbij je de complex toegevoegde neemt. De gewone Mandelbrotiteratie wordt gegeven door .

Overigens is het wel razend interessant, dus goed dat je het noemt.

Oké, fractaluitleg. Een fractal is wiskundig gezien eigenlijk alleen een verzameling punten. in een vlak (het complexe vlak om precies te zijn). Een punt hoort of wél bij die verzameling, of niet.


^{Bron: Wikimedia Commons. Maker: Connelly. Publiek Domein.}

Hier boven zie je dus de Mandelbrotverzameling in het complexe vlak. Zwart hoort er wel bij, wit niet. Waar komen dan die kleurtjes vandaan? Dat heeft te maken met het rekenproces dat bepaalt of zo’n punt in het vlak zit of niet.

Een complex getal bestaat uit een reële en een imaginaire component, doorgaans geschreven als a + bi, a is de reële component, b de imaginaire. Dit zie je ook hierboven. Het punt (1 + 0i) ligt bijvoorbeeld ‘op de x-as’, d.w.z. de horizontale, of eigenlijk reële as, het punt (0 + i) ligt op de verticale as, of imaginaire as. En het punt (1 + i) ligt in het kwadrant rechtsboven.

Complexe getallen kun je vrij eenvoudig optellen en aftrekken, dat is ongeveer zoals je zou verwachten: (2 + 3i) + (5 + 4i) = 7 + 7i. Vermenigvuldigen is ook niet zo raar, dat geeft: (2 + 3i)(5 + 4i) = (10 + 8i + 15i + 12i²) = (10 + 23i + 12i²). Alleen nu is er wel een ding speciaal, er geldt namelijk i² = -1. Dus we kunnen het vorige getal schrijven als (-2 + 23i).

Dat is dus de bekende i² = -1, of soms ook als i = √(-1) geschreven. Als je dit weet, weet je eigenlijk al genoeg om die Mandelbrot fractal te kunnen teken.

Je pakt namelijk een punt uit dit complexe vlak, zeg c, en dan zeg je: z₁ = c, z₂ = z₁*z₁ + c, z₃ = z₂*z₂ + c, en zo voort. Of in z’n algemeenheid: z_n+1 = z_n*z_n + c. Voor sommige waarden van c levert dit een heel groot getal op, dat steeds maar groter wordt. Die zitten niet in je verzameling. Voor sommige waarden geldt dat het getal niet steeds groter wordt. Neem bijvoorbeeld i:

z₁ = i
z₂ = i*i + i = -1 + i
z₃ = (-1 + i)² + i = (i² - 2i + 1) + i = -i
z₄ = (-i)² + i = -1 + i
z₅ = z₃

En zo voort. We komen dus in een rondje terecht. Probeer het eens voor c = 1:

z₁ = 1
z₂ = 1*1 + 1 = 2
z₃ = 2*2 + 1 = 5
z₄ = 5*5 + 1 = 26.

Dit gaat dus hopeloos mis, dit punt verdwijnt. De truc is nu: wanneer weet je zeker dat zo’n punt verdwijnt? Zoals je ziet kan een punt namelijk ‘op en neer klappen’ zoals in het geval van c = i. Als je rond de oorsprong een cirkel trekt met straal 2 in bovenstaand figuur, dan is het zeker dat als je iteratie een keertje buiten die cirkel komt, dat het dan misgaat.

Op deze manier kunnen we ook tot de kleuren komen: We tellen hoe vaak we bovenstaand proces moeten uitvoeren om buiten die cirkel te geraken. Dan krijg je zoiets:


^{Bron: Wikimedia Commons. Maker: Wolfgang Beyer. Licentie: CC-BY-SA.}

De zwarte punten zitten dus in de verzameling, de gekleurde niet. En je ziet heel duidelijke banden met dezelfde kleur. De meer roodachtige aan de buitenkant zijn direct al weg in feite; de rood-paarse kleur daarbinnen doet er 1 iteratie over, die daarbinnen 2, de blauw tinten nog langer, en de groen tinten nog weer langer, en de paarse tinten binnenin, grenzend aan het zwarte vlak, doen er nóg weer langer over.

Die kleuren geven dus eigenlijk vooral het berekeningsproces weer, en hoe lang je erover doet om te berekenen dat zo’n punt niet in de verzameling zit, maar zijn niet ‘de fractal zelf’ ook al wordt misschien vaak wel zo geassocieerd. De fractal zelf, de Mandelbrotverzameling in dit geval is dus het zwarte.

Maar hoe komt men dan aan zo’n afbeelding?


^{Bron: Wikimedia Commons. Maker: Wolfgang Beyer. Licentie: CC-BY-SA.}

Waarom zie je daar niet van die duidelijke strepen met dezelfde kleur? Dat is in feite gewoon een bewerkingstruc. Die strepen worden als het ware uitgevlakt en in een continue overgang geplaatst. Stel dat je een punt c hebt dat na n iteraties ‘buiten de cirkel is gekomen’ dan hoort daar dan de volgende waarde bij: v = n - log₂log₂ |z_n|, hier is z_n dus het punt dat voor het eerst buiten de cirkel valt, |z_n| geeft de afstand van dat punt tot de oorsprong (dus als rechte lijn gezien). Op deze manier krijg je een continu waardenverloop: immers punten die net ietsje verder weg komen krijgen een iets andere kleur. De truc is nu om die waarden ook nog op geschikte kleuren af te beelden.. Maar als je dat doet, dan krijg je dus zulke mooie, vloeiende, afbeeldingen.

De moeilijkheid, en het fascinerende aan fractals is, dat je op een gegeven moment je iteratie moet afkappen. Je kunt wel zeker weten dat een punt niet in de verzameling zit, en van sommige punten is ook duidelijk dat ze er wél inzitten, maar op het grensvlak is het vaak niet duidelijk. Het enige dat je dan kunt doen is gewoon rekenen. 100 iteraties proberen en kijken of het punt al ontsnapt. Of 1000. Of 10000. En zo voort. In die zin is een fractal dus altijd een benadering. Die grenspunten ontsnappen misschien niet na 1000 iteraties, en zijn daarom zwart gekleurd, maar mogelijk wel na 10000!

Dat is ook de reden dat men (alleen) kan zeggen: de oppervlakte van de verzameling is 1,506 591 77 ± 0,000 000 08. Om dat precies uit te rekenen zou je oneindig lang moeten doorrekenen. Er is geen formule met een exacte uitkomst te geven.

Zo’n tekening is dus altijd een benadering. Het grappige is ook dat de uitvinder van deze verzameling, Benoît Mandelbrot, in het begin, op basis van zulke computerafbeeldingen dacht dat de verzameling niet verbonden was, m.a.w. dat je niet via een zwart punt over alleen maar zwarte punten naar elk ander zwart punt kunt komen. Er zouden dus eilandjes zijn. Dat vermoeden was gebaseerd op tekeningen gerenderd door de computer waarbij heel dunne haarlijntjes niet zichtbaar waren. Je moet immers kiezen hoe nauwkeurig je zoiets doet. Als je c = -1.1 en c = 1.2 uitrekent, moet je dan c = 1.15 ook nog doen? En c = 1.155? En c = 1.1555? Je moet ergens stoppen. Het kan best dat dus in je tekening twee pixels naast elkaar beiden een kleurtje hebben, maar dat er tussen eigenlijk nog een – in die tekening onzichtbaar – zwart lijntje loopt.

Inmiddels is bewezen dat de gehele verzameling wel verbonden is, maar die inzoomfilmpjes die je ziet tonen aan dat je in principe steekds maar kunt vergroten en vergroten op de grens en telkens nieuw detail ziet. En wát je dan precies ziet, dat is pas te zeggen nadat het is uitgerekend. Je kunt dus niet een patroon ontdekken voorspellen. Ter vergelijking, een breuk als 1/7 ≈ 1,142857142857, maar die herhaalt zichzelf telkens. Je kunt zo voorspellen dat cijfer 1, 7, 13, 19, enz. een 1 zijn. Als iemand dus wil weten wat cijfer 283043 achter de komma is kun je dat direct zeggen zonder tot 283043 cijfers achter de komma door te rekenen omdat er een patroon in zit. Dat kan bij zo’n fractal niet. Je moet het helemaal uitrekenen.

quote:

Op woensdag 7 oktober 2009 12:42 schreef speknek het volgende:
Ik ben altijd bijzonder zwak in formele bewijzen geweest, toch teveel een chaoot, dus even een domme vraag:
[..]

Moet je dan niet eerst bewijzen dat combinaties van priemgetallen alleen weer deelbaar zijn door priemgetallen? Of zit dat besloten in de vermenigvuldiging?

Ik heb inderdaad nagelaten te vermelden dat elk getal een unieke priemfactorisatie heeft. Dat was op zich opzettelijk. Elk getal heeft een unieke factorisatie in priemgetallen. En we weten dus dat die factorisatie niet de getallen kan bevatten uit ons rijtje. Ergo, ons rijtje is niet compleet.

Overigens laat ik formeel gezien wel meer steekjes vallen, maar het is niet mijn bedoeling om strikt formeel te zijn. In die fractaluitleg praat ik b.v. over ‘complexe getallen die steeds maar groter worden’, alhoewel dat natuurlijk formeel gezien niet zo zinnig is.

Ik denk dat ook zonder die formaliteiten echter het idee, de slimmigheid van de redenering, wel over komt. (Of het fascinerende erachter.)