Waarom is 2^omega aftelbaar?

Moderators: dirkwb, Xilvo

Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
Reageer
Berichten: 2

Waarom is 2^omega aftelbaar?

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!

Gebruikersavatar
Berichten: 24.578

Re: Waarom is 2^omega aftelbaar?

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:
\({2^\omega } \ne {2^{{\aleph _0}}}\)
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)

Re: Waarom is 2^omega aftelbaar?

Ik kan je een exact bewijs geven, maar laten we het vooreerst proberen via overtuiging.

De rijen
\(0,1,2,3,4,5,\cdots\)
,
\(\omega,\omega+1,\omega+2,\omega+3,\omega+4,\omega+5,\cdots\)
\(2\omega,2\omega+1,2\omega+2,2\omega+3,2\omega+4,2\omega+5,\cdots\)
\(3\omega,3\omega+1,3\omega+2,3\omega+3,3\omega+4,3\omega+5,\cdots\)
\(\cdots\)
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:
\(0,\ \ \ ,1,\omega,\ \ \ ,2,\omega+1,2\omega,\ \ \ ,3,\omega+2,2\omega+1,4\omega,\ \ \ \cdots\)
.

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:
\(0,\ \ \ ,1,\omega,\ \ \ ,2,\omega+1,2\omega,\ \ \ ,3,\omega+2,2\omega+1,3\omega,\ \ \ \cdots\)
Bij elk element
\(\omega^2\)
bijtellen geeft de daaropvolgende aftelbare rij
\(\omega^2,\ \ \ ,\omega^2+1,\omega^2+\omega,\ \ \ ,\omega^2+2,\omega^2+\omega+1,\omega^2+2\omega,\ \ \ ,\omega^2+3,\omega^2+\omega+2,\omega^2+2\omega+1,\omega^2+3\omega,\ \ \ \cdots\)
Het volgende element is
\(\omega^3\)
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
\(a_1,a_2,a_3,\cdots\)
noem.

Op deze rij volgt de rij
\(\omega^3+a_1,\omega^3+a_2,\omega^3+a_3,\cdots\)
.

De vereniging van deze twee rijen wordt gevolgd door het element
\(\omega^4\)
.

Zo voortgaande krijgen we achtereenvolgens aftelbare rijen tot element
\(\omega^n\)
voor elke n.

Een vereniging van aftelbaar veel aftelbare verzamelingen is weer aftelbaar (diagonaaltruc).

Dus tot
\(\omega^{\omega}\)
zijn er aftelbaar veel ordinaalgetallen.

Berichten: 2

Re: Waarom is 2^omega aftelbaar?

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. ;)

Reageer