Numero ordinale (teoria degli insiemi)

Da Wikipedia, l'enciclopedia libera.
Se riscontri problemi nella visualizzazione dei caratteri, clicca qui.
Rappresentazione degli ordinali fino a ωω. Ogni spira rappresenta una potenza di ω

In matematica, i numeri ordinali costituiscono un'estensione dei numeri naturali che tiene conto anche di successioni infinite, introdotta da Georg Cantor nel 1897. Questa generalizzazione è l'oggetto della presente pagina.

Introduzione[modifica | modifica sorgente]

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 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"[modifica | modifica sorgente]

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

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 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:

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,...}
...
ω×ω=ω2:={1,2,3,...,ω,...,2ω,...,3ω,...,nω,.........}

La definizione originale[modifica | modifica sorgente]

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à[modifica | modifica sorgente]

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:

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 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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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 ST 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:

00 < 10 < 20 < 30 < ... < 01 < 11 < 21 < 31 < ...

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

00 < 10 < 01 < 11 < 02 < 12 < 03 < 13 < ...

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 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[modifica | modifica sorgente]

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\le\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_{\omega2},\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[modifica | modifica sorgente]

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 ε0. 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 ω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 first-countable, ma non second-countable, 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.

Voci correlate[modifica | modifica sorgente]

Bibliografia[modifica | modifica sorgente]

  • 1996 - Conway, J. H. e Guy, R. K. I numeri ordinali di Cantor. Ne Il libro dei Numeri. Hoepli, pp. 230–238 (ISBN 8820325195).
matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica