# Numero ordinale (teoria degli insiemi)

In matematica, i numeri ordinali costituiscono un'estensione dei numeri naturali che tiene conto anche di successioni infinite, introdotta da Georg Cantor nel 1897.

## 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.
Nella teoria degli insiemi, i numeri ordinali sono solitamente costruiti come insiemi, in modo tale che ogni numero ordinale è l'insieme di tutti i numeri ordinali 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 ordinale è 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 ordinale è 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 ordinale. Questo fatto fornisce la motivazione che porta alla generalizzazione dei numeri infiniti.

## Dal finito al "transfinito"

Abbiamo visto come è possibile costruire tutti i numeri ordinali 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 ordinali è dotato naturalmente di una struttura di insieme ben ordinato e al contempo tutti questi numeri ordinali 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 quelli che Cantor ha chiamato ordinali transfiniti. Consideriamo l'insieme ordinato di tutti gli insiemi definiti finora - cioè i numeri ordinali - e lo chiamiamo ω:
    ω:={0,1,2,3,...}
Omega è anch'esso naturalmente dotato di una struttura 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 ordinali:
    ωx2=ω+ω:={0,1,2,3,...,ω,ω+1,ω+2,ω+3,...}
E si può andare avanti come prima considerando ad ogni passo l'insieme di tutti gli 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:
* 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$;
* 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
    ωx3:={0,1,2,3,...,ω,ω+1,ω+2,ω+3,...,ωx2, ωx2+1, ωx2+2, ωx2+3, ...}
    ωx4:={0,1,2,3,...,ω,ω+1,ω+2,ω+3,...,ωx2, ωx2+1, ωx2+2, ωx2+3, ...,ωx3, ωx3+1, ωx3+2, ωx3+3, ...}
    ωxn:={0,1,2,3,...,ω,ω+1,ω+2,ω+3,...,ωx2, ωx2+1, ωx2+2, ωx2+3, ...,ωx3, ωx3+1, ωx3+2, ωx3+3, ...,ωx(n-1),ωx(n-1)+1,ωx(n-1)+2,...}
    ω×ω=ω$^2$:={1,2,3,...,ω,...,ωx2,...,ωx3,...,ωxn,.........}

## 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 solo numero ordinale. La definizione seguente migliora l'approccio di Cantor e venne data per primo da John von Neumann:
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:
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 sé stesso, cosa che contraddice l'assioma di regolarità (si veda anche il paradosso di Burali-Forti).
Un ordinale è finito se e solo se l'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 questa 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 un'operazione associativa che generalizza la moltiplicazione tra numeri naturali.
Questo è ω2:
    0$_0$ < 1$_0$ < 2$_0$ < 3$_0$ < ... < 0$_1$ < 1$_1$ < 2$_1$ < 3$_1$ < ...
e si ha che: ω2 = ω + ω. Mentre 2ω ha questo aspetto:
    0$_0$ < 1$_0$ < 0$_1$ < 1$_1$ < 0$_2$ < 1$_2$ < 0$_3$ < 1$_3$ < ...
che, dopo una sostituzione, ha l'aspetto di ω quindi 2ω = ω. 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 quasi-anello sinistro: però gli ordinali non sono nemmeno un quasi-anello 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$ (si ha uguaglianza se e solo se $\alpha =\omega ^{\alpha }$, fatto possibile, come spiegato in seguito).
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 ε$_0$. Questo ordinale è molto importante in molte dimostrazioni per induzione, perché per molti scopi l'induzione transfinita è richiesta solo fino a ε$_0$. Si noti che $\varepsilon _{0}=\omega ^{\omega ^{\omega ^{\cdots }}}$, così $\varepsilon _{0}=\omega ^{\varepsilon _{0}}$. Un'altra formula è
    $\varepsilon _{0}=1+\omega +\omega ^{\omega }+\omega ^{\omega ^{\omega }}+\omega ^{\omega ^{\omega ^{\omega }}}+\dots$.
L'ordinale $\varepsilon _{0}$ è anche il primo numero che soddisfa l'equazione di Cantor $\omega ^{\varepsilon }=\varepsilon$. Questa equazione ha infinite soluzioni: la successiva è
    $\varepsilon _{1}=(\varepsilon _{0}+1)+\omega ^{\varepsilon _{0}+1}+\omega ^{\omega ^{\varepsilon _{0}+1}}+\omega ^{\omega ^{\omega ^{\varepsilon _{0}+1}}}+\dots$,
cui seguono
    $\varepsilon _{1},\varepsilon _{2},\dots ,\varepsilon _{\omega },\varepsilon _{\omega +1},\dots ,\varepsilon _{\omega 2},\dots ,\varepsilon _{\omega ^{2}},\dots ,\varepsilon _{\omega ^{\omega }},\dots ,\varepsilon _{\varepsilon _{0}},\dots ,\varepsilon _{\varepsilon _{0}+\omega },\dots ,\varepsilon _{\varepsilon _{0}+\omega ^{\omega }},\dots ,$
    $\varepsilon _{\varepsilon _{0}2},\dots ,\varepsilon _{\varepsilon _{1}},\dots ,\varepsilon _{\varepsilon _{2}},\dots ,\varepsilon _{\varepsilon _{\omega }},\dots ,\varepsilon _{\varepsilon _{\varepsilon _{0}}},\dots ,\varepsilon _{\varepsilon _{\varepsilon _{1}}},\dots ,\varepsilon _{\varepsilon _{\varepsilon _{\omega }}},\dots ,\varepsilon _{\varepsilon _{\varepsilon _{\varepsilon _{0}}}},\dots$
e così via fino a $\varepsilon _{\varepsilon _{\varepsilon _{\varepsilon _{\varepsilon _{\dots }}}}}$, che è la prima soluzione di $\varepsilon _{\alpha }=\alpha$.
$\varepsilon _{0}$ è ancora numerabile. Tuttavia ci si può convincere dell'esistenza di almeno un ordinale non numerabile ricordando che la collezione di tutti gli ordinali non è un insieme (Paradosso di Burali-Forti) mentre è possibile costruire l'insieme di tutti gli ordinali numerabili: sicché deve esistere almeno un ordinale non numerabile e si prova che il più piccolo ordinale non numerabile è proprio l'insieme di tutti gli ordinali numerabili, e solitamente viene indicato con ω$_1$.

## Topologia e ordinali limite

Gli ordinali sono dotati anche di un'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 ε$_0$. Gli ordinali che non hanno un antecedente possono sempre essere scritti come limite 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 ω$_1$ e il suo successore ω$_1$+1 sono spesso usati nei libri di testo come esempi di spazi topologici non numerabili. Per esempio, nello spazio topologico ω$_1$+1, l'elemento ω$_1$ è nella chiusura del sottoinsieme ω$_1$ anche se nessuna successione di elementi in ω$_1$ ha l'elemento ω$_1$ come limite. Lo spazio ω$_1$ è uno spazio primo numerabile, ma non secondo numerabile, e ω$_1$+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.