Hoe construeer ik cantor's diagonaal?

[EvilBro]

Het ziet er naar uit dat landheha deze richting op wil

Dat denk ik niet... ik denk dat we te maken hebben met iemand die Cantor's redenering probeert te doorgronden.

[317070]

In de geschetste volgorde zie ik helaas dat ik er niet in slaag om die diagonaal door de hele verzameling heen te maken. Ik blijf zoals gezegd prematuur steken.

Maar waarom wil je een diagonaal door je verzameling maken? Je maakt normaal gezien een diagonaal door de aftelling van je verzameling. Dat is niet hetzelfde...

Ik wil dus graag een algoritme zien dat wel in staat is om in de door mij gekozen volgorde de diagonaal op de een-of-andere manier tot een goed einde te brengen.

Bedankt 317070, maar mijn vraag spitst zich inderdaad toe op het ALLE.

Wat is je vraag nu? ](*,) Om eerlijk te zijn begrijp ik het niet meer. Wil je het bewijs dat je een diagonaalgetal kunt construeren voor alle aftellingen van een bepaalde verzameling? Of geloof je niet dat 0,000000... niet in je aftelling voorkomt?

Dan maar door naar het volgende hoofdstuk over de reeele getallen zonder dit aspect helemaal te snappen...

Tenzij je een wiskunde- of natuurkundeopleiding volgt, is dit normaal gezien geen enkel probleem...

[landheha]

@EvilBro

sorry, ik dacht even dat je afhaakte op mijn eigenwijsheid.

@Bartjes

zoals EvilBro zegt. Ik ben die stromingen ook tegengekomen in mijn zoektocht naar antwoorden en ik herken wel wat. Het is mij echter volstrekt om het even waar ik uitkom.

@317070

Mijn veronderstelling was dat je voor het diagonale argument van Cantor echt een diagonaal door je hele oneindige verzameling T moet hebben wil je in staat zijn om aan het eind een geldige conclusie te kunnen trekken dat je iets nieuws creeert ten opzichte van T. Dat doet het diagonaal argument toch?.

Ik dacht een voorbeeld gevonden te hebben dat laat zien dat dat niet lukt.

Dan moet ik eens goed naar dat verschil tussen aftelling en verzameling gaan kijken, want aftelling staat inderdaad op dit moment niet op de radar. Misschien is dat mijn simpele denkfout dan wel.

Kun je dat verschil een beetje uitleggen (of verwijzen naar), wat is de crux voor dit bewijs?

edit

het helpt gewoon het best als die redenatie van mij punt voor punt wordt afgebroken of bevestigd.

- kan ik de verzameling zo maken?

- klopt het dat ik blijf steken in de volgorde die ik beschrijf?

- is dat dan bv. zo'n aftelling?

[Bartjes]

Zou de diagonaal door alle getallen van de als aftelbare lijst gepresenteerde verzameling getallen heen lopen, dan zou de verzameling inderdaad aftelbaar zijn. Door bij Cantors bewijs van overaftelbaarheid te eisen dat de diagonaal inderdaad alle getallen aandoet, maak je dus Cantors bewijsvoering van overaftelbaarheid onmogelijk.

De gestelde eis berust op een misvatting van de gebruikte bewijsvorm: namelijk het bewijs uit het ongerijmde. Bij een bewijs uit het ongerijmde neem je aan dat een bewering P waar is, juist om te kunnen bewijzen dat P niet waar is. Dit doe je door te laten zien dat als P waar zou zijn er een logische tegenstrijdigheid zou volgen. Omdat we ervan uitgaan dat in de wiskunde voor logische tegenstrijdigheden geen plaats is, moet de fout dan wel in de aanname zitten dat P waar was. Zo kan je in bepaalde gevallen bewijzen dat (in tegenstelling tot wat je aannam) P niet waar is.

Het is dus belangrijk te bedenken dat bij Cantors bewijs wordt aangenomen dat een zekere verzameling aftelbaar is, om vervolgens te bewijzen dat dat niet zo is. Je hoeft dus niet eerst te bewijzen dat de lijst aftelbaar is (oftewel dat de diagonaal alle getallen aandoet), alvorens met de rest van het bewijs verder te gaan. Sterker nog, dat kan niet eens. Als je zou kunnen aantonen dat een lijst aftelbaar is, hoeft (en kan als het goed is ook) niet meer te worden aangetoond dat de lijst overaftelbaar is.

Zat daar het probleem?

[EvilBro]

Hetgeen je wilt aantonen is dat er geen bijectie mogelijk is tussen de verzameling van oneindige reeksen enen en nullen en de natuurlijke getallen. Hiervoor ga je een bewijs uit het ongerijmde gebruiken. Veronderstel dat het wel mogelijk is om een lijst (je bijectie) te maken tussen de reeksen en de natuurlijke getallen. Voor elk natuurlijke getal is er dan een reeks die daarbij hoort. Voor elk natuurlijk getal k is er een reeks en hiervan is het k-de cijfer 0 of 1. Je kunt nu een reeks maken die op de k-de positie qua cijfer verschilt van de reeks die geassocieerd is met het k-de natuurlijke getal. Deze reeks is overduidelijk een oneindige reeks van enen en nullen en het moet dus op de lijst staan. Er is echter geen positie waar deze reeks kan staan. Als deze immers op de k-de plek op de lijst zou staan dan verschilt het k-de cijfer. De veronderstelling dat het mogelijk is om een lijst te maken met daarop alle reeksen leidt tot een tegenstrijdigheid. Het is dus niet mogelijk om de bijectie te maken. Je komt tot deze conclusie zonder dat je een specifieke lijst maakt. Slechts de veronderstelling dat zo'n lijst bestaat is genoeg.

Stel nu dat je naar een specifieke lijst kijkt, bijvoorbeeld de lijst die je voorstelde. Je weet van deze lijst dat voor de k-de reeks op de lijst het k-de cijfer een 1 is. De reeks met alleen nullen kan dus niet op deze lijst staan. Je blijft dus niet halverwege steken of zo, je weet gewoon met zekerheid dat er een reeks is die niet op de lijst staat. Hiermee heb je dus bewezen dat deze lijst niet alle reeksen bevat. Dit bewijst verder helemaal niks. Het is het gegeven dat elke mogelijke lijst tot een tegenstrijdigheid leidt wat je vertelt dat het niet mogelijk is om een lijst te maken van de reeksen.

[landheha]

(sorry voor de verstreken tijd, maar ik moet ook nog een beetje werken tussendoor)

@Bartjes

Dat is een puntje om over na te denken, maar dat moet ik even laten bezinken. In eerste instantie zou ik zeggen dat je 1e alinea in tegenspraak is met wat over het diagonaal argument wordt gezegd. Ergens hangt er ook iets in mijn geheugen dat ik ooit ergens gelezen heb dat Wittgenstein had gesuggereerd dat de diagonaal niet goed was, maar dat Russell had volgehouden dat je die wel degelijk kon construeren. Vandaar misschien mijn focus op "diagonaal".

Zie ook mijn antwoord aan EvilBro hieronder.

@EvilBro

"Het is het gegeven dat elke mogelijke lijst tot een tegenstrijdigheid leidt"

Elke mogelijke lijst leidt tot iets nieuws, een nieuw element, dat is toch geen tegenstrijdigheid (edit: aangezien het uitgangspunt niet alle combinaties bevatte)?

" wat je vertelt dat het niet mogelijk is om een lijst te maken van de reeksen. "

Uh, als ik nu alle nieuwe elementen van al die oneindige reeksen in een lijst ga stoppen, dan ben ik toch gewoon weer de totale verzameling T aan het samenstellen?

Het diagonale argument doet echt een uitspraak over de totale verzameling T.

Die laatste stap, die tegenspraak dat er iets nieuws wordt gemaakt tov T, die zie ik niet nog gebeuren.

[EvilBro]

"Het is het gegeven dat elke mogelijke lijst tot een tegenstrijdigheid leidt"

Elke mogelijke lijst leidt tot iets nieuws, een nieuw element, dat is toch geen tegenstrijdigheid?

Je veronderstelt dat de lijst compleet is. Dat is je uitgangspunt. Een complete lijst bevat alle elementen. Dit blijkt niet zo te zijn, want je kunt een element definieren dat niet op de lijst kan staan maar er wel op zou moeten staan. Je veronderstelling kan dus niet juist zijn. Dat noem ik een tegenstrijdigheid.

Die laatste stap, die tegenspraak dat er iets nieuws wordt gemaakt tov T, die zie ik niet nog gebeuren.

Veronderstel dat er een lijst is die de volledige verzameling T in een bepaalde volgorde zet. Ik definieer nu een reeks waarvan het k-de cijfer verschilt van van het k-de cijfer van de k-de reeks op de lijst. Dit legt mijn nieuwe reeks eenduidig vast. Ben je het eens dat deze nieuwe reeks in de verzameling T moet zitten? Zo nee, waarom niet? Zo ja, waar staat deze reeks dan in de volgorde?

[Bartjes]

@ landheha

Je zou eerst met een eenvoudig bewijs uit het ongerijmde kunnen oefenen. Zie:

http://nl.wikipedia.org/wiki/Bewijs_dat_wo..._irrationaal_is

Als je dat door hebt (en als een geldige bewijsmethode accepteert), kan je dan weer bekijken of Cantors bewijs nu wel begrijpelijk is.

[landheha]

@EvilBro

"Veronderstel dat er een lijst is die de volledige verzameling T in een bepaalde volgorde zet. Ik definieer nu een reeks waarvan het k-de cijfer verschilt van van het k-de cijfer van de k-de reeks op de lijst. Dit legt mijn nieuwe reeks eenduidig vast. Ben je het eens dat deze nieuwe reeks in de verzameling T moet zitten? Zo nee, waarom niet? Zo ja, waar staat deze reeks dan in de volgorde?"

Dan zijn we toch weer gewoon terug bij het uitgangspunt?

De nieuwe reeks zit altijd in verzameling T (per definitie). Geen probleem.

Ik stel nu weer, uitgaande van mijn voorbeeld, dat jouw nieuwe reeks alleen maar nieuw is tov verzameling A. Aangezien A veel kleiner is dan T kom ik op deze manier niet tot de gewenste conclusie dat de nieuwe reeks tevens niet in T zit.

Je neemt aan dat alle combinaties er in zitten, dat doe ik ook, maar op het moment dat je constateert dat dit niet het geval is, zoals ik in mijn voorbeeld denk te zien, dan kun je toch niet meer gewoon volharden in je oorspronkelijke opzet?

[EvilBro]

Ik stel nu weer, uitgaande van mijn voorbeeld, dat jouw nieuwe reeks alleen maar nieuw is tov verzameling A.

En dat blijft onzin. Verzameling A moet gelijk zijn aan verzameling T want dat was het uitgangspunt: een lijst met daarop alle reeksen uit de verzameling T.

..., maar op het moment dat je constateert dat dit niet het geval is, zoals ik in mijn voorbeeld denk te zien, dan kun je toch niet meer gewoon volharden in je oorspronkelijke opzet?

Snap je eigenlijk wel wat een bewijs uit het ongerijmde is?