Ordinaalgetal

In de verzamelingenleer is een ordinaalgetal of ordinaal een generalisatie van het begrip natuurlijk getal. Net zoals met de natuurlijke getallen de elementen in een eindige verzameling in een volgorde gezet kunnen worden door de elementen te tellen, zijn ordinaalgetallen ook een soort getallen om objecten in een gegeven volgorde te plaatsen.

Representatie van de ordinalen tot en met ω^ω. Iedere omwenteling in de spiraal representeert een factor ω.

Definitie

De definitie van een ordinaalgetal maakt gebruik van beginsegmenten van welgeordende verzamelingen. Een beginsegment bestaat uit alle elementen die in de volgorde voor een bepaald gegeven element liggen, dus

• Een beginsegment van een welgeordende verzameling ${\displaystyle (X,\leq )}$ is een verzameling ${\displaystyle X_{a}=\{x\in X\mid x<a\}}$.
• Een ordinaal is een welgeordende verzameling ${\displaystyle (X,\leq )}$ waarvoor geldt dat ${\displaystyle a=X_{a}}$ voor alle ${\displaystyle a}$ in ${\displaystyle X}$, dus een welgeordende verzameling waarvan ieder element zijn eigen beginsegment is.

Opvolger-ordinaal

Bij iedere ordinaal ${\displaystyle \alpha }$ kan een nieuwe ordinaal, de opvolger-ordinaal, ${\displaystyle \alpha +1=\alpha \cup \{\alpha \}}$ gevonden worden.

Uitgaande van de lege verzameling ontstaan zo de verzamelingtheoretische voorstellingen van de natuurlijke getallen, waarbij ∅ voor de lege verzameling staat:

• ${\displaystyle 0:=\varnothing }$, de lege verzameling. Er zijn geen natuurlijke getallen kleiner dan 0.
• ${\displaystyle 1:=\{0\}=\{\varnothing \}}$
• ${\displaystyle 2:=\{0,1\}=\{\varnothing ,\{\varnothing \}\}}$
• ${\displaystyle 3:=\{0,1,2\}=\{\varnothing ,\{\varnothing \},\{\varnothing ,\{\varnothing \}\}\}}$
• enzovoort

Dit is dus een inductieve verzameling. Maar er bestaan nog meer ordinalen.

Limietordinaal

Een limietordinaal wordt gedefinieerd als een ordinaal die niet leeg is en ook geen opvolger van een ordinaal. Een limietordinaal is de verzameling van alle kleinere ordinalen. Een voorbeeld van een limietordinaal is ${\displaystyle \omega }$, de ordinaal van de natuurlijke getallen.

De ordinaal ${\displaystyle \omega }$ met zijn opvolgers vormen de rij ${\displaystyle \omega ,\omega +1,\omega +2,\ldots }$. De limietordinaal van alle ordinalen tot en met deze rij is ${\displaystyle \omega \cdot 2}$. De ordinaal ${\displaystyle \omega \cdot 2}$ met zijn opvolgers vormen de rij ${\displaystyle \omega \cdot 2}$, ${\displaystyle \omega \cdot 2+1,\,\omega \cdot 2+2,\ldots }$. Deze "opeenvolging van oneindig veel rijen" heeft ook een limietordinaal, ${\displaystyle \omega ^{2}}$, enzovoort. De volgende limietordinalen zijn ${\displaystyle \omega ^{2}+\omega ,\omega ^{2}+\omega \cdot 2,\omega ^{2}+\omega \cdot 3,\ldots ,\omega ^{2}\cdot 2,\ldots }$. Zo krijgen we alle "polynomen" in ${\displaystyle \omega }$ met niet-negatieve gehele coëfficiënten. De volgende limietordinaal is de verzameling daarvan, aangeduid als ${\displaystyle \omega ^{\omega }}$. Hier kan weer elk van de voorgaande ordinalen bij worden opgeteld. Vervolgens is er dan de limietordinaal ${\displaystyle \omega ^{\omega }\cdot 2}$. Verdergaand (na veel tussenstappen) zijn er ook ${\displaystyle \omega ^{\omega ^{\omega }}}$, ${\displaystyle \omega ^{\omega ^{\omega ^{\omega }}},\ldots }$, en

${\displaystyle \varepsilon _{0}=\omega ^{\omega ^{\omega ^{\cdot ^{\cdot ^{\cdot }}}}}=\sup\{\omega ,\omega ^{\omega },\omega ^{\omega ^{\omega }},\omega ^{\omega ^{\omega ^{\omega }}},\ldots \}}$

Deze ordinalen, en meer, zijn allemaal aftelbaar. De verzameling van alle aftelbare ordinalen is de kleinste overaftelbare ordinaal, ${\displaystyle \omega _{1}}$. Er zijn dus ook overaftelbaar veel aftelbare ordinalen. Zie ook onder.

Bewerkingen op ordinalen

Optellen en vermenigvuldigen van ordinalen wordt hieronder steeds gedefinieerd in termen van een welgeordende verzameling die de resulterende ordinaal representeert.

Optellen van twee ordinalen

De som van de ordinalen ${\displaystyle \alpha }$ en ${\displaystyle \beta }$

${\displaystyle \alpha +\beta ={\tilde {\alpha }}\cup {\tilde {\beta }}}$

waarin ${\displaystyle {\tilde {\alpha }}}$ en ${\displaystyle {\tilde {\beta }}}$ disjuncte verzamelingen zijn die gelijkmachtig zijn met respectievelijk ${\displaystyle \alpha }$ en ${\displaystyle \beta }$, en de vereniging zodanig welgeordend is dat voor alle ${\displaystyle x,y\in {\tilde {\alpha }}\cup {\tilde {\beta }}}$ geldt:

${\displaystyle x\in {\tilde {\alpha }}}$ en ${\displaystyle y\in {\tilde {\beta }}}$ dan ${\displaystyle x<y}$

${\displaystyle x,y\in {\tilde {\alpha }}}$ of ${\displaystyle x,y\in {\tilde {\beta }}}$ dan geordend volgens respactievelijk ${\displaystyle \alpha }$ of ${\displaystyle \beta }$

Men kan bijvoorbeeld kiezen: ${\displaystyle {\tilde {\alpha }}=\alpha \times \{0\}}$ en ${\displaystyle {\tilde {\beta }}=\beta \times \{1\}}$

Voorbeelden (met de elementen van de verzamelingen in volgorde geschreven):

2 + 3 = {0,1} + {0,1,2} = {(0,0), (1,0), (0,1), (1,1), (2,1)}, isomorf met {0,1,2,3,4} = 5.

${\displaystyle 1+\omega =\{0\}+\{0,1,2,\ldots \}=\{(0,0),(0,1),(1,1),(2,1),\ldots \}}$, isomorf met ${\displaystyle \{0,1,2,\ldots \}=\omega }$

en

${\displaystyle \omega +1=\{0,1,2,\ldots \}+\{0\}=\{(0,0),(1,0),(2,0),\dots ,(0,1)\}>\omega }$

Som

${\displaystyle \sum _{\eta <\lambda }\alpha _{\eta }={\mbox{Ord}}(A,<_{A})}$

met

${\displaystyle A=\bigcup _{\xi <\lambda }(\alpha _{\xi }\times \{\xi \})}$

en

${\displaystyle (\nu ,\xi )<_{A}(\nu ',\xi ')\leftrightarrow (\xi <\xi ')\vee (\xi =\xi '\wedge \nu <\nu ')}$

Vermenigvuldigen

${\displaystyle \alpha \cdot \beta =\sum _{\xi <\beta }\alpha }$

Merk op dat zowel optellen als vermenigvuldigen niet commutatief is. We hebben gezien

${\displaystyle 1+\omega \neq \omega +1}$

en verder geldt bijvoorbeeld

${\displaystyle 2\cdot \omega =\omega }$ terwijl ${\displaystyle \omega \cdot 2=\omega +\omega >\omega }$

Verdere bespreking

Ordinaalgetallen werden in 1897 door Georg Cantor^[1] ingevoerd om oneindige rijen te beschrijven en aan te kunnen geven hoe geordende verzamelingen zich tot elkaar verhouden^[2].

Algemeen is een ordinaalgetal het ordetype van een welgeordende verzameling. Ordinaalgetallen worden meestal geïdentificeerd met erfelijk transitieve verzamelingen. Ordinalen vormen een uitbreiding van de natuurlijke getallen, die echter zowel van de gehele getallen als van de kardinaalgetallen verschillen. Net als andere soorten getallen kunnen ordinalen worden opgeteld, vermenigvuldigd, en geëxponentieerd. De eindige ordinalen en kardinalen zijn de natuurlijke getallen: 0, 1, 2, ..., dit aangezien elke twee totaalordeningen van een eindige verzameling orde-isomorf zijn.

De kleinste oneindige ordinaal is ${\displaystyle \omega }$, die wordt geïdentificeerd met het kardinaalgetal ${\displaystyle \aleph _{0}}$. Maar in het transfiniete geval, verder dan ${\displaystyle \omega }$, maken ordinaalgetallen op grond van hun orde-informatie een fijner onderscheid dan kardinalen. Terwijl er slechts één aftelbare oneindige kardinaal, namelijk ${\displaystyle \aleph _{0}}$ zelf is, zijn er oneindig veel aftelbare oneindige ordinalen, namelijk

${\displaystyle \omega ,\omega +1,\omega +2,\ldots ,\omega +\omega =\omega \cdot 2,\ldots ,\omega \cdot 2+1,\ldots ,\omega ^{2},\ldots ,\omega ^{3},\ldots ,\omega ^{\omega },\ldots ,\omega ^{\omega ^{\omega }},\ldots ,\varepsilon _{0},\ldots }$

en zo verder.

De verzameling van alle aftelbare ordinaalgetallen vormt de eerste onaftelbare ordinaal, ${\displaystyle \omega _{1}}$, die wordt geïdentificeerd met de kardinaal ${\displaystyle \aleph _{1}}$, de eerstvolgende kardinaal na ${\displaystyle \aleph _{0}}$. Welgeordende kardinalen worden geïdentificeerd met hun initiële ordinalen, dat wil zeggen de kleinste ordinaal van die kardinaliteit. De kardinaliteit van een ordinaalgetal definieert een "een-op-meer-associatie" van kardinalen naar ordinalen.

In het algemeen heeft elke ordinaal ${\displaystyle \alpha }$ het ordetype van de verzameling van ordinalen die strikt genomen kleiner zijn dan α zelf. Deze eigenschap laat toe dat elke ordinaal kan worden weergegeven als een verzameling van alle ordinalen kleiner dan zichzelf. Ordinalen kunnen als volgt worden gecategoriseerd: nul, opvolgerordinalen, en limietordinalen, van verschillende cofinaliteiten. Gegeven een klasse van ordinalen, kan men het α-ste lid van die klasse identificeren, dat wil zeggen dat men de ordinalen in deze klasse kan indexeren (tellen). Een klasse is gesloten en onbegrensd als haar indexeringsfunctie continu is en nooit stopt.

De Cantor-normaalvorm geeft elke ordinaal uniek weer als een eindige som van ordinaalmachten van ω. Dit kan echter niet de basis vormen voor een universele ordinaalnotatie, dit als gevolg van zulke zelf-referentiële weergaven als ${\displaystyle \varepsilon _{0}=\omega ^{\varepsilon _{0}}}$. Grotere en grotere ordinalen kunnen worden gedefinieerd, maar ze worden steeds moeilijker te beschrijven. Elke ordinaal kan worden omgezet in een topologische ruimte door de ordinaal uit te rusten met een ordetopologie. Deze topologie is slechts dan en slechts dan discreet als de ordinaal tevens een telbaar kardinaalgetal is, wat wil zeggen voor de meeste ω. Een deelverzameling van ${\displaystyle \omega +1}$ is open in de ordetopologie dan en slechts dan als deze deelverzameling cofiniet is of wanneer element ${\displaystyle \omega }$ er zelf geen deel van uitmaakt.

voetnoten

1. Georg Cantor, Beiträge zur Begründung der transfiniten Mengenlehre. II (vert.: Bijdragen aan de grondslagen van de theorie van de transfiniete getallen II), Mathematische Annalen 49 (1897), 207-­246. Vertaling in het Engels. Citaat uit Akihiro Kanamori, Set Theory from Cantor to Cohen (Verzamelingenleer van Cantor tot Cohen)
2. Voor diepgaande inleidingen zie Levy (1979) en Sacks (2003)

websites

• (en) Devlin, K.. The joy of sets, 1979.