Je leest:

Een nieuw bewijs van Cantors stelling

Een nieuw bewijs van Cantors stelling

Auteur: | 21 februari 2008

Georg Cantor (1845-1918) was de eerste wiskundige die de raadsels rond het begrip ‘oneindigheid’ wist op te helderen. Cantor besefte dat oneindige verzamelingen verschillende ‘groottes’ kunnen hebben. Zijn beroemde bewijs dat de verzameling van reële getallen groter is dan de verzameling natuurlijke getallen, het zogeheten ‘diagonaalargument van Cantor’, heeft sinds kort een broertje: de Amerikaan Matthew Baker publiceerde vorige maand een nieuw bewijs van Cantors stelling.

‘Oneindig’ is groter dan elk getal. Kun je zeggen ‘hoe groot’ oneindig is? Deze vraag is niet zo gemakkelijk te beantwoorden. De Duitse wiskundige Georg Cantor (1845-1918) maakte als eerste een serieuze studie van het begrip ‘oneindig’. Hij bewees dat oneindig in oneindig veel groottes voorkomt.

∞ is het symbool voor oneindig

De verzameling natuurlijke getallen, dat zijn de getallen 1, 2, 3, 4, enzovoorts, heeft de kleinste orde van oneindigheid. Cantor noemt de verzameling van natuurlijke getallen ‘aftelbaar’, omdat je deze getallen op een rij kunt zetten. De verzameling van gehele getallen, dat zijn de getallen …, -3, -2, -1, 0, 1, 2, 3, …, lijkt misschien twee keer zo groot als de verzameling natuurlijke getallen, maar voor Cantor zijn de verzameling van natuurlijke getallen en de verzameling van gehele getallen even groot, omdat je de gehele getallen eveneens op een rij kunt zetten: 0, 1, -1, 2, -2, 3, -3, 4, -4, enzovoorts. Zelfs de verzameling van alle breuken is aftelbaar; je kunt ze als volgt op een rij zetten: 0, 1, -1, 2, -2, 1/2, -1/2, 3, -3, 1/3, -1/3, 2/3, -2/3, 3/2, -3/2, 4, -4, enzovoorts (kun je zelf bedenken hoe het verder gaat?).

N, Z en Q zijn de wiskundige notaties voor achtereenvolgens de verzameling natuurlijke getallen, gehele getallen en rationale getallen (breuken). Hoewel de natuurlijke getallen allemaal deel uitmaken van de gehele getallen (maar omgekeerd niet) en de gehele getallen deel uitmaken van de breuken (maar omgekeerd niet), hebben deze drie verzamelingen dezelfde ‘orde van oneindigheid’: de elementen van deze verzamelingen kun je op een rij zetten. Cantor noemt deze verzamelingen daarom aftelbaar.

Met de breuken is de getallenlijn nog niet helemaal gevuld. Zo zijn bijvoorbeeld de getallen √2 en π (pi, de verhouding tussen omtrek en diameter van een cirkel) niet als breuk te schrijven. Dit soort getallen heten ‘irrationaal’. De decimalen van dit soort getallen repeteren niet. Andere voorbeelden van irrationale getallen zijn 1,01001000100001000001… en 0,1234567891011121314… In deze getallen zit wel een patroon (bij het eerste getal staat achter de komma één 0 en dan een 1, dan twee keer een 0 gevolgd door een 1, dan drie keer een 0 gevolgd door een 1, enzovoorts; bij het tweede getal, het getal van Champernowne, zijn achter de komma alle natuurlijke getallen achter elkaar geplakt), maar de decimalen repeteren niet en daarom zijn deze getallen niet als breuk te schrijven.

De verzameling van alle reële getallen, dat zijn de breuken én de irrationale getallen, kun je niet op een rij zetten. Cantor bewees dat met zijn beroemd geworden diagonaalmethode. Hij concludeerde: de verzameling van reële getallen heeft een hogere orde van oneindigheid dan de verzameling van natuurlijke getallen (en gehele getallen, en breuken). Cantor noemt oneindige verzamelingen die niet aftelbaar zijn, ‘overaftelbaar’.

Georg Cantor (1845-1918)

Matthew H. Baker van het Georgia Institute of Technology in Atlanta kwam onlangs met een nieuw bewijs van het feit dat de verzameling reële getallen niet aftelbaar is. Zijn bewijs is geheel anders dan dat van Cantor. Hij beschrijft een wiskundig spelletje dat als basis van het bewijs dient.

Een wiskundig spel

Alice en Bob spelen het volgende spel. Als eerste wordt een deelverzameling S van het interval [0, 1] (alle reële getallen tussen 0 en 1) gekozen. S kan bijvoorbeeld de verzameling [ ¼ , ¾ ] (het interval bestaande uit alle reële getallen tussen ¼ en ¾) zijn, of { 1/ n | n = 1, 2, 3, 4, … } (de verzameling van alle breuken met een 1 in de teller). Er zijn natuurlijk oneindig veel keuzes voor S. Ook het gehele interval [0, 1] is een toegestane keuze voor S.

Alice is als eerste aan zet. Zij kiest een reëel getal tussen 0 en 1. Noem de keuze van Alice a1. Dit getal kan bijvoorbeeld 0,528 zijn, of 2/3, of √(2/3), enzovoorts. Vervolgens is Bob aan de beurt. Hij kiest een reëel getal tussen a1 en 1. Noem Bobs keuze b1. Dan is Alice weer: zij kiest een reëel getal tussen a1 en b1, noem dit getal a2. Daarna kiest Bob een getal tussen a2 en b1, noem dit getal b2.

Zo gaan Alice en Bob verder: afwisselend kiezen ze een getal dat steeds ligt tussen de laatste twee gekozen getallen. De getallen a1, a2, a3, … (de door Alice gekozen getallen) en b1, b2, b3, … (Bobs getallen) liggen in het interval [0, 1], bijvoorbeeld zoals in het volgende plaatje:

Vanwege de spelregel dat een gekozen getal altijd tussen de laatste twee gekozen getallen ligt, geldt altijd dat 0 < a1 < a2 < a3 < … en 1 > b1 > b2 > b3 > … Verder is an < bm voor elke n en m. Wiskundigen noemen de rij a1, a2, a3, … monotoon stijgend. Bovendien is deze rij begrensd, omdat elk getal uit de rij kleiner is dan 1. Een bekende stelling in de wiskunde zegt dat elke begrensde monotoon stijgende rij een limiet heeft; noem de limiet van de rij a1, a2, a3, … α. In gewone-mensentaal: de getallen van Alice komen dichter en dichter in de buurt van een bepaald getal α dat groter is dan alle ai‘s maar kleiner dan alle bi’s.

Alice wint het spel indien α in de verzameling S (de deelverzameling van [0, 1] die bij aanvang van het spel werd vastgesteld) zit, anders wint Bob.

Bob wint als S aftelbaar is

Baker heeft een strategie gevonden die Bob kan toepassen waarmee hij het spel zeker wint, mits S aftelbaar is. Die strategie is als volgt. Zoals we eerder opmerkten, kun je de elementen van een aftelbare verzameling op een rij zetten. Stel dat S aftelbaar is, dan maakt Bob een lijst van alle elementen uit die verzameling: s1, s2, s3, … Bob moet zijn getallen op zo’n manier kiezen dat hij zeker weet dat de getallen van Alice nooit kunnen convergeren naar een getal uit die lijst van getallen waaruit S bestaat.

Hij doet dat als volgt. Als Alice haar eerste getal ( a1) heeft gekozen, vergelijkt hij a1 met s1. Indien s1 groter is dan a1, kiest Bob het getal s1. Als s1 kleiner dan of gelijk aan a1 is, kiest hij willekeurig een getal dat groter is dan a1. In het algemeen: bij de n-de beurt van Bob kiest hij bn = sn indien dat volgens de spelregels is toegestaan, en anders kiest hij willekeurig een getal bn > an. Voor elke waarde van n geldt dat sn ≤ an of sn ≥ bn. Omdat an < α < bn voor elke waarde van n, kunnen we concluderen dat α niet in de verzameling S zit.

Baker merkt vervolgens op dat indien voor S het gehele interval [0, 1] wordt gekozen, Bob vanzelfsprekend nooit kan winnen. Omdat we net hebben vastgesteld dat Bob altijd kan winnen indien S aftelbaar is, kan het interval [0, 1] niet aftelbaar zijn. Omdat het interval [0, 1] een deelverzameling is van de verzameling van álle reële getallen, die in de wiskunde met R wordt genoteerd, is R vanzelfsprekend eveneens overaftelbaar.

Speltheorie en getaltheorie

Baker bewijst niets meer dan Cantor, maar toch kan zijn bewijs worden gezien als een waardevolle aanvulling in de wiskunde. Zijn benadering is geheel anders dan die van Cantor. Baker gebruikt de speltheorie voor een stelling uit de getaltheorie: een verrassende combinatie.

Zie ook:

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 21 februari 2008

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.