b'\n_START_ARTICLE_\nDiagonaalbewijs van Cantor\n_START_PARAGRAPH_\nHet diagonaalbewijs van Cantor (ook: de diagonaalmethode van Cantor) is een bewijs, afkomstig van de wiskundige Georg Cantor, dat de kardinaliteit van de verzameling van re\xc3\xable getallen groter is dan die van de verzameling van natuurlijke getallen. De verzameling natuurlijke getallen is aftelbaar oneindig, kortweg aftelbaar genoemd. Als een oneindige verzameling  niet een-eenduidig op de natuurlijke getallen kan worden afgebeeld, wordt  overaftelbaar genoemd. Met zijn diagonaalmethode laat Cantor zien dat er geen een-eenduidige correspondentie is tussen de natuurlijke getallen en de re\xc3\xable getallen. Cantor publiceerde dit bewijs in 1891, maar had de overaftelbaarheid van de re\xc3\xable getallen al eerder bewezen.\n_START_SECTION_\nHet diagonaalbewijs\n_START_PARAGRAPH_\nHebben misschien alle oneindige verzamelingen hetzelfde formaat? Dit blijkt niet zo te zijn. En daar komt het diagonaalbewijs om de hoek kijken: er zijn meer re\xc3\xable getallen tussen 0 en 1 dan er natuurlijke getallen zijn. Dit bewijs gebruikt reductio ad absurdum. We nemen daarom aan dat er een bijectie (dat wil zeggen een een-op-eenafbeelding) van de natuurlijke getallen naar de re\xc3\xable getallen bestaat._NEWLINE_Zo\'n afbeelding ziet er bijvoorbeeld zo uit:_NEWLINE__NEWLINE_1 \xe2\x86\x94 0,23958239052222..._NEWLINE_2 \xe2\x86\x94 0,14345678901234..._NEWLINE_3 \xe2\x86\x94 0,00000000000120..._NEWLINE_4 \xe2\x86\x94 0,50000000000000..._NEWLINE_5 \xe2\x86\x94 0,14159265358979..._NEWLINE_6 \xe2\x86\x94 0,23562877077729..._NEWLINE_enzovoort._NEWLINE_De lijst is in twee richtingen oneindig lang. Nu nemen we van het eerste getal het eerste cijfer achter de komma. Van het tweede getal nemen we het tweede cijfer achter de komma, enzovoort. Deze cijfers zetten we achter elkaar, zodat we een nieuw getal krijgen, in het voorbeeld: 0,240098.... Het getal vormt als het ware de diagonaal van de tabel. Elk cijfer in dit getal veranderen we in een willekeurig ander cijfer (anders dan 0 of 9), bijvoorbeeld door het getal in 4 te veranderen als het anders is dan 4, en in 5 als het gelijk is aan 4. Het nieuwe getal  dat we nu hebben gemaakt (in het voorbeeld: 0,454444...) kan niet in de lijst staan. Immers, als je uit de lijst het getal  haalt, komt het -de cijfer van dat getal niet meer overeen met het -de cijfer uit . Omdat er altijd een nieuwe  gemaakt kan worden, zit er tussen 0 en 1 een overaftelbaar aantal re\xc3\xable getallen.\n_START_SECTION_\nUitbreiding\n_START_PARAGRAPH_\nBij uitbreiding kan het diagonaalbewijs ook gebruikt worden om te bewijzen dat voor elke verzameling , diens machtsverzameling (de verzameling van deelverzamelingen van ), genoteerd , een grotere kardinaliteit heeft. Stel dat er een afbeelding  bestaat zodanig dat elk element van  in het beeld van de afbeelding ligt. Vorm nu de deelverzameling . Neem nu de  zodanig dat . Zit  in ? Als , dan , dus . Maar als , dan , dus  Dit is onmogelijk, dus er is niet een dergelijke afbeelding ._NEWLINE_Door te beginnen met de natuurlijke getallen en het diagonaalargument oneindig vaak toe te passen op een volgende machtsverzameling, kan een oneindig aantal oneindige kardinaliteiten worden verkregen.\n_START_SECTION_\nParadox\n_START_PARAGRAPH_\nDeze laatstgenoemde versie van het diagonaalbewijs leverde een paradox: Zij  de verzameling van alle verzamelingen.  is de verzameling van alle verzamelingen van verzamelingen, en is dus een deelverzameling van , en dus kleiner of even groot, maar niet groter. Maar bovenstaand bewijs toont aan dat het groter moet zijn. Hier was dus duidelijk iets mis._NEWLINE_Een vergelijkbaar probleem werd geleverd door de "verzameling van alle verzamelingen die zichzelf niet bevatten". Bevat deze verzameling zichzelf of niet? Zie Russellparadox voor een uitgebreidere behandeling van deze paradoxen._NEWLINE_Op basis van deze paradoxen werd de verzamelingenleer opnieuw gedefinieerd: Tot dan toe had men als axioma aangenomen dat voor elke eigenschap  de verzameling van alle dingen met eigenschap  bestond. Dit werd veranderd tot het axioma dat gegeven een verzameling  en een eigenschap , de verzameling van die elementen van  die eigenschap  hebben, bestaat.'