Ordinaalgetallen

[PeterPan]

Afgesplitst uit hier:

Ik wil wel een minicursusje schrijven over ordinaalgetallen als je dat interesseert.

Het is interessante stof.

[Rogier]

Ik zou je niet willen belasten met het schrijven van een minicursus speciaal voor mij. Maar er zijn vast meer mensen die er iets aan hebben, en ik zou het zeker interessant vinden, dus in dat geval graag

[TD]

Goede toegankelijke boeken hierover vond ik Introduction to set theory (Hrbacek en Jech) en The joy of sets: fundamentals of contemporary set theory (Devlin).

[PeterPan]

Ik zou je niet willen belasten met het schrijven van een minicursus speciaal voor mij. Maar er zijn vast meer mensen die er iets aan hebben, en ik zou het zeker interessant vinden, dus in dat geval graag

Ik zal eens kijken dit weekend.

[dirkwb]

Ik zal eens kijken dit weekend.

Ik ben ook wel geinteresseerd als het laagdrempelig is

[jhnbk]

Doe maar hoor. Ik lees ook wel mee.

[wabojo]

en hier is nog iemand die geinteresseerd is

[PeterPan]

De ordinaalgetallen

Uitbreiding van de natuurlijke getallen

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.

(Deze truc zullen we steeds uitvoeren als we vastlopen).

Nu we een nieuw getal

\(\omega\)

hebben gecreëerd kunnen we weer normaal verder tellen

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

enz

We krijgen uiteindelijk:

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

.

We kunnen niet verder. We maken daarom gebruik van de eerder genoemde truc.

Per definitie is

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

,

en we kunnen weer vooruit.

Het is duidelijk dat we uiteindelijk uitkomen op

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

.

waarin de getallen

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

optreden.

Hoe verder?

Wel

\(\omega^2\)

is de verzameling van tot hier toe ontdekte getallen.

Het is duidelijk dat we getallen als

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

zullen tegenkomen.

Als we dan uiteindelijk vastlopen, dan hebben we weer een nieuw symbool paraat

\(\omega^3\)

, dat het schip weer van de zandbank trekt.

Na vele nachtjes doorwerken hebben we de volgende getallen gevonden

\(\omega,\omega^2,\omega^3,\cdots\)

.

We trekken het schip weer los met de definitie van

\(\omega^{\omega}\)

.

We vinden uiteindelijk getallen als

\(\omega, \omega^{\omega}, \omega^{\omega^{\omega}},\cdots\)

.

We bedenken een nieuw getal

\(\omega(1)\)

(de verzameling van alle tot nu toe bedachte getallen).

We lopen weer vast als we

\(\omega(1), \omega(1)^{\omega(1)}, \omega(1)^{\omega(1)^{\omega(1)}},\cdots\)

hebben gecreëerd.

We vinden dan een nieuwe,

\(\omega(2)\)

, en veel, veel later

\(\omega(\omega)\)

.

Afijn, na dingen als

\(\omega(\omega)^{\omega(\omega)^{\omega(\omega)}}\)

krijgen we (stel ik voor)

\(\omega(\omega+1)\)

.

Nu stop ik, want de getallen gaan me over het hoofd groeien.

Toepassing

Je hebt niets aan een theorie als hij geen toepassingen kent.

Bekijk alle continue functies op

\(\rr\)

.

Die verzameling wordt meestal weergegeven met

\(C\)

.

Bekijk vervolgens de verzameling van functies die puntsgewijze limiet zijn van een rij functies uit

\(C\)

.

Die verzameling heet de eerste klasse van Baire en wordt weergegeven met

\(B^1\)

.

Bijvoorbeeld:

\(1_{\zz} \in B^1\)

, (

\(\not \in C\)

), want

\(1_{\zz}(x) = \lim_{n\to\infty} \sin^{2n}((2x+1)\pi)\)

.

Bekijk vervolgens de verzameling van functies die puntsgewijze limiet zijn van een rij functies uit

\(B^1\)

.

Die verzameling heet de tweede klasse van Baire en wordt weergegeven met

\(B^2\)

.

Je snapt het al, zo kunnen we maken de rij

\(B^1,B^2,\cdots\)

.

\(B^{\omega}\)

is dan de vereniging van deze verzamelingen. M.a.w.

\(B^{\omega}\)

zijn de limieten van rijen waarvan de termen functies zijn van eindige klassen van Baire.

We vinden zo Baire klassen als

\(B^{\omega^2+3\omega+7}\)

. En het aantal Baireklassen is gigantisch, zoals we uit de eerste paragraaf wel mogen concluderen.

Voorbeeld van een functie van Baire klasse 2:

\(1_{\qq} \in B^2, (\not \in B^1)\)

.

Bijzondere eigenschappen van de klassen van Baire

Er geldt uiteraard (denk aan constante rijen): Als voor de ordinaalgetallen

\(i,j\)

geldt

\(i<j\)

, dan is

\(B^i \subset B^j\)

.

Zeer opmerkelijk is de volgende eigenschap:

Als

\(i,j\)

verschillende ordinaalgetallen zijn, dan is

\(B^i \neq B^j\)

.

Blijkbaar zijn alle Baireklassen verschillend.

Wat kunnen we nu zeggen van de verzameling

\(B\)

, die de vereniging is van alle klassen van Baire?

Is

\(B\)

de verzameling van alle functies?

Neen.

\(B\)

is de verzameling van Borel meetbare functies.

Het bewijs laat ik achterwege. (Wel jammer, want het bewijs is heel fraai en van de Belgique, de la Vallee Poussin).

\(B\)

is de kleinste verzameling die alle continue functies omvat, en die gesloten is ten aanzien van het nemen van puntsgewijze limieten.

De aftelbare ordinaalgetallen (formeel)

De verzameling van getallen die we gevonden hebben in de eerste paragraaf hebben de volgende eigenschappen:

De verzameling is totaal (/lineair) geordend. Dat wil zeggen, dat voor elk tweetal verschillende getallen, een van beide kleiner is dan de andere.

Verder heeft elke deelverzameling een kleinste element. We zeggen dan dat de verzameling welgeordend is.

We zullen hierna steeds veronderstellen dan de genoemde verzamelingen totaal geordend zijn.

Twee verzamelingen

\(X\)

en

\(Y\)

zijn als geordende verzamelingen niet van elkaar te onderscheiden als er een bijectieve functie

\(f: X \to Y\)

bestaat met

\(x \leq y \Leftrightarrow f(x)\leq f(y)\)

(ga na!).

\(X\)

en

\(Y\)

heten dan (orde)-isomorf:

\(X \sim Y\)

.

Voorbeelden:

\(\nn \sim \{1-\frac1n | n \in \nn\}\)

.

\(\nn \not \sim \{1-\frac1n | n \in \nn\}\cup\{1\}\)

. Waarom niet?

\(\nn\)

is welgeordend,

\(\zz\)

niet!

Stelling:

Stel

\(X\)

is welgeordend en

\(f: X\to X\)

is strikt stijgend, dan is

\(f(x)\ge x\)

voor alle

\(x\in X\)

Bewijs:

Stel dat

\(A = \{x\in X| f(x) < x\} \neq \emptyset\)

.

\(X\)

is welgeordend en

\(A \subset X\)

, dus

\(A\)

heeft een kleinste element, zeg

\(a\)

.

Dan is

\(a \in A\)

, dus

\(f(a)<a\)

(*).

\(f\)

is strikt stijgend, dus

\(f(f(a)) < f(a)\)

.

Maar hier staat niets anders dan dat

\(f(a) \in A\)

.

\(a\)

is het kleinste element van

\(A\)

, dus moet

\(f(a) \ge a\)

zijn.

Echter dit is in strijd met (*). Tegenspraak.

Als

\(X\)

welgeordend is, dan kunnen we beginstukken van

\(X\)

onderzoeken.

Met een beginstuk bedoel ik uiteraard het volgende:

Definitie:

\(A\)

is een beginstuk van een welgeordende verzameling

\(X\)

als voor elk tweetal elementen

\(x,y\in X\)

geldt

\(y\leq x \wedge x\in A \Rightarrow y\in A\)

.

Als

\(A\neq X\)

, dan bevat

\(X\backslash A\)

een kleinste element

\(c\)

.

Dan is

\(A = \{x\in X | x<c\}\)

.

Stelling:

Als

\(X\)

welgeordend is en

\(A\)

is een beginstuk van

\(X\)

en

\(X\sim A\)

, dan is

\(X=A\)

.

Bewijs:

Zeg

\(f:X \to A\)

is een isomorfisme.

Kies

\(x\in X\)

.

Volgens de eerste stelling is

\(x \le f(x)\)

.

\(f(x)\in A\)

, dus is ook (

\(A\)

was immers een beginstuk van

\(X\)

)

\(x\in A\)

.

Dus

\(X=A\)

Stelling:

Als

\(X\)

welgeordend en

\(f:X \to X\)

is een isomorfisme, dan is

\(f(x)=x\)

voor alle

\(x\in X\)

.

Bewijs:

\(f^{-1}: X \to X\)

is strikt stijgend, dus

\(f^{-1}(z)\ge z\)

voor alle

\(z\in X\)

.

Substitutie van

\(z=f(x)\)

geeft:

\(x \ge f(x)\)

. Nu is

\(f\)

strikt stijgend, dus

\(f(x)\ge x\)

.

Dus

\(f(x) = x\)

.

Stelling:

Als

\(X,Y\)

twee welgeordende verzamelingen zijn, dan is

\(X\)

isomorf met een beginstuk van

\(Y\)

, of omgekeerd,

\(Y\)

isomorf met een beginstuk van

\(X\)

.

Het bewijs is niet moeilijk, maar is wat langer, en derhalve laat ik het hier achterwege.

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.

Een laatste opmerking:

Voor kennen het principe van volledige inductie (

\(P(1) \wedge (P(n) \to P(n+1)) \Rightarrow P\)

) en

het principe van verloopsinductie (

\(P(1) \wedge \{P(m)|m<n\} \to P(n) \Rightarrow P\)

).

Voor de natuurlijke getallen zijn ze gelijkwaardig, maar voor de ordinaalgetallen kunnen we slechts gebruik maken van het principe van verloopsinductie, dat dus krachtiger is.

[halb]

Je hebt niets aan een theorie als hij geen toepassingen kent.

en dan, een 'toepassing'

-

Het ziet er goed uit.

ps. heb je dit/gerelateerd tijdens informatica-studie geleerd?

[PeterPan]

Nee .

Er zijn veel meer toepassingen. Even zoeken met Google geeft b.v.

Transfinite ordinals as axiom number symbols for unification of quantum and electromagnetic wave functions

[Bartjes]

We vinden uiteindelijk getallen als

\(\omega, \omega^{\omega}, \omega^{\omega^{\omega}},\cdots\)

.

We bedenken een nieuw getal

\(\omega(1)\)

(de verzameling van alle tot nu toe bedachte getallen).

We lopen weer vast als we

\(\omega(1), \omega(1)^{\omega(1)}, \omega(1)^{\omega(1)^{\omega(1)}},\cdots\)

hebben gecreëerd.

We vinden dan een nieuwe,

\(\omega(2)\)

, en veel, veel later

\(\omega(\omega)\)

.

Afijn, na dingen als

\(\omega(\omega)^{\omega(\omega)^{\omega(\omega)}}\)

krijgen we (stel ik voor)

\(\omega(\omega+1)\)

.

Nu stop ik, want de getallen gaan me over het hoofd groeien.

Dat is inderdaad het punt waar het mij ook begint te duizelen. Klopt het dat ons voorstellingsvermogen tekort schiet om

\(\aleph_1\)

langs deze weg te bereiken?

[PeterPan]

We begrijpen het opbouwprincipe (in principe), maar een voorstelling maken van het geheel gaat boven onze pet.

Zie de laatste stelling: Elk beginstuk is aftelbaar, dus in principe zouden de beginstukken van de verzameling der ordinaalgetallen elementen uit

\(\qq\)

kunnen zijn. Maar de totale verzameling van ordinaalgetallen is overaftelbaar. Daar haak ik af.

Het is te vergelijken met de verzameling

\(\nn\)

, waar elk beginstuk eindig is, maar het geheel aftelbaar oneindig.

[Bartjes]

Dan ligt het dus niet aan mij. Ik vreesde al dat ik er te dom voor was. Dan heb ik nog een vraag: zou het zo kunnen zijn dat de weerbarstigheid van de continuümhypothese met deze beperkingen van ons voorstellingsvermogen samenhangt?

[TD]

Wat bedoel je met weerbarstigheid? Van de continuümhypothese heeft men kunnen tonen dat het onafhankelijk is van de gangbare axiomatiek voor de verzamelingenleer (ZF), het is binnen dat kader "onbeslisbaar" (noch de stelling, noch het tegendeel kunnen aangetoond worden; je kan een van beide gewoonweg aannemen als axioma en verschillende theorieën verder uitbouwen).

[Bartjes]

Wat bedoel je met weerbarstigheid? Van de continuümhypothese heeft men kunnen tonen dat het onafhankelijk is van de gangbare axiomatiek voor de verzamelingenleer (ZF), het is binnen dat kader "onbeslisbaar" (noch de stelling, noch het tegendeel kunnen aangetoond worden; je kan een van beide gewoonweg aannemen als axioma en verschillende theorieën verder uitbouwen).

De axioma's formaliseren een intuïtieve voorstelling van wat een verzameling is. Ikzelf zie een verzameling min of meer als een zak spulletjes. Daarbij zijn vervolgens alle materiële en geometrische beperkingen van feitelijk bestaande zakken weggedacht. Dat klinkt vast wat vreemd, maar dit beeld voldoet mij uitstekend. Ik kan mij heel goed een ideële wereld voorstellen waarin zulke verzamelingen/zakken bestaan. Wat ik mij dan weer niet kan voorstellen is dat in deze geïdealiseerde wiskundige wereld de continuümhypothese onbepaald zou zijn. Er komt onder alle deelverzamelingen van R naar mijn idee wel of niet een overaftelbare deelverzameling van R voor die niet gelijkmachtig met R is. 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.

Om op mijn oorspronkelijke vraag terug te komen: ik acht het denkbaar dat de beperkingen in het menselijk voorstellingsvermogen het zicht op zekere eigenschappen van "grote" verzamelingen ontnemen, waardoor het ontbrekende axioma ons ontgaat.

Nu ik dit zo opschrijf besef ik dat het nogal platonistisch aandoet. Ik meen echter niet dat getallen, verzamelingen, functies en dergelijken ergens een objectief bestaan hebben. Maar wel dat we het ons zo kunnen voorstellen, en dat er duidelijke grenzen zijn aan wat er in zulke denkbeeldige werelden wel of niet mogelijk is.