Ordinaalgetallen

[TD]

Er moet dus iets aan de gangbare axiomatiek (of wellicht aan de gereedschapskist van de logica) ontbreken, waardoor de continuümhypothese vooralsnog onbeslisbaar is. Anders gezegd: er zou een (vooralsnog onbekend) axioma moeten zijn, dat het mogelijk maakt de hypothese te beslissen. De weerbarstigheid zit hem dus eigenlijk daarin dat we er maar niet in slagen met een intuïtief bevredigd extra axioma op de proppen te komen, dat de hypothese beslist.

Zoals ik al zei, zou je de continuümhypothese zelf als axioma kunnen toevoegen. Men doet dat doorgaans niet, we vinden de continuümhypothese niet "intuïtief" genoeg om zomaar toe te voegen. Wat je zegt is wel precies wat men probeert (of geprobeerd heeft): een axioma vinden dat nauwer aansluit bij onze intuïtie en dat (samen met ZF of ZFC) de continuümhypothese (of de negatie ervan) impliceert.

[Bartjes]

Ik heb vroeger wel wat boekjes over zulke zaken gelezen. Maar dan moet je maar hopen dat je het goed begrepen hebt. Dank voor de uitleg.

[TD]

Misschien nog wat interessante referenties, ik sprak al over Introduction to set theory van Hrbacek en Jech (toegankelijk), een stuk diepgaander (maar minder toegankelijk) is Set theory van Jech alleen (daar heb ik me nog niet doorgeworsteld). Misschien iets minder zwaar en met meer nadruk op onafhankelijkheid (welke axioma's impliceren wat, wat is onbeslisbaar en hoe zou je zoiets kunnen aantonen) is Set Theory: An Introduction to Independence Proofs van Kunen.

[PeterPan]

Een tweede voorbeeld van een toepassing van ordinaalgetallen:

Bekijk het getal

\(2^{133}+2^8+1\)

.

Dit getal is duidelijk binair weergegeven.

Cantor was hier niet tevreden mee, want de exponenten waren helemaal niet binair, dus ging hij die ook binair schrijven.

\(2^{2^7+2^2+1}+2^{2^3}+1\)

.

Hij was nog niet tevreden, want de exponenten van de exponenten waren niet binair. Dus gaan we nog een stapje verder.

\(2^{2^{2^2+2+1}+2^2+1}+2^{2^{2+1}}+1\)

Nu gaf ie zich gewonnen. We hebben het getal geschreven in "Cantor Normaalvorm" met basis 2.

Voorbeelden:

Als we het getal 173 in Cantor Normaalvorm schrijven met basis 3, dan krijgen we:

\(2\cdot 3^{3^1+1}+3^2+2\)

.

Als we 100.000.002.300 in Cantor Normaalvorm schrijven met basis 10, dan krijgen we:

\(10^{10^1+2}+2\cdot 10^3+3\cdot 10^2\)

.

Snel stijgende rijen.

We gaan nu een zeer sterk stijgende rij getallen construeren:

We starten met een getal (zeg 17).

In Cantor Normaalvorm met basis 2 is dit

\(2^{2^2}+2^0\)

Hoe het rijtje wordt gemaakt zie je vanzelf:

\(2^{2^2}+2^0,\ \ 3^{3^3}+3^0,\ \ 4^{4^4}+4^0,\ \ 5^{5^5}+5^0,\ \ 6^{6^6}+6^0, \cdots\)

.

Het basissymbool wordt dus telkens 1 opgehoogd.

Dit is een gruwelijk snel stijgend rijtje.

Nu doe ik hetzelfde, maar ik trek bij elk volgende getal eerst 1 af, dus

\(2^{2^2}+2^0, 3^{3^3},\)

?

Wat wordt het getal dat op het vraagteken komt te staan?

\(3^{3^3}-1 = 7625597484986 = 2\cdot 3^{21}+2\cdot 3^{20} + 2\cdot 3^{19} + 2\cdot 3^{18}+\cdots+2\cdot 3^{0} = \)

\( 2\cdot 3^{2\cdot 3^2+3^1}+2\cdot 3^{2\cdot 3^2+2} + 2\cdot 3^{2\cdot 3^2+1} + 2\cdot 3^{2\cdot 3^2}+\cdots+2\cdot 3^{0}\)

Dus het rijtje wordt

\(2^{2^2}+2^0, 3^{3^3},2\cdot 4^{2\cdot 4^2+4^1}+2\cdot 4^{2\cdot 4^2+2} + 2\cdot 4^{2\cdot 4^2+1} + 2\cdot 4^{2\cdot 4^2}+\cdots+2\cdot 4^{0}, \cdots\)

De vraag is nu: convergeert deze rij of niet?

[PeterPan]

Als we het rijtje starten met 17, dan bestaat de achtste!!! term (decimaal uitgeschreven) reeds uit ruim 369 miljard cijfers.

Het rijtje stijgt godsgruwelijk snel maar zal uiteindelijk op 0 uitkomen. Je kunt je er geen voorstelling van maken hoe lang het duurt voordat het rijtje bij die 0 is aangekomen en hoe groot de getallen in dat rijtje worden.

Ruwe schets van een bewijs dat onafhankelijk van de startwaarde de rij altijd op 0 uitkomt:

Vervang in het rijtje elke basis door ω. Door telkens bij een nieuwe term er 1 af te halen neemt het

oneindige ordinaalgetal af bij elke stap, en zal derhalve na een eindig aantal stappen eindigen.

Elk ordinaalgetal heeft een opvolger, maar niet noodzakelijk een voorganger.

Bijvoorbeeld. Bekijk het beginstuk

\(1,2,3,\cdots,\omega,\omega+1,\cdots,2\omega,\cdots\)

Het getal

\(\omega\)

heeft een opvolger (

\(\omega+1\)

, maar geen voorganger.

Als we even voor het gemak de getallen die geen voorganger hebben "limietgetallen" noemen, en als A en B twee opeenvolgende limietgetallen zijn, dwz tussen hen bevindt zich nergens een limietgetal, dan wordt in onze rij op het moment dat we in B aankomen, en er 1 af willen halen, B vervangen door A + r, waarbij r een basis is (dus eindig).

Na een eindig aantal stappen ben je dat bij A, en het verhaal herhaalt zich, totdat je bij 0 bent aangekomen (eindig aantal stappen).

[PeterPan]

In de minicursus:

\(\Omega\)

is per definitie de verzameling van ordinaalgetallen.

[Bartjes]

We bekijken nu de verzameling

\(R\)

van welgeordende deelverzamelingen van

\(\rr\)

.

Als

\(X\)

zo'n verzameling is, dan stoppen we alle verzamelingen die orde-isomorf zijn met

\(X\)

in een equivalentieklasse

\([X]\)

.

De verzameling van equivalentieklassen noemen we

\(\Omega\)

.

Op die equivalentieklassen bestaat een totale ordening:

\(X \leq Y \Leftrightarrow X\)

is isomorf met een beginstuk van

\(Y\)

.

\(\Omega\)

blijkt een welgeordende verzameling te zijn.

Opmerkelijk is de volgende stelling

Stelling:

1.) Elk beginstuk van

\(\Omega\)

, dat niet gelijk is aan

\(\Omega\)

is aftelbaar.

2.)

\(\Omega\)

is overaftelbaar.

Zijn hier twee grote omega's in het spel?

[Rogier]

We beginnen vanaf 1 te tellen:

\(1,2,3,\cdots\)

.

We gaan nu deze verzameling van natuurlijke getallen uitbreiden met een extra symbool

\(\omega\)

.

Per definitie is

\(\omega = \{1,2,3,\cdots\}\)

.

\(\omega\)

is dus de verzameling van alle tot dan toe gecreëerde/gevonden getallen.

Als ik het goed begrijp: je begint met de verzameling

\(\nn\)

, die breid je uit tot een nieuwe verzameling

\(A=\nn\cup\{\omega\}\)

waarbij

\(\omega=\{1,2,3,\cdots\}=\nn\)

.

Dus eigenlijk

\(A=\nn\cup\{\nn\}=\{1,2,3,\cdots,\nn\}=\{1,2,3,\cdots,\{1,2,3,\cdots\}\}\)

Klopt dat tot zo ver?

Nu we een nieuw getal

\(\omega\)

hebben gecreëerd kunnen we weer normaal verder tellen

\(\omega+1, \omega + 2\)

enz

Misschien zoek ik hier te veel achter, maar daarnet was

\(\omega\)

een verzameling, en nu is

\(\omega\)

een getal wat je bovendien bij andere ("normale") getallen optelt. Wat betekent een x+y als x een verzameling en y een natuurlijk getal is? Hoe is die "+" operator gedefinieerd? (of denk ik nu te moeilijk en hoeft dat op dit moment nog niet per se iets te betekenen?)

[PeterPan]

Zijn hier twee grote omega's in het spel?

Nee. Er is sprake van een en dezelfde

\(\Omega\)

[Bartjes]

Nee. Er is sprake van een en dezelfde

\(\Omega\)

Is dit ook de verzameling van ordinaalgetallen?

[PeterPan]

Als ik het goed begrijp: je begint met de verzameling

\(\nn\)

, die breid je uit tot een nieuwe verzameling

\(A=\nn\cup\{\omega\}\)

waarbij

\(\omega=\{1,2,3,\cdots\}=\nn\)

.

Dus eigenlijk

\(A=\nn\cup\{\nn\}=\{1,2,3,\cdots,\nn\}=\{1,2,3,\cdots,\{1,2,3,\cdots\}\}\)

Klopt dat tot zo ver?

Misschien zoek ik hier te veel achter, maar daarnet was

\(\omega\)

een verzameling, en nu is

\(\omega\)

een getal wat je bovendien bij andere ("normale") getallen optelt. Wat betekent een x+y als x een verzameling en y een natuurlijk getal is? Hoe is die "+" operator gedefinieerd? (of denk ik nu te moeilijk en hoeft dat op dit moment nog niet per se iets te betekenen?)

Je moet het zo zien.

In den beginnne was er niets

\(\emptyset\)

. Dit symbool noteren we gebruikelijker met het symbool (dat ala nu tot getal wordt verheven) 0.

De opvolger, soms genoteerd als

\(S(\emptyset)\)

, of plastischer als

\(\emptyset + 1\)

, is de verzameling van alles wat je tot nu toe hebt gecreëerd, dus

\(\{\emptyset\}\)

.

De gebruikelijke afkorting is 1.

De opvolger van 1 is de verzameling van alle objecten die tot nu zijn gecreëerd, dus 2 = {0,1} ofwel

\(\{\emptyset, \{\emptyset\}\}\)

.

Zo gaan we verder.

Je ziet dat

\(\omega\)

op dezelfde manier gecreëerd wordt als elk ander getal.

De optelling

\(x+y\)

is wat je ervan verwachten mag.

\(\omega^2 +3\omega +5 - 7\omega = \omega^2 -4\omega + 5\)

.

We spreken van symbolen in de verzamelings-schrijfwijze, en van getallen als we de afkortingen gebruiken die we daarvoor gegeven hebben, zoals 1,2,3,

\(\omega\)

.

[PeterPan]

Is dit ook de verzameling van ordinaalgetallen?

De laatste paragraaf geeft de formele definitie van ordinaalgetallen.

Voor het geven van bewijzen is dit veel handiger. Ze komen overeen met de losse informele manier waarop de ordinaalgetallen in de eerste paragraaf zijn gedefinieerd. Eigenlijk zijn ze in de eerste paragraaf niet gedefinieerd, maar intuitief geconstrueerd. Maar zoals ik al aan het eind van die paragraaf meld raak je op den duur verstrikt in de complexiteit.

Vergelijk dit met de theorie van de equivalentieklassen

\(L^2\)

, als het om kwadratisch integreerbare functies gaat.

[Bartjes]

Dan is de

\(\rr\)

in je stuk dus niet de verzameling van reële getallen?

[PeterPan]

Dat begrijp ik niet. Beweer ik dat ergens?

[Bartjes]

Dan is de

\(\rr\)

in je stuk dus niet de verzameling van reële getallen?

Ik wist niet dat dat teken ook voor andere verzamelingen gebruikt wordt. Vandaar.