Hoe construeer ik cantor's diagonaal?

[landheha]

Hallo,

ik heb een probleem met het construeren van de diagonaal in Cantor's diagonale argument.

Het diagonale algoritme is makkelijk zat

linksboven beginnen

stapje horizontaal, stapje verticaal, tik, stapje horizontaal, stapje verticaal, tik, etc. etc..

Het is ook totaal onafhankelijk van de eigenlijke volgorde van de data.

Ik kies om te beginnen een volgorde die makkelijk laat zien waar de diagonaal loopt. Ik begin met allemaal elementen die bestaan uit allemaal nullen met 1 enkel 1-tje precies op de plaats van de diagonaal.

1,0,0,0,0,0,0,0,...

0,1,0,0,0,0,0,0,...

0,0,1,0,0,0,0,0,...

0,0,0,1,0,0,0,0,...

0,0,0,0,1,0,0,0,...

0,0,0,0,0,1,0,0,...

...

Je ziet het gebeuren, ik heb mijn oneindige diagonaal al te pakken.

Zowel vertikaal als horizontaal lopen de waarden netjes gelijkop naar het oneindige.

Als ik kijk naar de data zie ik echter dat ik niet door de hele verzameling aan het lopen ben. Er zijn vele mogelijke waarden die ik op deze manier nooit ga bereiken.

Daar het diagonale mechanisme onafhankelijk is van de data kan ik alleen maar bedenken dat dit altijd gebeurt, alleen dan minder zichtbaar.

Op deze manier kom ik dus nooit tot een diagonaal die door de hele verzameling heenloopt.

Kan iemand mij uitleggen welke denkfout(en) ik maak.

Een beetje op de rails zetten, zodat ik de diagonaal wel goed krijg?

dank

[317070]

Een beetje op de rails zetten, zodat ik de diagonaal wel goed krijg?

Het idee is dat je eerst een verzameling getallen moet hebben die aftelbaar zou zijn (hypothese).

Aangezien de verzameling aftelbaar is, kun je de verzameling aftellen (duh) en dus de getallen op een volgorde plaatsen.

Nu construeren we een getal n die WEL in de verzameling zit, maar uit constructie NIET in de verzameling zit. (tegenspraak, ergo: veronderstelling is verkeerd, de verzameling is niet aftelbaar)

Dit kun je doen bij de reele getallen bv:

stel dat je aftelling er zo uitziet:

0,1234...

0,2345...

0,3456...

...

Dan kan ik een getal n construeren die wel in de verzameling van de reele getallen zit, en niet in je aftelling: bijvoorbeeld:

0,2222...

WANT

0,2222... =/= 0,1234...

0,2222... =/= 0,2345...

0,2222... =/= 0,3456

ENZOVOORT:

Dus dit getal zit niet in je aftelling, want het is niet gelijk aan alle getallen van je aftelling. Het is nochtans wel een reeel getal. Dus welke aftelling je ook bedenkt, ik kan je een getal geven die reeel is en niet in je aftelling zit. De verzameling van de reele getallen is dus niet aftelbaar.

QED

[EvilBro]

De redenering zegt iets over de verzameling die op je lijst staat. Als die verzameling niet overeenkomt met de verzameling waar je daadwerkelijk een uitspraak over wilt doen dan heb je je lijst niet goed gemaakt.

[landheha]

@317070

dank je, maar dit is wat er volgt nadat je de diagonaal geconstrueerd hebt van linksboven naar rechtsonder.

Daar heb ik (nog) geen probleem mee. Ik krijg die diagonaal niet zoals hij zou moeten zijn. Als je niet de hele verzameling hebt geraakt lijkt het me lastig om aan het eind zoals jij uitlegt te kunnen concluderen dat je echt iets nieuws hebt gemaakt.

[landheha]

@EvilBro

deze opmerking begrijp ik niet helemaal.

Bij mijn weten ga ik uit van dezelfde verzameling als in het originele argument: een oneindig aantal elementen onder elkaar waar elk element bestaat uit een oneindige aantal nullen en enen. De verzameling kun je zien als "vierkant". Alle mogelijke combinaties van nullen en enen komen voor.

Ik kies er alleen voor om een bepaalde volgorde in de elementen aan te brengen om een gevoel te krijgen hoe het algoritme zich gedraagt.

Hoe zegt dit dat ik mijn lijst verkeerd heb gemaakt?

[EvilBro]

Elk element in de door jou gemaakte lijst bevat maar een 1. De verzameling op de lijst is dus niet de verzameling die je aan het bekijken bent.

[317070]

@317070

dank je, maar dit is wat er volgt nadat je de diagonaal geconstrueerd hebt van linksboven naar rechtsonder.

Daar heb ik (nog) geen probleem mee. Ik krijg die diagonaal niet zoals hij zou moeten zijn. Als je niet de hele verzameling hebt geraakt lijkt het me lastig om aan het eind zoals jij uitlegt te kunnen concluderen dat je echt iets nieuws hebt gemaakt.

Dat is net het punt: noem mij een willekeurig getal in de aftelling, en ik geef je de decimaal vanaf waar mijn geconstrueerd getal ZEKER verschilt met jouw getal. Dus voor elk willekeurig getal dat je geeft in je aftelling, kan ik aantonen dat mijn getal er niet gelijk aan is, maar toch zit mijn getal in je verzameling. Hieruit kun je concluderen dat mijn getal niet in je aftelling zit, maar wel in je verzameling, en dus loopt je aftelling niet alle getallen in de verzameling af.

Aangezien je dit normaal gezien aantoont voor alle mogelijke aftellingen, is je verzameling niet-aftelbaar.

Maar die constructie is praktisch gezien niet mogelijk om te doen, en van iedere aftelling kun je (overaftelbaar!) oneindig veel diagonaalgetallen maken die er niet in zitten. Is dit laatste het probleem dat je had?

Misschien zouden we je wat beter kunnen helpen als je zegt welke de verzameling is waarvan je wil aantonen dat ze niet aftelbaar is, en wat de aftelling is die je gebruikt in je voorbeeld?

[landheha]

@EvilBro

Dat is precies mijn punt.

De diagonale stapjes zijn onafhankelijk van de data, maar ik kan een volgorde maken die aantoont dat ik niet in staat ben om op die manier door de totale verzameling van alle combinaties heen te komen. Ik lijk zeg maar "vast te lopen in een lokale oneindigheid waar ik niet meer uit kom met diagonale stapjes".

Noem de totale verzameling T en de verzameling die er in mijn voorbeeldje hierboven uit komt rollen A.

Ik hoop dat je het met me eens bent dat zowel T als A dezelfde "oneindige diagonaal" in zich dragen.

De elementen van deze verzamelingen zijn 1-op-1 met elkaar te matchen.

Toch is A niet gelijk aan T.

Als ik de diagonaal van A ga pakken krijg ik een element met een oneindig aantal 1-tjes.

Die zit inderdaad in T (per definitie) en hij zit inderdaad niet in A (simpel te zien). Aangezien A en T niet gelijk zijn heeft dit volgens mij verder geen speciale betekenis.

[EvilBro]

De diagonale stapjes zijn onafhankelijk van de data, maar ik kan een volgorde maken die aantoont dat ik niet in staat ben om op die manier door de totale verzameling van alle combinaties heen te komen.

Maar dat is niet een zinnige methode. Het vertelt je niks. Je moet aantonen dat er altijd een element mist ongeacht welke lijst je ook maakt. Dat zegt namelijk wel iets.

[landheha]

@317070

In principe gebruik ik dezelfde situatie die direct onder de inhoudsopgave wordt genoemd in het artikel van de wikipedia waarnaar ik hier helemaal boven verwijs. De totale set van alle combinaties van nullen en enen. Ik heb alleen de volgorde zoals geschetst aangepast.Dat zou toch zo aftelbaar moeten zijn als een standaardvoorbeeld maar kan zijn.

Ik moet nog even over je opmerking nadenken, maar mijn begin ligt linksboven.

[landheha]

@EvilBro

Het gaat er niet om of het een zinnige methode is.

First things first

Wil dit argument werken, dan moet je in staat zijn om een diagonaal door de hele verzameling heen te vormen.

Toch?

Ik ga alleen die stapjes maken en dat vertelt me op zich inderdaad niets.

Alleen dat ik de diagonaal kan maken.

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.

Aangezien de diagonale stapjes onafhankelijk zijn van de volgorde van de elementen kan ik alleen maar bedenken dat het dus op deze manier met geen enkele gekozen volgorde binnen de verzameling gaat lukken.

Met de "lokale diagonaal" die ik nu zie hoef ik niet te beginnen aan

From this it follows that the set T, consisting of all infinite sequences of zeros and ones, cannot be put into a denumerable list s1, s2, s3, ... Otherwise, it would be possible by the above process to construct a sequence s0 which would both be in T (because it is a sequence of 0s and 1s which is by the definition of T in T) and at the same time not in T (because we can deliberately construct it not to be in the list). T, containing all such sequences, must contain s0, which is just such a sequence. But since s0 does not appear anywhere on the list, T cannot contain s0.

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.

Ik zie nog niet in hoe die "aftelbaarheid" waar 317070 het over heeft daar bij gaat helpen.

[317070]

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.

Voor jouw diagonaal:

0,10000...

0,01000...

0,00100...

0,00010...

...

Vind je het getal n = 0,0000000....

Dat getal zit niet in je aftelling, maar zit wel in de verzameling, aangezien hij enkel bestaat uit 1'en en 0'en.

Maar an sich heeft weinig zin. Je moet bewijzen dat voor ALLE aftellingen een getal n bestaat, die niet in die aftelling zit, om te bewijzen dat alle getallen die bestaan uit aftelbaar veel 1'en of 0'en, overaftelbaar in aantal zijn.

[landheha]

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

Excuus dat ik het niet zo helder uit kon leggen. Ik dacht even met EvilBro de goede kant op te gaan, maar zijn laatste antwoord voorspelt helaas weinig goeds.

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

[EvilBro]

Ik dacht even met EvilBro de goede kant op te gaan, maar zijn laatste antwoord voorspelt helaas weinig goeds.

?

[Bartjes]

Het ziet er naar uit dat landheha deze richting op wil:

http://plus.maths.org/issue49/features/wilson/index.html

http://en.wikipedia.org/wiki/Ultrafinitism