Utente:Roberto.zanasi/sandbox

In matematica, i numeri ordinali costituiscono una estensione dei numeri naturali introdotta da Georg Cantor nel 1897 allo scopo di tenere conto anche di successioni infinite e di classificare gli insiemi in base a certi tipi di strutture d'ordine che essi possiedono. Questa generalizzazione è l'oggetto della presente pagina. Questa estensione è diversa da quella che si ottiene definendo i numeri cardinali.

Il buon ordinamento è un ordinamento totale dotato di induzione transfinita, dove con il termine induzione transfinita si intende un'estensione dell'induzione matematica che va oltre i numeri finiti. Gli ordinali rappresentano classi di equivalenza di buoni ordinamenti, dove la relazione di equivalenza considerata è l'isomorfismo d'ordine. Ogni ordinale è definito come l'insieme degli ordinali minori di esso. Gli ordinali possono essere suddivisi nelle seguenti categorie: zero, ordinali successori, ordinali limite (di diversa cofinalità). Data una classe di ordinali, è possibile identificare il membro α-esimo di quella classe: cioè è possibile indicizzarli tutti. Una classe è chiusa e illimitata se la sua funzione indice è continua e non ha termine. Si possono definire l'addizione, la moltiplicazione e la potenza di ordinali, ma non la sottrazione o la divisione. La forma norlame di Cantor è un metodo standard per scrivere gli ordinali. Esiste una corrispondenza molti-a-uno tra gli ordinali e i cardinali. Si possono definire ordinali sempre più grandi, ma diventano sempre più complicati da descrivere. Gli ordinali possiedono una topologia naturale.

Introduzione

Un numero naturale può essere usato per due scopi: per descrivere la grandezza di un insieme, o per descrivere la posizione di un elemento in una successione. Mentre nel mondo finito questi due concetti coincidono, quando si ha a che fare con insiemi infiniti è necessario distinguerli. La nozione di grandezza porta ai numeri cardinali, anch'essi scoperti da Cantor, mentre la nozione di posizione è generalizzata dai numeri ordinali descritti qui.

Mentre la nozione di numero cardinale è associata a insiemi che non sono dotati di particolari strutture, gli ordinale sono invece intimamente legati a quella speciale categoria di insiemi detti insiemi bene ordinati (questo legame è talmente stretto che alcuni matematici non fanno alcuna distinzione tra i due concetti). Per definire brevemente questi concetti, un insieme bene ordinato è un insieme totalmente ordinato (ovvero tale per cui presa una qualunque coppia di suoi elementi si può sempre dire quale dei due sia il più piccolo e quale il più grande) in cui non esistono successioni infinite decrescenti (ma possono esistere successioni infinite crescenti). Gli ordinali possono essere usati per etichettare gli elementi di un qualunque insieme bene ordinato (il più piccolo elemento viene chiamato 0, quello successivo 1, quello dopo 2, "e così via") e per misurare la "lunghezza" dell'intero insieme mediante il più piccolo ordinale che non rappresenta nessun elemento dell'insieme stesso. Questa "lunghezza" viene detta il tipo di ordine dell'insieme.

Ogni ordinale è definito dall'insieme di ordinali che lo precedono: in effetti, la più comune definizione di ordinale identifica ogni ordinale come l'insieme degli ordinali che lo precedono. Per esempio, l'ordinale 42 è il tipo di ordine degli ordinali minori di esso, e cioè gli ordinali da 0 (il più piccolo di tutti gli ordinali) a 41 (il predecessore immediato di 41), e viene generalmente identificato con l'insieme {0,1,2,…,41}. Inversamente, ogni insieme di ordinali chiuso verso il basso (il che significa che ogni ordinale minore di un ordinale dell'insieme appartiene anch'esso all'insieme) è un ordinale — o può essere identificato con un ordinale.

Finora sono stati nominati solo ordinali finiti, che sono i numeri naturali. Ma esistono anche ordinali infiniti: il più piccolo di essi è ω, che è il tipo di ordine dei numeri naturali (cioè degli ordinali finiti) e che può essere identificato con l'insieme dei numeri naturali (infatti l'insieme dei naturali è bene ordinato, così come deve essere ogni insieme di ordinali, e siccome è chiuso verso il basso può essere identificato con l'ordinale associato ad esso, che è esattamente la definizione di ω).

Una rappresentazione grafica dell'ordinale ω². Ogni segmento verticale corrisponde a un ordinale nella forma ω·m+n dove m e n sono numeri naturali.

Si può creare un'idea intuitiva più chiara sugli ordinali esaminandone alcuni: come detto sopra, essi hanno inizio con i numeri naturali 0, 1, 2, 3, 4, 5, … Dopo tutti i numeri naturali viene il primo ordinale infinito, ω, e dopo vengono gli ordinali ω+1, ω+2, ω+3, e così via (il significato preciso dell'addizione di ordinali sarà definito in seguito, per ora si considerino queste operazioni solo come simboli). Dopo tutti questi ordinali viene ω·2 (che è ω+ω), ω·2+1, ω·2+2, e così via, poi ω·3, e, più avanti, ω·4. L'insieme degli ordinali che hanno la questa forma (ω·m+n, dove m e n sono numeri naturali) deve essere esso stesso associato ad un ordinale, che è ω². Proseguendo, si arriverà a ω³, poi ω⁴, e cos' via fino a ω^ω, poi ω^ω², e molto dopo a ε₀ (per dare alcuni esempi dei primi ordinali numerabili). Si può andare avanti indefinitamente, e questo è proprio ciò che gli ordinali permettono sempre di fare: ogni volta che si pronuncia la frase "e così via" quando si enumerano gli ordinali si sta definendo un ordinale più grande.

Definizioni

Insieme bene ordinato

Un insieme bene ordinato è un insieme ordinato in cui ogni sottoinsieme non vuoto ammette minimo: questo è equivalente (almeno in presenza dell'assioma della scelta dipendente) a dire che l'insieme è totalmente ordinato e non contiene successioni infinite decrescenti.

In practice, the importance of well-ordering is justified by the possibility of applying transfinite induction, which says, essentially, that any property that passes on from one the predecessors of an element to that element itself must be true of all elements (of the given well-ordered set). If the states of a computation (computer program or game) can be well-ordered in such a way that each step is followed by a "lower" step, then you can be sure that the computation will terminate.

Now we don't want to distinguish between two well-ordered sets if they only differ in the "labeling of their elements", or more formally: if we can pair off the elements of the first set with the elements of the second set such that if one element is smaller than another in the first set, then the partner of the first element is smaller than the partner of the second element in the second set, and vice versa. Such a one-to-one correspondence is called an order isomorphism (or a strictly increasing function) and the two well-ordered sets are said to be order-isomorphic, or similar (obviously this is an equivalence relation). Provided there exists an order isomorphism between two well-ordered sets, the order isomorphism is unique: this makes it quite justifiable to consider the sets as essentially identical, and to seek a "canonical" representative of the isomorphism type (class). This is exactly what the ordinals provide, and it also provides a canonical labeling of the elements of any well-ordered set.

So we essentially wish to define an ordinal as an isomorphism class of well-ordered sets: that is, as an equivalence class for the equivalence relation of "being order-isomorphic". There is a technical difficulty involved, however, in the fact that the equivalence class is too large to be a set in the usual Zermelo-Fraenkel formalization of set theory. But this is not a serious difficulty. We will say that the ordinal is the order type of any set in the class.

---

Nella teoria degli insiemi, i numeri naturali sono solitamente costruiti con gli insiemi, in modo tale che ogni numero naturale è l'insieme di tutti i numeri naturali più piccoli di esso:

0 = {} (insieme vuoto)

1 = {0} = { {} }

2 = {0,1} = { {}, { {} } }

3 = {0,1,2} = {{}, { {} }, { {}, { {} } }}

4 = {0,1,2,3} = { {}, { {} }, { {}, { {} } }, {{}, { {} }, { {}, { {} } }} }

eccetera.

Visto in questo modo, ogni numero naturale è un insieme ben ordinato: l'insieme 4, per esempio, contiene gli elementi 0, 1, 2, 3 che sono ovviamente ordinati in questo modo: 0 < 1 < 2 < 3. Un numero naturale è più piccolo di un altro se e solo se è un elemento dell'altro.

Non vogliamo distinguere due insiemi bene ordinati se essi differiscono solamente nella notazione usata per i loro elementi. Detto in modo più formale: se si possono accoppiare gli elementi del primo insieme con quelli del secondo in modo tale che se un elemento è più piccolo di un altro nel primo insieme, allora il corrispondente del primo elemento è più piccolo del corrispondente del secondo nel secondo insieme, e viceversa. Una tale corrispondenza biunivoca è detta isomorfismo d'ordine (o una funzione strettamente crescente, o isotonìa) e i due insiemi bene ordinati sono detti isomorfi rispetto all'ordine, o isotoni.

Seguendo questa convenzione, si può mostrare che ogni insieme finito bene ordinato è isomorfo rispetto all'ordine a uno e uno solo numero naturale. Questo fatto fornisce la motivazione che porta alla generalizzazione ai numeri infiniti.

Dal finito al "transfinito"

Abbiamo visto come è possibile costruire tutti i numeri naturali partendo dall'insieme vuoto e considerando di volta in volta l'insieme che ha come suoi elementi tutti gli insiemi precedentemente costruiti. Abbiamo visto che ciascuno di questi "numeri naturali" è dotato naturalmente di una struttura di insieme ben ordinato e al contempo tutti questi numeri naturali costituiscono nel complesso un insieme ben ordinato. Abbiamo visto che la relazione d'ordine che è naturale definire in questo contesto è quella che stabilisce che un "numero" è minore di un altro se è un suo elemento. Questi insiemi ordinati sono chiamati anche ordinali finiti.

Il tipo di costruzione che genera la sequenza degli ordinali finiti può essere portata avanti molto "oltre" definendo in questo modo quelli che Cantor chiamava ordinali transfiniti. Supponiamo di aver definito tutti i numeri ordinali finiti nel modo suddetto e facciamo un ulteriore "passo": consideriamo - di nuovo - l'insieme ordinato di tutti gli insiemi definiti finora - cioè i numeri naturali - e lo chiamiamo ω:

ω:={0,1,2,3,...}

Omega è anch'esso naturalmente dotato di una strruttura di insieme ordinato, come i suoi predecessori (l'ordinamento è dato, come prima, dall'inclusione insiemistica). Se prima avevamo gli ordinali finiti ω è il primo ordinale transfinito.

Ma possiamo andare ancora avanti: definiamo

ω+1:={0,1,2,3,...,ω}

che è ancora un insieme totalmente ordinato, poi

ω+2:={0,1,2,3,...,ω,ω+1}

ω+3:={0,1,2,3,...,ω,ω+1,ω+2}

...

Otteniamo così una nuova sequenza infinita. Osserviamo che anche l'insieme degli ordinali che abbiamo costruito finora è dotato naturalmente di una struttura di insieme ordinato, più precisamente abbiamo:

1<2<3<4<...<ω<ω+1<ω+2<ω+3<...

Si verifica facilmente che questo ordinamento è totale ed è un buon ordinamento.
Di nuovo possiamo andare "oltre" e dare un nome all'insieme di tutti questi oedinali:

2ω=ω+ω:={0,1,2,3,...,ω,ω+1,ω+2,ω+3,...}

E si può andare avanti come prima considerando ad ogni passo l'insieme di tutti oggetti costruiti fino a quel momento... ma vale la pena soffermarsi un attimo ad analizzare la sequenza di insiemi che stiamo costruendo.

Nello schema esposto fin qui si procede alternativamente in due modi:

1. dato un ordinale $\alpha$ precedentemente costruito, si aggiunge al suo interno un nuovo elemento dato da $\alpha$ stesso. Il nuovo insieme è quindi $\alpha \cup \{\alpha \}$, è un insieme ordinato ed è chiamato ordinale successore di $\alpha$;
2. data una sequenza ordinata e infinita di ordinali $\alpha _{1},\alpha _{2},\alpha _{3},...\alpha _{n},....$ di cui il successivo include il precedente si costruisce un nuovo insieme come unione degli insiemi della sequenza $\alpha _{\infty }:=\cup _{n}\alpha _{n}$. L'insieme $\alpha _{\infty }$ così definito si chiama ordinale limite della sequenza $\{\alpha _{n}\}$.

Con queste due regole si può continuare la sequenza definendo gli ordinali

3ω:={0,1,2,3,...,ω,ω+1,ω+2,ω+3,...,2ω, 2ω+1, 2ω+2, 2ω+3, ...}

4ω:={0,1,2,3,...,ω,ω+1,ω+2,ω+3,...,2ω, 2ω+1, 2ω+2, 2ω+3, ...,3ω, 3ω+1, 3ω+2, 3ω+3, ...}

...

nω:={0,1,2,3,...,ω,ω+1,ω+2,ω+3,...,2ω, 2ω+1, 2ω+2, 2ω+3, ...,3ω, 3ω+1, 3ω+2, 3ω+3, ...,(n-1)ω,(n-1)ω+1,(n-1)ω+2,...}

...

ω×ω=ω²:={1,2,3,...,ω,...,2ω,...,3ω,...,nω,.........}

Rappresentazione visiva dell'ordinale ω²: i primi segmenti rappresentano i numeri naturali, il primo triangolo rappresenta ω, nell'immagine ci sono (idealmente) ω copie di ω disposte in sequenza.

La definizione originale

La definizione originale di numero ordinale, presente per esempio nei Principia Mathematica, definisce il tipo di ordine di un buon ordinamento come l'insieme di tutti i buoni ordinamenti simili (isomorfi rispetto all'ordine, o isotonici) a quel buon ordinamento. Questa definizione deve essere abbandonata nel sistema di assiomi di Zermelo-Fraenkel e nei sistemi relativi a questa teoria assiomatica degli insiemi perché queste classi di equivalenza sono troppo grandi; però questa definizione può ancora essere usata nella teoria dei tipi e nella teoria degli insiemi di Quine New Foundations e in sistemi ad esse relativi, nei quali essa offre una sorprendente soluzione alternativa al paradosso di Burali-Forti riguardante il più grande numero ordinale.

La definizione moderna e le prime proprietà

Si vogliono costruire i numeri ordinali come speciali insiemi bene ordinati in modo tale che ogni insieme ben ordinato sia isomorfo rispetto all'ordine a uno un un solo numero ordinale. La definizione seguente migliora l'approccio di Cantor e venne data per primo da John von Neumann:

Un insieme S è un ordinale se e solo se S è totalmente ordinato rispetto all'inclusione tra insiemi e ogni elemento di S è anche un sottoinsieme di S.

L'insieme S risulta così automaticamente bene ordinato rispetto all'inclusione. Questo fatto si basa sull'assioma di fondazione: ogni insieme non vuoto S contiene un elemento a che è disgiunto da S.

Si noti che i numeri naturali sono ordinali secondo questa definizione. Per esempio, 2 è un elemento di 4 = {0, 1, 2, 3}, e 2 è uguale a {0, 1} e per questo è un sottoinsieme di {0, 1, 2, 3}.

Mediante induzione transfinita si può dimostrare che ogni insieme ben ordinato è isomorfo rispetto all'ordine a esattamente uno di questi ordinali.

Inoltre, gli elementi di ogni ordinale sono pure ordinali. Ogni volta che si hanno due ordinali S e T, S è un elemento di T se e solo se S è un sottoinsieme proprio di T; in più, o S è un elemento di T, o T è un elemento di S, oppure i due insiemi sono uguali. Così ogni insieme di ordinali è totalmente ordinato. In effetti, è vera una proprietà molto più forte:

Ogni insieme di ordinali è bene ordinato.

Questo importante risultato generalizza il fatto che ogni insieme di numeri ordinali è bene ordinato e permette l'uso della induzione transfinita con gli ordinali.

Un'altra conseguenza è la seguente:

• Ogni ordinale S è un insieme avente precisamente come elementi gli ordinali più piccoli di S.

Questa affermazione determina completamente, dal punto di vista della teoria degli insiemi, la struttura di ogni ordinale a partire da altri ordinali. È anche usata per dimostrare molti altri risultati utili sugli ordinali, ad esempio l'importante caratterizzazione della relazione d'ordine tra gli ordinali:

• Ogni insieme di ordinali ha un estremo superiore, che è l'ordinale ottenuto prendendo l'unione di tutti gli ordinali dell'insieme.

Un altro esempio è il fatto seguente:

• La collezione di tutti gli ordinali non è un insieme.

Inoltre, dal momento che ogni ordinale contiene solo altri ordinali, ne segue che ogni membro della collezione di tutti gli ordinali è anche un suo sottoinsieme. Quindi, se questa collezione fosse un insieme, dovrebbe essere per definizione un ordinale; allora sarebbe membro di se stesso, cosa che contraddice l'assioma di regolarità (si veda anche il paradosso di Burali-Forti).

Un ordinale è finito se e solo sel'insieme dei suoi elementi, ordinato secondo l'ordine inverso, è anch'esso bene ordinato, e questo succede se e solo se ogni suo sottoinsieme ha massimo.

Altre definizioni

Esistono altre formulazioni moderne della definizione di ordinale. Ognuna di queste è essenzialmente equivalente alla definizione data sopra. Una di queste è la seguente. Una classe S è transitiva se, ogni volta che x è elemento di y e y è elemento di S, allora x è elemento di S. Allora un ordinale viene definito come una classe S transitiva e tale che ogni membro di S è anch'esso transitivo. Si noti che queste definizione funzionerà solo in presenza dell'assioma di regolarità: un insieme che è il suo unico elemento soddisfa a questa condizione ma non è un ordinale!

Aritmetica degli ordinali

Per definire la somma S + T dei due ordinali S e T si procede come di seguito: per prima cosa gli elementi di T sono rinominati in modo tale che S e T risultino disgiunti, poi l'insieme bene ordinato S viene scritto "alla sinistra" dell'insieme bene ordinato T; questo significa che si definisce un ordinamento su S ∪ T in cui ogni elemento di S risulta essere più piccolo di ogni elemento di T. Gli insiemi S e T mantengono l'ordinamento che già avevano. In questo modo viene formato un nuovo insieme bene ordinato che è isomorfo rispetto all'ordine a un ordinale, che viene chiamato S + T. Questa addizione è associativa e generalizza l'addizione dei numeri naturali. Detto in altri termini meno rigorosi, per sommare due ordinali S e T basta mettere accanto gli elementi dei due insiemi e ricontare.

Il primo ordinale transfinito è ω, l'insieme di tutti i numeri naturali. Si provi ora a visualizzare l'ordinale ω+ω: si prendono due copie dei numeri naturali ordinate secondo l'ordinamento usuale, e la seconda copia deve essere messa alla destra della prima. Se si indica la seconda copia con {0'<1'<2',...} allora ω+ω può essere rappresentato così:

0 < 1 < 2 < 3 < ... < 0' < 1' < 2' < ...

Questo ordinale è un numero diverso da ω perché in ω solo lo 0 non ha un antecedente (cioè 0 non è il successore di nessun numero) mentre in ω+ω i due elementi 0 e 0' non hanno un antecedente. Questo è 3 + ω

0 < 1 < 2 < 0' < 1' < 2' < ...

e, dopo aver rinominato i suoi elementi, si vede che è uguale ad ω. Si ha quindi che 3 + ω = ω. Ma ω + 3 non è uguale a ω, visto che ω + 3 ha un massimo elemento, mentre ω non lo possiede. Dunque l'addizione tra numeri ordinali non è commutativa.

Ora è facile vedere che, per esempio, (ω + 4) + ω = ω + (4 + ω) = ω + ω.

Per moltiplicare i due ordinali S e T si deve scrivere l'insieme bene ordinato T sostituendo ogni suo elemento con una diversa copia dell'insieme bene ordinato S. Questa operazione produce un nuovo insieme bene ordinato, che definisce un ordinale, indicato con ST. Anche in questo caso si ha una operazione associativa che generalizza la moltiplicazione tra numeri naturali.

Questo è ω2:

0₀ < 1₀ < 2₀ < 3₀ < ... < 0₁ < 1₁ < 2₁ < 3₁ < ...

e si ha che: ω2 = ω + ω. Mentre 2ω ha questo aspetto:

0₀ < 1₀ < 0₁ < 1₁ < 0₂ < 1₂ < 0₃ < 1₃ < ...

che, dopo una sostituzione, ha l'aspetto di ω quindi 2ω = &omega. La moltiplicazione tra ordinali non è commutativa.

La proprietà distributiva è parzialmente valida nell'aritmetica degli ordinali: R(S+T) = RS + RT. Ma l'altra legge distributiva (T+U)R = TR + UR non è vera in generale: (1+1)ω è uguale a 2ω = ω mentre 1ω + 1ω è uguale a ω+ω. Quindi i numeri ordinali non formano un anello.

Una struttura ad anello come questa, con solo la proprietà distributiva sinistra, viene chiamata quasianello sinistro: però gli ordinali non sono nemmeno un quasianello perché non ammettono l'inverso dell'addizione (la negazione).

Ora si può definire l'esponenziazione di numeri ordinali. Per esponenti finiti la definizione dovrebbe essere ovvia, per esempio $\omega ^{2}=\omega \omega$, perché viene usata la moltiplicazione tra ordinali. Ma questa operazione può anche essere visualizzata come un insieme di coppie ordinate di numeri naturali, ordinate secondo una variante dell'ordinamento lessicografico che mette al primo posto la posizione meno significativa:

(0,0) < (1,0) < (2,0) < (3,0) < ... < (0,1) < (1,1) < (2,1) < (3,1) < ... < (0,2) < (1,2) < (2,2) < ...

Analogamente per ogni n finito $\omega ^{n}$ può essere visualizzato come l'insieme delle n-uple di numeri naturali.

Procedendo oltre, per $\omega ^{\omega }$ si può cercare di visualizzare l'insieme delle successioni infinite di numeri naturali. Però se si cerca di usare una qualsiasi variante dell'ordinamento lessicografico in questo insieme, si scopre che esso non è bene ordinato. Occorre aggiungere la restrizione che solo un numero finito di elementi della successione è diverso da zero. In questo modo l'ordinamento funziona, e appare come l'ordinamento di numeri naturali scritti in notazione decimale, ma con le posizioni delle cifre rovesciate, e con numeri naturali arbitrari al posto delle sole cifre 0-9.

(0,0,0,...) < (1,0,0,0,...) < (2,0,0,0,...) < ... <

(0,1,0,0,0,...) < (1,1,0,0,0,...) < (2,1,0,0,0,...) < ... <

(0,2,0,0,0,...) < (1,2,0,0,0,...) < (2,2,0,0,0,...)

< ... <

(0,0,1,0,0,0,...) < (1,0,1,0,0,0,...) < (2,0,1,0,0,0,...)

< ...

Così, in generale, per elevare un ordinale S alla potenza di un ordinale T si devono scrivere le copie dell'insieme bene ordinato T e si deve sostituire ogni elemento con qualche elemento di S, con la restrizione che tutti gli elementi della successione, eccetto un numero finito, devono essere il primo elemento di S. Si trova che $1^{\omega }=1$, $2^{\omega }=\omega$, $2^{\omega +1}=\omega 2=\omega +\omega$. Valgono inoltre le regole sulle potenze seguenti: $(S^{T})^{U}=S^{TU}$ e $S^{T+U}=S^{T}S^{U}$.

Forma normale di Cantor

I numeri ordinali presentano un'aritmetica estremamente ricca. Ogni numero ordinale $\alpha >0$ può essere scritto in modo unico come $\omega ^{\beta _{1}}c_{1}+\omega ^{\beta _{2}}c_{2}+\ldots +\omega ^{\beta _{k}}c_{k}$, dove $k,c_{1},c_{2},\ldots ,c_{k}$ sono interi positivi, e $\beta _{1}>\beta _{2}>\ldots >\beta _{k}$ sono numeri ordinali (è possibile che $\beta _{k}=0$). Questa decomposizione di $\alpha$ è chiamata forma normale di Cantor di $\alpha$, e può essere considerata il sistema numerico in base-ω. L'esponente maggiore $\beta _{1}$ viene detto il grado di $\alpha$, e soddisfa alla relazione $\beta _{1}\leq \alpha$. Nel caso in cui $\beta _{1}<\alpha$, si ha una rappresentazione finita di α fatta con soli interi (che si appoggia a uno scheletro di ω, addizioni, moltiplicazioni e potenze).

Esistono numeri ordinali che non possono essere ottenuti a partire da ω con un numero finito di addizioni, moltiplicazioni ed elevamenti a potenza. Il più piccolo di questi è indicato con ε₀. Questo ordinale è molto importante in molte dimostrazioni per induzione, perché per molti scopi l'induzione transfinita è richiesta solo fino a ε₀. Si noti che $\epsilon _{0}=\omega ^{\omega ^{\omega ^{\cdots }}}$, così $\epsilon _{0}=\omega ^{\epsilon _{0}}$. Un'altra formula è

$\epsilon _{0}=1+\omega +\omega ^{\omega }+\omega ^{\omega ^{\omega }}+\omega ^{\omega ^{\omega ^{\omega }}}+\dots$.

L'ordinale $\epsilon _{0}$ è anche il primo numero che soddisfa l'equazione di Cantor $\omega ^{\epsilon }=\epsilon$. Questa equazione ha infinite soluzioni: la successiva è

$\epsilon _{1}=(\epsilon _{0}+1)+\omega ^{\epsilon _{0}+1}+\omega ^{\omega ^{\epsilon _{0}+1}}+\omega ^{\omega ^{\omega ^{\epsilon _{0}+1}}}+\dots$,

cui seguono

$\epsilon _{1},\epsilon _{2},\dots ,\epsilon _{\omega },\epsilon _{\omega +1},\dots ,\epsilon _{\omega 2},\dots ,\epsilon _{\omega ^{2}},\dots ,\epsilon _{\omega ^{\omega }},\dots ,\epsilon _{\epsilon _{0}},\dots ,\epsilon _{\epsilon _{0}+\omega },\dots ,\epsilon _{\epsilon _{0}+\omega ^{\omega }},\dots ,$

$\epsilon _{\epsilon _{0}2},\dots ,\epsilon _{\epsilon _{1}},\dots ,\epsilon _{\epsilon _{2}},\dots ,\epsilon _{\epsilon _{\omega }},\dots ,\epsilon _{\epsilon _{\epsilon _{0}}},\dots ,\epsilon _{\epsilon _{\epsilon _{1}}},\dots ,\epsilon _{\epsilon _{\epsilon _{\omega }}},\dots ,\epsilon _{\epsilon _{\epsilon _{\epsilon _{0}}}},\dots$

e così via fino a $\epsilon _{\epsilon _{\epsilon _{\epsilon _{\epsilon _{\dots }}}}}$, che è la prima soluzione di $\epsilon _{\alpha }=\alpha$.

$\epsilon _{0}$ è ancora numerabile. Esistono ordinali non numerabili. Il più piccolo ordinale non numerabile è uguale all'insieme di tutti gli ordinali numerabili, e solitamente viene indicato con ω₁.

Topologia e ordinali limite

Gli ordinali sono dotati anche di una interessante topologia d'ordine in virtù del fatto che sono totalmente ordinati. In questa topologia, la successione 0, 1, 2, 3, 4, ... ha limite ω e la successione ω, ω^ω, ω^(ω^ω), ... ha limite ε₀. Gli ordinali che non hanno un antecedente possono sempre essere scritti come llimite di una rete di altri ordinali (ma non necessariamente come il limite di una successione, cioè come limite di una quantità numerabile di ordinali più piccoli) e sono chiamati ordinali limite; gli altri ordinali sono gli ordinali successori.

Gli spazi topologici ω₁ e il suo successore ω₁+1 sono spesso usati nei libri di testo come esempi di spazi topologici non numerabili. Per esempio, nello spazio topologico ω₁+1, l'elemento ω₁ è nella chiusura del sottoinsieme ω₁ anche se nessuna successione di elementi in ω₁ ha l'elemento ω₁ come limite. Lo spazio ω₁ è uno spazio first-countable, ma non second-countable, e ω₁+1 non gode di nessuna di queste due proprietà.

Alcuni ordinali speciali possono essere usati per misurare la grandezza o cardinalità di un insieme. Questi sono chiamati numeri cardinali.

Voci correlate

• ordinale successore
• ordinale limite
• numero cardinale

Bibliografia

• 1996 - Conway, J. H. e Guy, R. K. "I numeri ordinali di Cantor." Ne Il libro dei Numeri. Hoepli, pp. 230-238 (ISBN 8820325195).

Definitions

Define well-ordered set

A well-ordered set is an ordered set in which every non-empty subset has a least element: this is equivalent (at least in the presence of the axiom of dependent choices) to just saying that the set is totally ordered and there is no infinite decreasing sequence, something which is perhaps easier to visualize. In practice, the importance of well-ordering is justified by the possibility of applying transfinite induction, which says, essentially, that any property that passes on from one the predecessors of an element to that element itself must be true of all elements (of the given well-ordered set). If the states of a computation (computer program or game) can be well-ordered in such a way that each step is followed by a "lower" step, then you can be sure that the computation will terminate.

Now we don't want to distinguish between two well-ordered sets if they only differ in the "labeling of their elements", or more formally: if we can pair off the elements of the first set with the elements of the second set such that if one element is smaller than another in the first set, then the partner of the first element is smaller than the partner of the second element in the second set, and vice versa. Such a one-to-one correspondence is called an order isomorphism (or a strictly increasing function) and the two well-ordered sets are said to be order-isomorphic, or similar (obviously this is an equivalence relation). Provided there exists an order isomorphism between two well-ordered sets, the order isomorphism is unique: this makes it quite justifiable to consider the sets as essentially identical, and to seek a "canonical" representative of the isomorphism type (class). This is exactly what the ordinals provide, and it also provides a canonical labeling of the elements of any well-ordered set.

So we essentially wish to define an ordinal as an isomorphism class of well-ordered sets: that is, as an equivalence class for the equivalence relation of "being order-isomorphic". There is a technical difficulty involved, however, in the fact that the equivalence class is too large to be a set in the usual Zermelo-Fraenkel formalization of set theory. But this is not a serious difficulty. We will say that the ordinal is the order type of any set in the class.

Definition of an ordinal as an equivalence class

The original definition of ordinal number, found for example in Principia Mathematica, defines the order type of a well-ordering as the set of all well-orderings similar (order-isomorphic) to that well-ordering: in other words, an ordinal number is genuinely an equivalence class of well-ordered sets. This definition must be abandoned in ZF and related systems of axiomatic set theory because these equivalence classes are too large to form a set. However, this definition still can be used in type theory and in Quine's set theory New Foundations and related systems (where it affords a rather surprising alternative solution to the Burali-Forti paradox of the largest ordinal).

Von Neumann definition of ordinals

Rather than defining an ordinal as an equivalence class of well-ordered sets, we can try to define it as some particular well-ordered set which (canonically) represents the class. Thus, we want to construct ordinal numbers as special well-ordered sets in such a way that every well-ordered set is order-isomorphic to one and only one ordinal number.

The ingenious definition suggested by John von Neumann, and which is now taken as standard, is this: define each ordinal as a special well-ordered set, namely that of all ordinals before it. Formally:

A set S is an ordinal if and only if S is totally ordered with respect to set containment and every element of S is also a subset of S.

(Here, "set containment" is another name for the subset relationship.) Such a set S is automatically well-ordered with respect to set containment. This relies on the axiom of well foundation: every nonempty set S has an element a which is disjoint from S.

Note that the natural numbers are ordinals by this definition. For instance, 2 is an element of 4 = {0, 1, 2, 3}, and 2 is equal to {0, 1} and so it is a subset of {0, 1, 2, 3}.

It can be shown by transfinite induction that every well-ordered set is order-isomorphic to exactly one of these ordinals.

Furthermore, the elements of every ordinal are ordinals themselves. Whenever you have two ordinals S and T, S is an element of T if and only if S is a proper subset of T, and moreover, either S is an element of T, or T is an element of S, or they are equal. So every set of ordinals is totally ordered. And in fact, much more is true: Every set of ordinals is well-ordered. This important result generalizes the fact that every set of natural numbers is well-ordered and it allows us to use transfinite induction liberally with ordinals.

Another consequence is that every ordinal S is a set having as elements precisely the ordinals smaller than S. This statement completely determines the set-theoretic structure of every ordinal in terms of other ordinals. It's used to prove many other useful results about ordinals. One example of these is an important characterization of the order relation between ordinals: every set of ordinals has a supremum, the ordinal obtained by taking the union of all the ordinals in the set. Another example is the fact that the collection of all ordinals is not a set. Indeed, since every ordinal contains only other ordinals, it follows that every member of the collection of all ordinals is also its subset. Thus, if that collection were a set, it would have to be an ordinal itself by definition; then it would be its own member, which contradicts the axiom of regularity. (See also the Burali-Forti paradox). The class of all ordinals is variously called "Ord", "ON", or "∞".

An ordinal is finite if and only if the opposite order is also well-ordered, which is the case if and only if each of its subsets has a greatest element.

Other definitions

There are other modern formulations of the definition of ordinal. Each of these is essentially equivalent to the definition given above. One of these definitions is the following. A class S is called transitive if each element x of S is a subset of S, i.e. $y\in x\in S\Longrightarrow y\in S$. An ordinal is then defined to be a transitive set whose members are also transitive. It follows from this that the members are themselves ordinals. Note that the axiom of regularity (foundation) is used in showing that these ordinals are well ordered by containment (subset).

Transfinite induction

What is transfinite induction?

Transfinite induction holds in any well-ordered set, but it is so important in relation to ordinals that it is worth restating here.

Any property which passes from the set of ordinals smaller than a given ordinal α to α itself, is true of all ordinals.

That is, if P(α) is true whenever P(β) is true for all β<α, then P(α) is true for all α. Or, more practically: in order to prove a property P for all ordinals α, one can assume that it is already known for all smaller β<α.

Transfinite recursion

Transfinite induction can be used not only to prove things, but also to define them (such a definition is normally said to follow by transfinite recursion - we use transfinite induction to prove that the result is well-defined): the formal statement is tedious to write, but the bottom line is, in order to define a (class) function on the ordinals α, one can assume that it is already defined for all smaller β<α. One proves by transfinite induction that there is one and only one function satisfying the recursion formula upto and including α.

Here is an example of definition by transfinite induction on the ordinals (more will be given later): define a function F by letting F(α) be the smallest ordinal not in the set of F(β) for all β<α. Note how we assume the F(β) known in the very process of defining F: this apparent paradox is exactly what definition by transfinite induction permits. Now in fact F(0) makes sense since there is no β<0, so the set of all F(β) for β<0 is empty, so F(0) must be 0 (the smallest ordinal of all), and now that we know F(0), then F(1) makes sense (and it is the smallest ordinal not equal to F(0)=0), and so on (the and so on is exactly transfinite induction). Well, it turns out that this example is not very interesting since F(α)=α for all ordinals α: but this can be shown, precisely, by transfinite induction.

Successor and limit ordinals

Any nonzero ordinal has a smallest element (which is zero). It may or may not have a largest element, however: 42 or ω+6 have a largest element, whereas ω does not (there is no largest natural number). If an ordinal has a largest element α, then it is the next ordinal after α, and it is called a successor ordinal, namely the successor of α, written α+1. In the von Neumann definition of ordinals, the successor of α is $\alpha \cup \{\alpha \}$ since its elements are those of α and α itself.

A nonzero ordinal which is not a successor is called a limit ordinal. One justification for this term is that a limit ordinal is indeed the limit in a topological sense of all smaller ordinals (for the order topology).

Quite generally, when (α_ι<γ) is a sequence of ordinals (a family indexed by a limit γ), and if we assume that (α_ι) is increasing (α_ι<α_ι′ whenever ι<ι′), or at any rate non-decreasing, we define its limit to be the least upper bound of the set {α_ι}, that is, the smallest ordinal (it always exists) greater than any term of the sequence. In this sense, a limit ordinal is the limit of all smaller ordinals (indexed by itself).

Thus, every ordinal is either zero, or a successor (of a well-defined predecessor), or a limit. This distinction is important, because many definitions by transfinite induction rely upon it. Very often, when defining a function F by transfinite induction on all ordinals, one defines F(0), and F(α+1) assuming F(α) is defined, and then, for limit ordinals δ one defines F(δ) as the limit of the F(β) for all β<δ (either in the sense of ordinal limits, as we have just explained, or for some other notion of limit if F does not take ordinal values). Thus, the interesting step in the definition is the successor step, not the limit ordinals. Such functions (especially for F nondecreasing and taking ordinal values) are called continuous. We will see that ordinal addition, multiplication and exponentiation are continuous as functions of their second argument.

Indexing classes of ordinals

We have mentioned that any well-ordered set is similar (order-isomorphic) to a unique ordinal number $\alpha$, or, on other words, that its elements can be indexed in increasing fashion by the ordinals less than $\alpha$. This applies, in particular, to any set of ordinals: any set of ordinals is naturally indexed by the ordinals less than some $\alpha$. The same holds, with a slight modification, for classes of ordinals (a collection of ordinals, possibly too large to form a set, defined by some property): any class of ordinals can be indexed by ordinals (and, when the class is unbounded, this puts it in class-bijection with the class of all ordinals). So we can freely speak of the $\gamma$-th element in the class (with the convention that the “0-th” is the smallest, the “1-th” is the next smallest, and so on). Formally, the definition is by transfinite induction: the $\gamma$-th element of the class is defined (provided it has already been defined for all $\beta <\gamma$), as the smallest element greater than the $\beta$-th element for all $\beta <\gamma$.

We can apply this, for example, to the class of limit ordinals: the $\gamma$-th ordinal which is either a limit or zero is $\omega \cdot \gamma$ (so far we have not defined multiplication but we can take this notation as a temporary definition, which will agree with the general notion to be defined later). Similarly, we can consider ordinals which are additively indecomposable (meaning that it is a nonzero ordinal which is not the sum of two strictly smaller ordinals): the $\gamma$-th additively indecomposable ordinal is indexed as $\omega ^{\gamma }$. The technique of indexing classes of ordinals is often useful in the context of fixed points: for example, the $\gamma$-th ordinal such that $\omega ^{\alpha }=\alpha$ is written $\varepsilon _{\gamma }$.

Closed unbounded sets and classes

A class of ordinals is said to be unbounded, or cofinal, when given any ordinal, there is always some element of the class greater than it (then the class must be a proper class, i.e., it cannot be a set). It is said to be closed when the limit of a sequence of ordinals in the class is again in the class: or, equivalently, when the indexing (class-)function $F$ is continuous in the sense that, for $\delta$ a limit ordinal, $F(\delta )$ (the $\delta$-th ordinal in the class) is the limit of all $F(\gamma )$ for $\gamma <\delta$; this is also the same as being closed, in the topological sense, for the order topology (to avoid talking of topology on proper classes, one can demand that the intersection of the class with any given ordinal is closed for the order topology on that ordinal, this is again equivalent).

Of particular importance are those classes of ordinals which are closed and unbounded, sometimes called clubs. For example, the class of all limit ordinals is closed and unbounded: this translates the fact that there is always a limit ordinal greater than a given ordinal, and that a limit of limit ordinals is a limit ordinal (a fortunate fact if the terminology is to make any sense at all!). The class of additively indecomposable ordinals, or the class of $\varepsilon _{\cdot }$ ordinals, or the class of cardinals, are all closed unbounded; the set of regular cardinals, however, is unbounded but not closed, and any finite set of ordinals is closed but not unbounded.

A class is stationary if it has a nonempty intersection with every closed unbounded class. All superclasses of closed unbounded classes are stationary and stationary classes are unbounded, but there are stationary classes which are not closed and there are stationary classes which have no closed unbounded subclass (such as the class of all limit ordinals with countable cofinality). Since the intersection of two closed unbounded classes is closed and unbounded, the intersection of a stationary class and a closed unbounded class is stationary. But the intersection of two stationary classes may be empty, e.g. the class of ordinals with cofinality ω with the class of ordinals with uncountable cofinality.

Rather than formulating these definitions for (proper) classes of ordinals, we can formulate them for sets of ordinals below a given ordinal $\alpha$: A subset of a limit ordinal $\alpha$ is said to be unbounded (or cofinal) under $\alpha$ provided any ordinal less than $\alpha$ is less than some ordinal in the set. More generally, we can call a subset of any ordinal $\alpha$ cofinal in $\alpha$ provided every ordinal less than $\alpha$ is less than or equal to some ordinal in the set. The subset is said to be closed under $\alpha$ provided it is closed for the order topology in $\alpha$, i.e. a limit of ordinals in the set is either in the set or equal to $\alpha$ itself.

Arithmetic of ordinals

There are three usual operations on ordinals: addition, multiplication, and (ordinal) exponentiation. Each can be defined in essentially two different ways: either by constructing an explicit well-ordered set which represents the operation or by using transfinite recursion. The Cantor normal form provides a standardized way of writing ordinals. The so-called "natural" arithmetical operations retain commutivity at the expense of continuity.

Ordinals and cardinals

Initial ordinal of a cardinal

Each ordinal has an associated cardinal, its cardinality, obtained by simply forgetting the order. Any well-ordered set having that ordinal as its order-type has the same cardinality. The smallest ordinal having a given cardinal as its cardinality is called the initial ordinal of that cardinal. Every finite ordinal (natural number) is initial, but most infinite ordinals are not initial. The axiom of choice is equivalent to the statement that every set can be well-ordered, i.e. that every cardinal has an initial ordinal. In this case, it is traditional to identify the cardinal number with its initial ordinal, and we say that the initial ordinal is a cardinal.

The α-th infinite initial ordinal is written $\omega _{\alpha }$. Its cardinality is written $\aleph _{\alpha }$. For example, the cardinality of ω₀ = ω is $\aleph _{0}$, which is also the cardinality of ω² or ε₀ (all are countable ordinals). So (assuming the axiom of choice) we identify ω with $\aleph _{0}$, except that the notation $\aleph _{0}$ is used when writing cardinals, and ω when writing ordinals (this is important since $\aleph _{0}^{2}=\aleph _{0}$ whereas $\omega ^{2}>\omega$). Also, $\omega _{1}$ is the smallest uncountable ordinal (to see that it exists, consider the set of equivalence classes of well-orderings of the natural numbers: each such well-ordering defines a countable ordinal, and $\omega _{1}$ is the order type of that set), $\omega _{2}$ is the smallest ordinal whose cardinality is greater than $\aleph _{1}$, and so on, and $\omega _{\omega }$ is the limit of the $\omega _{n}$ for natural numbers n (any limit of cardinals is a cardinal, so this limit is indeed the first cardinal after all the $\omega _{n}$).

Cofinality

The cofinality of an ordinal $\alpha$ is the smallest ordinal $\delta$ which is the order type of a cofinal subset of $\alpha$. Notice that a number of authors define confinality or use it only for limit ordinals. The cofinality of a set of ordinals or any other well ordered set is the cofinality of the order type of that set.

Thus for a limit ordinal, there exists a $\delta$-indexed strictly increasing sequence with limit $\alpha$. For example, the cofinality of ω² is ω, because the sequence ω·m (where m ranges over the natural numbers) tends to ω²; but, more generally, any countable limit ordinal has cofinality ω. An uncountable limit ordinal may have either cofinality ω as does $\omega _{\omega }$ or an uncountable cofinality.

The cofinality of 0 is 0. And the cofinality of any successor ordinal is 1. The cofinality of any limit ordinal is at least $\omega$.

An ordinal which is equal to its cofinality is called regular and it is always an initial ordinal. Any limit of regular ordinals is a limit of initial ordinals and thus is also initial even if it is not regular which it usually is not. If the Axiom of Choice, then $\omega _{\alpha +1}$ is regular for each α. In this case, the ordinals 0, 1, $\omega$, $\omega _{1}$, and $\omega _{2}$ are regular, whereas 2, 3, $\omega _{\omega }$, and ω_ω·2 are initial ordinals which are not regular.

The cofinality of any ordinal α is a regular ordinal, i.e. the cofinality of the cofinality of α is the same as the cofinality of α. So the cofinality operation is idempotent.

Some “large” countable ordinals

We have already mentioned the ordinal ε₀, which is the smallest satisfying the equation $\omega ^{\alpha }=\alpha$, so it is the limit of the sequence 0, 1, $\omega$, $\omega ^{\omega }$, $\omega ^{\omega ^{\omega }}$, etc. Many ordinals can be defined in such a manner as fixed points of certain ordinal functions (the $\iota$-th ordinal such that $\omega ^{\alpha }=\alpha$ is called $\varepsilon _{\iota }$, then we could go on trying to find the $\iota$-th ordinal such that $\varepsilon _{\alpha }=\alpha$, “and so on”, but all the subtlety lies in the “and so on”). We can try to do this systematically, but no matter what system is used to define and construct ordinals, there is always an ordinal that lies just above all the ordinals constructed by the system. Perhaps the most important ordinal which limits in this manner a system of construction is the Church-Kleene ordinal, $\omega _{1}^{\mathrm {CK} }$ (despite the $\omega _{1}$ in the name, this ordinal is countable), which is the smallest ordinal which cannot in any way be represented by a computable function (this can be made rigorous, of course). Considerably large ordinals can be defined below $\omega _{1}^{\mathrm {CK} }$, however, which measure the “proof-theoretic strength” of certain formal systems (for example, $\varepsilon _{0}$ measures the strength of Peano arithmetic). Large ordinals can also be defined above the Church-Kleene ordinal, which are of interest in various parts of logic.

Topology and ordinals

Ordinals as topological spaces

Any ordinal can be made into a topological space by endowing it with the order topology (since, being well-ordered, an ordinal is in particular totally ordered): in the absence of indication to the contrary, it is always that order topology which is meant when an ordinal is thought of as a topological space. (Note that if we are willing to accept a proper class as a topological space, then the class of all ordinals is also a topological space for the order topology.)

The set of limit points of an ordinal α is precisely the set of limit ordinals less than α. Successor ordinals (and zero) less than α are isolated points in α. In particular, the finite ordinals and ω are discrete topological spaces, and no ordinal beyond that is discrete. The ordinal α is compact as a topological space if and only if α is a successor ordinal.

The closed sets of a limit ordinal α are just the closed sets in the sense that we have already defined, namely, those which contain a limit ordinal whenever they contain all sufficiently large ordinals below it.

Any ordinal is, of course, an open subset of any further ordinal. We can also define the topology on the ordinals in the following inductive way: 0 is the empty topological space, α+1 is obtained by taking the one-point compactification of α (if α is a limit ordinal; if it is not, α+1 is merely the disjoint union of α and a point), and for δ a limit ordinal, δ is equipped with the inductive limit topology.

As topological spaces, all the ordinals are Hausdorff and even normal. They are also totally disconnected (connected components are points), scattered (=every non-empty set has an isolated point; in this case, just take the smallest element), zero-dimensional (=the topology has a clopen basis: here, write an open interval (β,γ) as the union of the clopen intervals (β,γ'+1)=[β+1,γ'] for γ'<γ). However, they are not extremally disconnected in general (there is an open set, namely ω, whose closure is not open).

The topological spaces ω₁ and its successor ω₁+1 are frequently used as text-book examples of non-countable topological spaces. For example, in the topological space ω₁+1, the element ω₁ is in the closure of the subset ω₁ even though no sequence of elements in ω₁ has the element ω₁ as its limit. The space ω₁ is first-countable, but not second-countable, and ω₁+1 has neither of these two properties, despite being compact. It is also worthy of note that any continuous function from ω₁ to R (the real line) is eventually constant: so the Stone-Čech compactification of ω₁ is ω₁+1, just as its one-point compactification (in sharp contrast to ω, whose Stone-Čech compactification is much larger than ω₁).

Ordinal-indexed sequences

If α is a limit ordinal and X is a set, an α-indexed sequence of elements of X merely means a function from α to X. If X is a topological space, we say that an α-indexed sequence of elements of X converges to a limit x when it converges as a net, in other words, when given any neighborhood U of x there is an ordinal β<α such that x_ι is in U for all ι≥β. This coincides with the notion of limit defined above for increasing ordinal-indexed sequences in an ordinal.

Ordinal-indexed sequences are more powerful than ordinary (ω-indexed) sequences to determine limits in topology: for example, ω₁ is a limit point of ω₁+1 (because it is a limit ordinal), and, indeed, it is the limit of the ω₁-indexed sequence which maps any ordinal less than ω₁ to itself: however, it is not the limit of any ordinary (ω-indexed) sequence in ω₁, since any function from the natural numbers to ω₁ is bounded. However, ordinal-indexed sequences are not powerful enough to replace nets (or filters) in general: for example, on the Tychonoff plank (the product space $(\omega _{1}+1)\times (\omega +1)$), the corner point $(\omega _{1},\omega )$ is a limit point (it is in the closure) of the open subset $\omega _{1}\times \omega$, but it is not the limit of an ordinal-indexed sequence.

See also

• successor ordinal
• limit ordinal
• ordinal arithmetic
• large countable ordinals
• cardinal number

References

• Conway, J. H. and Guy, R. K. "Cantor's Ordinal Numbers." In The Book of Numbers. New York: Springer-Verlag, pp. 266-267 and 274, 1996.
• Sierpinski, W. (1965). Cardinal and Ordinal Numbers (2nd ed.). Warszawa: Pantswowe Wydawnictwo Naukowe. Also defines ordinal operations in terms of the Cantor Normal Form.
• Patrick Suppes, Axiomatic Set Theory, D.Van Nostrand Company Inc., 1960

it:Numero ordinale