Springen naar inhoud

Waarom is 2^omega aftelbaar?


  • Log in om te kunnen reageren

#1

VictorG

    VictorG


  • 0 - 25 berichten
  • 2 berichten
  • Gebruiker

Geplaatst op 29 juli 2009 - 20:41

Ik heb de laatste tijde wat zitten lezen over oneindige ordinaal- en kardinaalgetallen, maar ik ben nu ergens tegenaan gelopen dat ik niet helder krijg en wat ik denk ik moet begrijpen voordat ik me verder ga verdiepen.

Een verzameling S is aftelbaar als er een injectieve functie van S op de natuurlijke getallen is. Dat begrijp ik, en ik begrijp waarom verzamelingen met grootte ω, ω * 2, ω ^ 2 en ω ^ 3 aftelbaar zijn, en als kardinaalgetal dus allemaal ℵ0 hebben. Voor elke eindige n zie ik hoe je een functie kan construeren van de ordinalen tot aan ω ^ n op de natuurlijke getallen.

Wat ik ook begrijp is waarom 2 ^ ℵ0 de (kardinale) grootte van R is, en waarom deze niet aftelbaar is.

Waar het misgaat is wanneer we de limiet nemen van de rij ω^n en aankomen bij ω^ω. Alle literatuur die ik heb gezien zegt hier simpelweg dat ω^ω ook aftelbaar is, net zoals ε0, en nog veel verder. Het is schijnbaar heel gemakkelijk om dit in te zien, want geen van die boeken / internetpagina's die ik las nam de moeite dit nog verder uit te leggen.

Maar ik zie het niet. Welke functie is dan een injectie van de ordinalen tot en met ω^ω op N?

Laat ik het anders verwoorden. Ik neem aan dat 2 ^ ω =< ω ^ ω. Wat is nu het verschil tussen 2^ω en 2^ℵ0? Waarom is de eerste aftelbaar en de tweede overaftelbaar? Er zijn toch precies zoveel reŽle getallen als er mogelijkheden zijn om ω-maal een binaire keuze te maken? (Beeld R af op het eenheidslijnstuk, schrijf de reŽle getallen in binaire ontwikkeling, en elk getal in R correspondeert met precies ťťn reeks 0-en en 1-en.) En 2^ω is precies het aantal manieren om ω maal een binaire keuze te maken. Dus waarom is 2^ω nu niet overaftelbaar, en corresponderend met 2 ^ ℵ0?

Nog anders gezegd. ω^ω is het aantal manieren om ω maal een element uit N te kiezen (er zitten immers ω elementen in N). Stel dat we ťťn manier om dat te doen opschrijven als horizontaal achter elkaar de getallen die zijn gekozen; en dat we vervolgens al deze mogelijke manieren onder elkaar schrijven. Dan kunnen we op hetgeen we nu hebben gekregen toch precies het diagonaal-bewijs uitvoeren waarmee je laat zien dat R niet afgebeeld kan worden op N?

Ergens ga ik de mist in, maar ik weet niet waar. Veel dank voor wie mij kan helpen!

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

TD

    TD


  • >5k berichten
  • 24052 berichten
  • VIP

Geplaatst op 29 juli 2009 - 21:19

Het is misschien erg verwarrend, maar volgens mij ga je de mist in omdat je geen onderscheid maakt tussen machtsverheffing op ordinalen en op kardinalen, die operaties zijn namelijk niet gelijk (ze zijn anders gedefinieerd). Met andere woorden:

LaTeX

Tenminste, als we in het eerste geval een machtsverheffing van ordinalen bedoelen en in het tweede geval een machtsverheffing van kardinalen. Meestal maakt men dit onderscheid stilzwijgend op basis van de symbolen (omega voor een ordinaal, aleph0 voor het bijbehorende kardinaal).
"Malgré moi, l'infini me tourmente." (Alfred de Musset)

#3

*_gast_PeterPan_*

  • Gast

Geplaatst op 29 juli 2009 - 21:27

Ik kan je een exact bewijs geven, maar laten we het vooreerst proberen via overtuiging.
De rijen
LaTeX ,
LaTeX
LaTeX
LaTeX
LaTeX
zijn stuk voor stuk aftelbaar.
Maar dan is ook de verzameling van al deze getallen aftelbaar, want de getallen vormen een "matrix" van oneindig veel rijen en oneindig veel kolommen.
Nu kun je al deze getallen in ťťn lange rij opschrijven door de getallen diagonaalsgewijs te doorlopen, te beginnen bij het getal 0, dus:
LaTeX .
Ik ga hier de bijbehorende functie niet noemen. Ik weet dat die functie bestaan en dat het een flink gepuzzel is om hem op te schrijven.

Zo vinden we dus al doende de volgende aftelbare rijen:
LaTeX
Bij elk element LaTeX bijtellen geeft de daaropvolgende aftelbare rij
LaTeX
Het volgende element is LaTeX
Voeg nu de laatstgecreerde twee rijen samen tot 1 rij door afwisselend een element uit de ene rij en dan weer een element van de andere rij te nemen.
We krijgen dan de aftelbare rij, die ik voor het gemak even LaTeX noem.
Op deze rij volgt de rij LaTeX .
De vereniging van deze twee rijen wordt gevolgd door het element LaTeX .
Zo voortgaande krijgen we achtereenvolgens aftelbare rijen tot element LaTeX voor elke n.
Een vereniging van aftelbaar veel aftelbare verzamelingen is weer aftelbaar (diagonaaltruc).
Dus tot LaTeX zijn er aftelbaar veel ordinaalgetallen.

#4

VictorG

    VictorG


  • 0 - 25 berichten
  • 2 berichten
  • Gebruiker

Geplaatst op 29 juli 2009 - 21:59

Bedankt, dat helpt allebei. Door de post van PeterPan zie ik nu inderdaad hoe je een injectieve functie van <0, 1, ..., ω^ω> op N definieert. De opmerking van TD bracht mij na wat zoekwerk op een pagina over machtsverheffen van ordinaalgetallen, en daar las ik iets dat in feite ook een antwoord op mijn vraag was:

In general, any well ordered set B can be raised to the power of another well ordered set E, resulting in another well ordered set, the power B^E. Each element of B^E is a function from E to B such that only a finite number of elements of the domain E map to an element larger than the least element of the range B.


Mijn cursivering. Dat cursieve gedeelte is precies wat (a) ordinaal-machtsverheffen anders maakt dan kardinaal-machtsverheffen, (b) ervoor zorgt dat je bij de ordinaal-variant weer een welordening kan maken, en © het verschil maakt tussen N en R, als je begrijpt wat ik bedoel. (Elk getal in N heeft maar eindig veel niet-nullen in zijn decimale of binaire ontwikkeling; voor getallen in R geldt dat uiteraard niet.)

Het is me nu dus helder geworden. Bedankt. ;)





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures