De fraaiste wiskundige bewijzen #1

Zijn er evenveel breuken als gehele positieve getallen?

Een drieluik! Vandaag het eerste deel. Het idee voor vandaag is om te bewijzen dat er evenveel rationale getallen, ook wel bekend als breuken, zijn als natuurlijke getallen, d.w.z. de positieve gehele getallen.

Wat ‘evenveel’ is zullen we vandaag eveneens verduidelijken. Het volgende stuk is de Calkin-Wilf-reeks, en als laatste zullen we Cantors diagonaal-argument doen.

Deze aflevering is (hopelijk) goed te volgen ook al heb je nooit veel wiskunde gehad.

De natuurlijke getallen

We beginnen met de natuurlijke getallen, dit zijn de getallen 1, 2, 3, 4, 5 en zo voort. Deze verzameling wordt meestal aangeduid met een hoofdletter N (eigenlijk: ℕ):



_{Soms stopt men 0 er ook bij, maar ik vandaag niet.}

Deze verzameling bevat uiteraard oneindig veel getallen. Er is niet zoiets als ‘een grootste natuurlijk getal’. Alhoewel het er oneindig veel zijn, kunnen we ze toch systematisch opsommen. Je begint gewoon bij 1, en dan telkens eentje meer. Je komt nooit bij het eind, maar je kunt weet zeker dat je ook geen getal overslaat als je zo opsomt. En dat is belangrijk, daarom wordt deze verzameling aftelbaar oneindig genoemd.

De gehele getallen
Nu bekijken we de verzameling van alle gehele getallen, meestal aangeduid met een Z (ℤ) van het Duitse Zahlen. Je kunt je ℤ voorstellen als:



Nu beweer ik ‘er zijn evenveel gehele getallen als natuurlijke getallen’. Wat ‘evenveel’ inhoudt zal ik nog iets preciseren. Normaliter, bij eindige verzamelingen, zeg je b.v. {a, b, c} en {1, 2, 3} bevatten evenveel elementen omdat ze allebei 3 elementen bevatten. Maar ja, het is niet in een getal uit te drukken hoeveel elementen ℕ bevat, oneindig is geen getal immers.

‘Evenveel’ precies gemaakt
Daarom is er een iets algemenere definitie voor evenveel. Namelijk, twee verzamelingen bevatten evenveel elementen als er een 1:1 koppeling te vinden tussen de elementen van beide verzamelingen. Kortom, je kunt paartjes maken met één element uit de ene verzameling, en eentje uit de andere verzameling, waarbij alle elementen gebruikt, maar waarbij je geen enkel element dubbel gebruikt, bijvoorbeeld:



Hierboven zie je twee manieren om de verzamelingen {1,2,3} en {a,b,c} aan elkaar te koppelen. Ook zie je dat voor {1,2} en {a,b,c} niet zo’n koppeling te vinden is. Je komt er immers altijd eentje te kort. In dit voorbeeld kun je c niet koppelen.

In het geval van oneindige verzamelingen kan dit een soms een wat onverwacht resultaat geven, maar hopelijk is het toch redelijk logisch als je erover nadenkt. Neem b.v. de even natuurlijke getallen ({2,4,6,…}) en alle natuurlijke getallen:



Het is duidelijk dat die koppeling helemaal door te trekken. Elk even getal n wordt gekoppeld aan n/2 en elk natuurlijk getal m aan het even getal 2m. In deze zin zijn er dus evenveel gehele getallen als even getallen. Nu is duidelijk (hopelijk) wat ik met evenveel bedoel.

Een koppeling tussen ℕ en ℤ
Er zijn op die manier ook evenveel gehele getallen als natuurlijke getallen:



Het is ook duidelijk dat deze koppeling gewoon door te trekken is, bovenaan som je de natuurlijke getallen op, onderaan gaat het verder met -4, 4, -5, 5, -6, 6 enz.

Dus er zijn ook evenveel gehele getallen als natuurlijke getallen.

Er zijn evenveel breuken als natuurlijke getallen!
Nu komen we bij de volgende stap. De eerstvolgende grotere verzameling van getallen die wiskundigen gebruiken is Q (of ℚ), die bestaat uit alle breuken. Dus b.v. 3/5, 7/3, 1/8, 9/2, enz. Hieronder zie je alle positieve breuken systematisch opgesomd als een vierkant dat oneindig is naar twee kanten:



Het misschien nog wel duidelijk hoe je één rij of één kolom kunt koppelen aan de natuurlijke getallen, maar allemaal? Toch kan dit. Het volgende werkt duidelijk niet:



Want aan welk getal wordt 2/3 bijvoorbeeld gekoppeld? Dat is niet te zeggen. Want er zijn duidelijk oneindig veel breuken in de vorm 1/n. En 2/3 komt pas ‘daarna’. Maar ‘na oneindig’ is er niet veel, en al helemaal geen getal. Dus er moet iets slimmers bedacht worden.

En dat gaat zo (volg de blauwe lijn):



Je gaat dus systematisch de diagonalen af, dit levert de volgende koppeling:



En dit systeem is wél door te trekken. Op het plaatje staat al grofweg hoe het werkt.

Tot slot

Een nadeel van deze koppeling is dat je er dubbele vormen in hebt, zoals 4/4, 3/1 en 6/2. In een volgende post zullen we een heel slimme manier van opsommen zien, die zulke ‘dubbelen’ overslaat.