# Numero cardinale

In matematica, i numeri cardinali sono una generalizzazione dei numeri naturali e sono utilizzati per indicare la grandezza di un insieme. Mentre per gli insiemi finiti la grandezza è indicata da un numero naturale, e cioè il numero di elementi, i numeri cardinali (la cardinalità) classificano oltre a questi anche diversi tipi di infinito.
Da un lato è possibile che un sottoinsieme proprio di un insieme infinito abbia la stessa cardinalità dell'insieme che lo contiene, d'altra parte non è detto che tutti gli insiemi infiniti abbiano la stessa grandezza. Esiste una caratterizzazione formale di come alcuni insiemi infiniti siano più piccoli di altri insiemi infiniti. Il concetto di cardinalità è utilizzato in molte branche della matematica, ed è anche studiato nella teoria degli insiemi, particolarmente per descrivere le proprietà dei grandi cardinali.

## Storia

I numeri cardinali furono definiti da Georg Cantor mentre stava sviluppando la teoria degli insiemi oggi chiamata teoria ingenua degli insiemi nel periodo 1874–1884.
Inizialmente definì il concetto di cardinalità come strumento per confrontare insiemi finiti; per esempio, gli insiemi ${1,2,3}$ e ${2,3,4}$ non sono uguali, ma hanno la stessa cardinalità, e cioè tre.
Cantor utilizzò il concetto di corrispondenza biunivoca per mostrare che due insiemi finiti hanno la stessa cardinalità se esiste una corrispondenza biunivoca tra i loro elementi. In seguito trasferì il concetto agli insiemi infiniti, come per esempio l'insieme dei numeri naturali $\mathbb {N} =\{1,2,3,\dots \}$. Chiamò questi numeri cardinali numeri cardinali transfiniti, e definì insiemi numerabili tutti gli insiemi in corrispondenza biunivoca con $\mathbb {N}$.
Al numero cardinale transfinito che corrisponde alla cardinalità di $\mathbb {N}$ Cantor diede il nome di $\aleph _{0}$ (aleph zero; aleph è la prima lettera dell'alfabeto ebraico). Inoltre dimostrò il fatto, non intuitivo, che alcuni sottoinsiemi di $\mathbb {N}$ (quelli infiniti) hanno la stessa cardinalità di $\mathbb {N}$ stesso. Provò inoltre che l'insieme di tutte le coppie ordinate (e quindi, per biettività, anche l'insieme $\mathbb {Q}$ dei razionali) di numeri naturali è numerabile, e in seguito che l'insieme di tutti i numeri algebrici lo è.
A questo punto, nel 1874, si chiese se tutti gli insiemi infiniti fossero numerabili, rendendo così di poca utilità la definizione di cardinalità. Invece Cantor riuscì a dimostrare che esistono numeri cardinali più grandi utilizzando una tecnica che ha preso il nome di argomento diagonale di Cantor. Il primo numero cardinale maggiore di $\aleph _{0}$ scoperto da Cantor venne indicato con ${\mathfrak {c}}$ e chiamato cardinalità del continuo.
Cantor sviluppò poi una teoria generale dei numeri cardinali, dimostrando che $\aleph _{0}$ è il più piccolo numero cardinale transfinito, e che per ogni numero cardinale ne esiste uno più grande ($\aleph _{1},\aleph _{2},\aleph _{3},\dots$).
La successiva ipotesi del continuo suggerì che ${\mathfrak {c}}$ è lo stesso numero indicato da $\aleph _{1}$; in seguito venne dimostrato che questa ipotesi è indipendente dagli assiomi standard della teoria degli insiemi: essa non può essere dimostrata né contraddetta utilizzando gli assiomi standard.

## Motivazioni per l'uso dei numeri cardinali

Nell'uso non rigoroso, un numero cardinale è ciò che serve per contare. I numeri cardinali vengono identificati con i numeri naturali, a partire da 0. I numeri naturali sono esattamente ciò che viene definito in modo formale come i numeri cardinali finiti. I cardinali infiniti vengono usati soltanto nella matematica di livello più alto e nella logica.
In modo più formale si può dire che un numero può essere usato per due scopi differenti: per descrivere la grandezza di un insieme, o per descrivere la posizione di un elemento in una successione. Per insiemi e successioni finite è facile vedere che queste due nozioni coincidono, dato che per ogni numero che descrive una posizione in una successione si può costruire un insieme che ha esattamente quella grandezza. Per esempio, 3 descrive la posizione di $c$ nella successione $<a,b,c,d,\dots >$, e si può costruire l'insieme $\{a,b,c\}$ che ha 3 elementi. Però quando si ha a che fare con insiemi infiniti è necessario distinguere tra i due concetti, che per insiemi infiniti sono effettivamente diversi. L'aspetto della posizione in una successione porta al concetto di numero ordinale, mentre l'aspetto della grandezza di un insieme è generalizzato dai numeri cardinali descritti qui.
L'intuizione che sta dietro alla definizione formale di cardinale consiste nella definizione di "grandezza" di un insieme senza però fare riferimento al tipo di elementi che l'insieme contiene. Per gli insiemi finiti è facile, basta semplicemente contare gli elementi di un insieme uno dopo l'altro. Ma per confrontare le dimensioni di insiemi più grossi occorre fare uso di nozioni più sottili.
Un insieme $Y$ è almeno grande quanto un insieme $X$ se esiste una funzione iniettiva dagli elementi di $X$ agli elementi di $Y$, in questo modo ogni elemento di $X$ viene identificato con un unico elemento di $Y$. Per esempio, supponiamo di avere gli insiemi $X=\{1,2,3\}$ e $Y=\{a,b,c,d\}$; osserviamo che esiste una funzione
    ${\begin{aligned}1&\mapsto a\\2&\mapsto b\\3&\mapsto c\end{aligned}}$
che è iniettiva, e quindi possiamo concludere che $Y$ ha cardinalità maggiore o uguale di $X$. Si noti che l'elemento $d$ non ha corrispondente nel primo insieme, ma questo fatto è permesso dal fatto che la funzione è solo iniettiva e non anche suriettiva. Il vantaggio di questa definizione consiste nel fatto che essa può essere estesa agli insiemi infiniti.
Questa definizione può essere modificata per renderla una relazione di equivalenza.
Due insiemi $X$ e $Y$ hanno la stessa cardinalità se esiste una funzione biunivoca tra $X$ e $Y$, oppure se esistono sia una funzione iniettiva da $X$ a $Y$ e una funzione iniettiva da $Y$ a $X$. In tal caso, si scrive $|X|=|Y|$. Il numero cardinale di $X$ spesso è definito come il minore numero ordinale $a$ tale che $|a|=|X|$. Questa procedura viene chiamata assegnazione cardinale di von Neumann. Perché questa definizione abbia senso, deve essere dimostrato che ogni insieme ha la stessa cardinalità di un qualche ordinale: questa affermazione è il teorema del buon ordinamento. È comunque possibile parlare della cardinalità relativa di insiemi senza assegnare esplicitamente dei nomi agli oggetti in questione.
L'esempio classico che viene fatto di solito è quello del paradosso dell'albergo infinito, anche chiamato paradosso del Grand Hotel di Hilbert. Si immagini che esista un albergo con un numero infinito di stanze. L'albergo è pieno, e arriva un nuovo ospite. È possibile trovare un posto per il nuovo arrivato chiedendo a chi occupa la stanza numero 1 di spostarsi nella numero 2, a chi occupa la numero 2 di spostarsi nella numero 3, e così via. Viene così lasciata libera la stanza numero 1. Si può scrivere esplicitamente una parte di questa funzione:
    ${\begin{aligned}1&\leftrightarrow 2\\2&\leftrightarrow 3\\3&\leftrightarrow 4\\&\dots \\n&\leftrightarrow n+1\\&\dots \end{aligned}}$
In questo modo si vede che l'insieme $\{1,2,3,\dots \}$ ha la stessa cardinalità dell'insieme $\{2,3,4,\dots \}$, dato che è stata mostrata un'applicazione biunivoca tra il primo e il secondo insieme. Questo motiva la definizione di insieme infinito come insieme che possiede un sottoinsieme proprio con la stessa cardinalità: in questo caso $\{2,3,4,\dots \}$ è un sottoinsieme proprio di $\{1,2,3,\dots \}$.
Quando si considerano questi oggetti così grandi si vuole anche vedere se la nozione di "counting order" coincide con quella di cardinale. In effetti, no. Considerando l'esempio precedente dell'albergo infinito si può vedere che se esiste un oggetto "infinito più uno" allora esso deve avere la stessa cardinalità dell'insieme infinito dal quale si è partiti. Si può usare una nozione differente di numero, chiamata numero ordinale, basata sull'idea di contare i numeri uno dopo l'altro, e si vede che le due nozioni sono diverse quando si passa ai numeri infiniti.
Si può dimostrare che la cardinalità dei numeri reali è maggiore di quella dei numeri naturali. Questo fatto può essere visualizzato grazie all'argomento diagonale di Cantor. Problemi classici nello studio della cardinalità (per esempio l'ipotesi del continuo) hanno a che fare con la possibilità che esista qualche cardinale compreso tra una coppia di altri cardinali infiniti. Nei tempi recenti i matematici hanno iniziato a descrivere le proprietà di cardinali sempre più grandi.
Poiché la cardinalità è un concetto molto comune in matematica, per esso vengono usati molti nomi diversi, come equipotenza, equipollenza o equinumerosità. Si dice quindi che due insiemi con la stessa cardinalità sono equipotenti, equipollenti o equinumerosi.

## Definizione formale

La definizione di cardinale viene solitamente data appoggiandosi a due concetti base:
* il concetto di numero ordinale;
* la relazione d'ordine $|\cdot |\leq |\cdot |$, definita come $|A|\leq |B|\iff \exists f:A\rightarrow B$ iniettiva
Il teorema di Cantor-Bernstein-Schroeder afferma che se $|X|\leq |Y|,|Y|\leq |X|\Rightarrow |X|=|Y|$, ovvero esiste una funzione bigettiva tra $X$ e $Y$, e ci garantisce quindi che $|\cdot |\leq |\cdot |$ è effettivamente una relazione d'ordine. Supponendo vero l'assioma della scelta otteniamo poi che dati due insiemi $X$ e $Y$, vale sempre $|X|\leq |Y|$ o $|Y|\leq |X|$, ovvero la relazione d'ordine è totale.
A questo punto definiamo numero cardinale ogni ordinale iniziale, ovvero ogni ordinale $\alpha$ tale che:
$\forall \beta {\text{ ordinale}},\beta <\alpha \Rightarrow |\beta |<|\alpha |$
Osserviamo che il primo "$<$" che compare è l'ordine indotto sugli ordinali, ovvero la semplice inclusione.
Si verifica facilmente che dati due ordinali iniziali $\alpha ,\beta$, si ha che, se $\alpha >\beta$ oppure $\beta >\alpha$, non vale $|\alpha |=|\beta |$. Infatti se così non fosse avremmo, ad esempio, che $\alpha >\beta$ (il caso opposto è identico) ma $|\alpha |=|\beta |$, e quindi $\alpha$ non è un ordinale iniziale.
Supponendo valido l'assioma della scelta, chiamiamo poi cardinalità di un insieme $X$, e denotiamo con $|X|$, il cardinale (l'unico) $k$ tale che esista una bigezione tra $X$ e $k$.
A questo punto possiamo vedere la relazione $|\cdot |\leq |\cdot |$ come una semplice relazione $\leq$ tra cardinali.
Se l'assioma della scelta non viene invece ritenuto valido e $X$ non possiede un buon ordinamento, la cardinalità di $X$ viene solitamente definita come l'insieme di tutti gli insiemi che sono equipotenti a $X$ e hanno il minor rango che un insieme equipotente con $X$ possa avere (questo è un trucco dovuto a Dana Scott: funziona perché la collezione di oggetti aventi un dato rango è un insieme). La più antica definizione di cardinalità di un insieme $X$ (implicita in Cantor ed esplicita in Frege e nei Principia Mathematica) è l'insieme di tutti gli insiemi che sono equipotenti a $X$: non funziona in ZFC o altri sistemi simili della teoria assiomatica degli insiemi perché questa collezione è troppo grande per essere un insieme, ma funziona nella teoria dei tipi, nella teoria New Foundations e nei sistemi ad esse relativi.
Un insieme $X$ è infinito, o equivalentemente il suo cardinale è infinito, se esiste un sottoinsieme proprio $Y$ di $X$ tale che $|X|=|Y|$. Un cardinale che non è infinito viene detto finito; si può dimostrare che i cardinali finiti sono i numeri naturali, cioè che un insieme $X$ è finito se e solo se $|X|=|n|=n$ per qualche numero naturale $n$.

## Numeri aleph

Definiamo innanzitutto la Funzione-Classe di Hartogs, che è definita in questo modo:
${\begin{matrix}\ H:V\longrightarrow ORD\\a\longmapsto \alpha \end{matrix}}$
sulla classe propria universale di tutti gli insiemi $V$ in $ORD$ la classe propria di tutti gli ordinali tale che ad ogni insieme $a$ associa l'insieme $\alpha =min\{\beta {\text{ ordinale }}\mid |\beta |>|a|\}$.
(ricordiamo che con l'assiomatizzazione GB le classi si indicano con le lettere maiuscole e gli insiemi con le minuscole).
Si dimostra che l'immagine di H è la classe propria dei cardinali, quindi è possibile ora definire tutti i cardinali infiniti facendo uso dei numeri ordinali per induzione transfinita:
${\begin{cases}\aleph _{0}=\omega \\\aleph _{\alpha +1}=H(\aleph _{\alpha })\\\aleph _{\lambda }=\bigcup _{\gamma \in \lambda }\aleph _{\gamma }\qquad {\mbox{con }}\lambda {\mbox{ limite}}\end{cases}}$

### Cardinali successori e cardinali limite

Chiameremo cardinale successore un qualsiasi cardinale $\aleph _{\alpha }$ tale che esista un ordinale $\beta$ per cui $\aleph _{\alpha }=\aleph _{\beta +1}$ e cardinale limite un qualsiasi cardinale $\aleph _{\lambda }$ con $\lambda$ ordinale limite.
Un cardinale successore non è un ordinale successore; tutti i cardinali sono infatti ordinali limiti. Un cardinale successore è immagine attraverso la funzione $\aleph$ di un ordinale successore.
Si dimostra che la funzione $\aleph$ è iniettiva e suriettiva. Ovviamente non è una funzione vera e propria nella teoria degli insiemi di Zermelo-Fraenkel, dato che le famiglie dei cardinali e degli ordinali costituiscono due classi proprie; è solitamente detta una funzione classe, nel senso che soddisfa il requisito
    $\forall x\ \exists !\ y\colon \ \aleph _{x}=y.$
L'iniettività e la surgettività si possono vedere come iniettività e surgettività su ogni segmento iniziale della famiglia degli ordinali e di quella dei cardinali.

## Aritmetica dei cardinali

Si possono definire delle operazioni aritmetiche sui numeri cardinali che generalizzano le operazioni ordinarie sui numeri naturali. Se X e Y sono disgiunti, allora l'addizione è data dall'unione di $X$ e $Y$:
    $|X|+|Y|=|X\cup Y|.$
Il prodotto di numeri cardinali è dato dal prodotto cartesiano:
    $|X|\cdot |Y|=|X\times Y|.$
La potenza è data da
    $|X|^{|Y|}=|X^{Y}|$
dove $X^{Y}$ è definito come l'insieme di tutte le funzioni da $Y$ a $X$. Si può dimostrare che per cardinali finiti queste operazioni coincidono con le usuali operazioni sui numeri naturali. Inoltre, queste operazioni condividono molte proprietà con l'aritmetica ordinaria:
* l'addizione e la moltiplicazione di numeri cardinali sono associative e commutative;
* la moltiplicazione è distributiva sull'addizione;
* $|X|^{|Y|+|Z|}=|X|^{|Y|}\cdot |X|^{|Z|}$;
* $|X|^{|Y|\cdot |Z|}=\left(|X|^{|Y|}\right)^{|Z|}$;
* $(|X|\cdot |Y|)^{|Z|}=|X|^{|Z|}\cdot |Y|^{|Z|}$.
L'addizione e la moltiplicazione di cardinali infiniti (supponendo valido l'assioma della scelta) sono semplici: se $X$ o $Y$ sono infiniti ed entrambi sono non vuoti, allora
    $|X|+|Y|=|X|\cdot |Y|=\max\{|X|,|Y|\}.$
Questo concorda con il risultato raggiunto da Cantor che afferma che, ad esempio, il prodotto cartesiano di $\mathbb {N}$ (di cardinalità $\aleph _{0}$) con sé stesso è ancora $\aleph _{0}$.
Si noti che $2^{|X|}$ è la cardinalità dell'insieme potenza dell'insieme $X$ e l'argomento diagonale di Cantor dimostra che $2^{|X|}>|X|$ per ogni insieme $X$. Ciò dimostra che non esiste un cardinale più grande di tutti gli altri. In effetti, la classe di tutti i cardinali è una classe propria.
Esistono ulteriori regole per la potenza:
* $|X|^{0}=1$ (in particolare $0^{0}=1$), si veda la funzione vuota;
* $0^{|Y|}=0$ se $Y$ non è vuoto;
* $1^{|Y|}=1$;
* $|X|\leq |Y|$ implica che $|X|^{|Z|}\leq |Y|^{|Z|}$:
* se $|X|$ e $|Y|$ sono entrambi finiti e maggiori di $1$, e $Z$ è infinito, allora $|X|^{|Z|}=|Y|^{|Z|}$;
* se $X$ è infinito e $Y$ è finito e non vuoto allora $|X|^{|Y|}=|X|$.

## L'ipotesi del continuo

L'ipotesi del continuo (continuum hypothesis, abbreviato con CH) afferma che non esistono cardinali strettamente compresi tra $\aleph _{0}$ e $2^{\aleph _{0}}$. Il cardinale $2^{\aleph _{0}}$ è spesso indicato con ${\mathfrak {c}}$; è la cardinalità del continuo (l'insieme dei numeri reali). In questo caso $2^{\aleph _{0}}=\aleph _{1}$. L'ipotesi del continuo generalizzata (GCH) afferma che per ogni insieme infinito $X$ non esistono cardinali strettamente compresi tra $|X|$ e $2^{|X|}$. L'ipotesi del continuo è indipendente dagli assiomi usuali della teoria degli insiemi, cioè dagli assiomi di Zermelo - Fraenkel con l'assioma della scelta (ZFC).