Diagonaalbewijs van cantor

[Rene_BE]

Dag dames, heren ook,

In Wikipedia kun je lezen over het diagonaalbewijs van Cantor. Ik begrijp het niet; misschien kan en wil iemand het mij eens uitleggen?

Het heeft allemaal te maken met de kardinaliteit van oneindige verzamelingen. Een soort maat voor de oneindigheid, als ik het een beetje goed begrijp.

Bon. Je kunt laten zien dat de verzameling der natuurlijke getallen "even oneindig is" als, pak 'em beet, de verzameling der rationale getallen. In voornoemd Wikipedia-artikel doet men dat zo:

Gaan we naar op het eerste gezicht grotere verzamelingen, dan blijkt dat ook de rationale getallen dezelfde cardinaliteit hebben als de natuurlijke getallen. Het gaat hier om de volgende getallen:

1 / 1 1 / 2 1 / 3 ...

2 / 1 2 / 2 2 / 3 ...

3 / 1 3 / 2 3 / 3 ...

... ... ...

We kunnen ze niet aftellen door met de eerste kolom te beginnen, want dan komen we nooit aan de tweede kolom toe. Het kan echter wel door diagonaal te werken: eerst de breuken waarvan teller en noemer samen 2 zijn, daarna de breuken met som 3 enzovoort. Dit levert"

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

Breuken 1 / 1 1 / 2 2 / 1 1 / 3 2 / 2 3 / 1 1 / 4 2 / 3 3 / 2 4 / 1 1 / 5 2 / 4 ...

Er zijn dus niet meer breuken van natuurlijke getallen dan natuurlijke getallen, en dus ook niet meer rationale getallen.

Vervolgens wordt met het diagonaalbewijs aangetoond dat N en R een verschillende karidnaliteit hebben:

Hebben misschien alle oneindige verzamelingen hetzelfde formaat? Dit blijkt niet zo te zijn. En daar komt het diagonaalbewijs om de hoek: Er zijn meer reële getallen tussen 0 en 1 dan er natuurlijke getallen zijn. Dit bewijs gebruikt reductio ad absurdum. We nemen daarom aan dat er een bijectie, dit wil zeggen een 1-op-1 afbeelding van de natuurlijke getallen naar de reële getallen bestaat.

Zo'n afbeelding ziet er bijvoorbeeld zo uit:

1 - 0,23958239052222...

2 - 0,12345678901234...

3 - 0,00000000000120...

4 - 0,50000000000000...

5 - 0,14159265358979...

6 - 0,23562877077729...

enzovoort.

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 nieuwe getal krijgen, in het voorbeeld: 0,220098.... Elk cijfer in dit getal veranderen we in een willekeurig ander cijfer, bijvoorbeeld door er 1 bij op te tellen (9 wordt dan 0). Het nieuwe getal 0,331109.... dat we nu hebben gemaakt, kan nooit in de lijst staan; immers als je uit de lijst het getal n haalt dan komt het n-de cijfer van dat getal niet meer overeen met het n-de cijfer uit m. Omdat er altijd een nieuwe m gemaakt kan worden, zit er tussen 0 en 1 een overaftelbaar aantal reële getallen.

En hier is men mij kwijt.

In de eerste plaats begrijp ik niet waarom bovenstaande diagonaalbewijs valide is.

Maar bovendien snap ik niet waarom niet gewoon dezelfde truuk als in het koppelen van N aan Q wordt gebruikt. Daar werd namelijk gezegd: weet je wat? We nemen gewoon eerst alle breuken waarvan de teller en noemer samen opgeteld 2 zijn, vervolgens die waar ze opgeteld 3 zijn, dan 4, enzovoort.

Waarom kun je, analoog daaraan, niet zeggen: ik neem eerst (van de getallen tussen 0 en 1, want daar gaat het hier even om) eerst alle getallen met 1 cijfer achter de komma (en de rest 0), dan die met 2 cijfers achter de komma (en de rest 0), enzovoort. Dus:

1 .. 0,1000000000000

2 .. 0,2000000000000, enz, tot

9 .. 0,9000000000000 en dan

10 .. 0,0100000000000

11 .. 0,0200000000000,

Probleem is dan wel dat je sommige getallen uit R meer keer tegenkomt, dus misschien maak ik daar een denkfout?

Groet,

René.

[Klintersaas]

Dat je het diagonaalbewijs van Cantor niet zo goed begrijpt is zeker geen schande. Massa's prominente wiskundigen hebben lange tijd de onjuistheid van het bewijs proberen aan te tonen, maar niemand is daar ooit in geslaagd. Ik zal het bewijs even helemaal opnieuw opbouwen in - dat hoop ik althans - begrijpelijker taal.

Het diagonaalbewijs van Cantor bewijst dat er meer reële getallen zijn dan natuurlijke getallen. Dat klinkt zeer vreemd, aangezien beide getalverzamelingen uit oneindig veel elementen bestaan. Blijkbaar zijn er dus gradaties in oneindigheid, die aangegeven worden met de zgn. kardinaalgetallen.

Hoe bewees Cantor nu dat er meer reële getallen dan natuurlijke getallen zijn? Wel, hij bewees dit uit het ongerijmde. Dit betekent zoveel als: we nemen aan dat er evenveel natuurlijke getallen als reële getallen bestaan. Vervolgens zien we dat deze aanname leidt tot een contradictie en besluiten we dat deze aanname vals is. Zodoende zijn er dus meer reële getallen dan natuurlijke getallen.

Om het ons gemakkelijk te maken, zullen we bewijzen dat er zelfs tussen 0 en 1 meer reële getallen zitten dan er natuurlijke getallen zijn. Als dat geldt, dan hoeft het niet gezegd te worden dat, wanneer we alle reële getallen bekijken, het er sowieso meer zullen zijn. Dus, hier komt het bewijs.

Stelling: Er zijn meer reële getallen dan natuurlijke getallen.

Bewijs: Stel dat we een lijst hebben die elk natuurlijk getal aan een reëel getal koppelt. We zullen een getal construeren dat niet in die lijst voorkomt en zo aantonen dat zo'n lijst dus niet kan bestaan.

Beschouw dus de lijst hieronder:

\(\begin{tabular}{l | l}\nn & \rr \\\hline1 & 0,2569836589\ldots \\2 & 0,3333333333\ldots \\3 & 0,1010010001\ldots \\4 & 0,2272272272\ldots \\5 & 0,3141589756\ldots \\6 & 0,1689593154\ldots \\\vdots & \vdots\end{tabular}\)

Dit zou dus een lijst moeten zijn die de natuurlijke getallen en de reële getallen één op één op elkaar afbeeldt. We construeren nu dus een getal dat niet op die lijst staat. Dat doen we als volgt:

• We nemen van het eerste getal het eerste cijfer achter de komma;
• We nemen van het tweede getal het tweede cijfer achter de komma;
• We nemen van het derde getal het eerste cijfer achter de komma;
• ...
• We nemen van het n^de getal het n^de cijfer achter de komma;

We verkrijgen nu het volgend getal:

\(0,231259\ldots\)

Nu verhogen we elk cijfer achter de komma met 1 (9 wordt 0):

\(0,342360\ldots\)

Dit getal kan onmogelijk in de lijst staan, want als dit wel het geval was, dan zou het op de n^de plaats achter de komma met zichzelf verschillen en een getal dat met zichzelf verschilt is onmogelijk. Onze aanname dat een lijst zoals hierboven bestaat leidt dus tot een onmogelijkheid. Er bestaat dus geen één-op-éénrelatie tussen de natuurlijke en de reële getallen.

Duidelijk? Indien niet, aarzel niet om door te vragen.

[Klintersaas]

Ik bedacht net dat de meeste mensen problemen hebben met het volgende stukje:

Dit getal kan onmogelijk in de lijst staan, want als dit wel het geval was, dan zou het op de n^de plaats achter de komma met zichzelf verschillen en een getal dat met zichzelf verschilt is onmogelijk. Onze aanname dat een lijst zoals hierboven bestaat leidt dus tot een onmogelijkheid. Er bestaat dus geen één-op-éénrelatie tussen de natuurlijke en de reële getallen.

Daarom een voorbeeld:

Stel dat het getal wel in de lijst stond op laten we zeggen de tiende plaats. Wanneer we dan het nieuwe getal construeren nemen we het eerste cijfer achter de komma van het eerste getal enzovoort, dus ook het tiende cijfer achter de komma van het tiende getal. Tot daar is er nog geen probleem. Maar wanneer we elk getal achter de komma met 1 verhogen (en dus ook het tiende cijfer achter de komma), staat het getal niet meer in de lijst omdat er minstens 1 cijfer na de komma (in dit geval zeker het tiende) veranderd is.

[TD]

Om goed te begrijpen wat er gaande is, lijkt het me ook belangrijk om goed te snappen wat we precies bedoelen met "meer getallen", want dat is (nog) geen goed gedefinieerd begrip. Ik zou de stelling dus ook zeker niet omschrijven als "Er zijn meer reële getallen dan natuurlijke getallen.", want wat is meer?

Intuïtief zijn er ook "meer" gehele getallen, want elk natuurlijk getal is een geheel getal maar er bestaan niet-natuurlijke gehele getallen. Toch schijnen deze verzamelingen "even groot" te zijn, er is dus nood aan een preciezere karakterisering van die "grootte".

Dit geeft inderdaad aanleiding tot kardinaalgetallen en het is belangrijk dat je hiervoor begrijpt wat een bijectie (injectie, surjectie) is. We zeggen dat twee verzamelingen A en B hetzelfde kardinaalgetal hebben, als er een bijectie bestaat tussen A en B. In het diagonaalbewijs, toon je dus (inderaad uit het ongerijmde) aan dat zo'n bijectie niet kan bestaan.

[Klintersaas]

Om goed te begrijpen wat er gaande is, lijkt het me ook belangrijk om goed te snappen wat we precies bedoelen met "meer getallen", want dat is (nog) geen goed gedefinieerd begrip. Ik zou de stelling dus ook zeker niet omschrijven als "Er zijn meer reële getallen dan natuurlijke getallen.", want wat is meer?

Dat weet ik, maar ik wilde het (nog) niet over bijecties hebben vooraleer Rene_BE (intuïtief) goed weg is met het bewijs op zich. Ik heb echter geprobeerd om het idee van bijectie al in mijn posts te gebruiken door te spreken over een één-op-éénrelatie.

[TD]

Het was ook geen verwijt, maar een aanvulling. Het is mijn ervaring dat de problemen soms veroorzaakt worden door het net onvoldoende precies te formuleren; dit is immers erg abstract en dan kan het 'gevaarlijk' zijn om in eerder vage begrippen zoals "meer elementen" te spreken. Dat is misschien intuïtiever, maar het is net het intuïtieve begrip van grootte dat bij een oneindig aantal elementen niet meer echt werkt - vandaar de nood aan een definitie van "grootte" (en dus bijecties).

[Klintersaas]

Het was ook geen verwijt, maar een aanvulling. Het is mijn ervaring dat de problemen soms veroorzaakt worden door het net onvoldoende precies te formuleren; dit is immers erg abstract en dan kan het 'gevaarlijk' zijn om in eerder vage begrippen zoals "meer elementen" te spreken.

Dat ben ik zeker met je eens. In mijn eigen oefeningen/bewijzen ben ik steeds zo precies mogelijk (volgens sommige leerkrachten soms zelfs ietsje té precies; juist daarom wil ik wanneer ik iemand iets uitleg wat minder precies zijn, omdat ik besef dat sommige mensen moeite hebben met mijn exactheid, zeker als ze iets niet goed begrijpen).

[Rhel]

Ik begrijp het diagonaalbewijs van Cantor. Echter gaat hij uit van de veronderstelling dat er een diagonaal is. Ik ben van mening dat hij zich hierin vergist heeft. Het klinkt misschien vreemd, maar wanneer je alle mogelijke getallen genoteerd hebt levert dit niet een vierkant op maar een rechthoek waarvan de hoogte groter is dan de breedte. In deze rechthoek kan de diagonaal van Cantor niet getrokken worden en daarmee ook niets bewezen worden.

Om te bewijzen dat het een rechthoek is en geen vierkant zal ik beginnen met alle mogelike getallen te noteren. Ik zal dit doen in het binaire stelsel, omdat dit minder grote matrixen opleverd. Het principe geldt voor alle talstelsels.

Ik begin met alle combinaties te maken met 1 bit:

0

1

Nu alle mogelijke combinaties met 2 bits:

00

01

10

11

U ziet: de matrix is alijd hoger dan dat hij breed is. In deze matrix is geen diagonaal van Cantor te trekken.

Ik ga nog even door: alle combinaties met 3 bits:

000

001

010

011

100

101

110

111

In feite is het zo dat het aantal regels zich verhoudt tot het aantal kolommen als volgt:

Aantal regels = 2 ^ aantal kolommen.

In het decimale stelsel is het:

Aantal regels = 10 ^ aantal kolommen.

Dezelfde redenering is toe te passen op de reele getallen.

[EvilBro]

Nee, want:

0.000000000000...

0.100000000000...

0.200000000000...

0.300000000000...

0.400000000000...

0.500000000000...

0.600000000000...

0.700000000000...

0.800000000000...

0.900000000000...

[Rhel]

Elke 0 die u toevoegd levert extra mogelijke combinaties op. In uw voorbeeld tel ik 12 nullen in de breedte. Dit houdt in dat het aantal combinaties, en dus het aantal regels, 10 ^ 12 is. Anders gezegd, wanneer alle mogelijke combinaties genoteerd worden met 12 cijfers achter de komma dan levert dat 1.000.000.000.000 regels op. Hierin kan geen bruikbare diagonaal getrokken worden.

[EvilBro]

Elke redenatie die je op eindige lijstjes toepast is niet relevant. Het gaat immers over oneindige lijstjes. De enige manier waarop er geen diagonaal is bij zo'n oneindig lijstje, is als er een getal is dat geen oneindige decimale representatie heeft. Zo'n getal bestaat niet. Er is dus een diagonaal.

[Rhel]

Ok. Als ik die redenatie volg dan bedoelt u dat een reëel getal altijd aangevuld kan worden met oneindig veel nullen. In Cantors bewijs gaat het erom dat er meer reële getallen zijn dan natuurlijke getallen. Maar volgens mij kun je altijd een uniek natuurlijk getal construeren adhv een reëel getal, simpelweg door alle cijfers achter de komma om te draaien.

0,100000... wordt dan ...000001

0,200000... wordt dan ...000002

.

.

0,000012... wordt dan ...210000

0,715631... wordt dan ...136517

met andere woorden: ongeacht welk reëel getal ook geconstrueerd wordt met de diagonaal van Cantor, het is altijd gekoppeld aan een uniek natuurlijk getal. (Dit werkt overigens beide kanten op. Van elk natuurlijk getal is op dezelfde manier een uniek reëel getal te construeren)

Conclusie: er zijn evenveel natuurlijke als reële getallen.

Zo niet, wat is er fout aan deze redenatie?

[EvilBro]

Maar volgens mij kun je altijd een uniek natuurlijk getal construeren adhv een reëel getal, simpelweg door alle cijfers achter de komma om te draaien.

Dit kan niet. Geen enkel natuurlijk getal heeft oneindig veel cijfers in zijn representatie. Het natuurlijke getal dat volgens jouw methode hoort bij \(\frac{1}{3}\), \(\pi - 3\) en \(\sqrt{2} - 1\) is er dus niet.

[Rhel]

Geen enkel natuurlijk getal heeft oneindig veel cijfers in zijn representatie.

Wat is het bewijs van die stelling? Waarom is 3333/ een ongeldig repeterend getal? Of waarom zijn ...395141 ...412414 ongeldige natuurlijke getallen?

[EvilBro]

Natuurlijke getallen kun je genereren door te beginnen bij 1 en er dan telkens 1 bij op te tellen (simpel gezegd). Als je mij een natuurlijk getal geeft dan kan ik een groter natuurlijk getal generen door er 1 bij op te tellen.

Stel dat er een natuurlijk getal bestaat dat het kleinste natuurlijke getal is met oneindig veel cijfers in zijn representatie. Omdat dit het kleinste getal is met oneindige veel cijfers moet het getal wat hiervoor ligt eindig veel cijfers hebben. Nu is er een probleem. Dit getal met eindig veel cijfers (laten we het aantal N noemen) kan bestaan uit alleen maar negens. Als je daar 1 bij optelt krijg je een getal met een 1 gevolgd door N nullen. Als het niet alleen bestaat uit N negens dan is het nieuwe getal een getal met N cijfers. In beide gevallen is het geen getal met oneindig veel cijfers. Dit is dus een contradictie.

De veronderstelling dat er een kleinste natuurlijk getal is met oneindig veel cijfers impliceert dat de voorganger van dit getal een getal is met eindig veel cijfers, maar die veronderstelling leidt tot dat het volgende getal ook eindig veel cijfers moet hebben, maar dat getal zou oneindig veel cijfers moeten hebben. De enige manier om dit op te lossen is dus met de conclusie dat zo'n kleinste getal met oneindig veel cijfers niet kan bestaan.

Natuurlijke getallen met oneindig veel cijfers in hun representatie bestaan niet.