La cardinalità di un insieme è intuitivamente il numero di elementi che esso contiene. Per quanto riguarda gli insiemi finiti il discorso è molto semplice. Per gli insiemi infiniti – dal momento che risulta impossibile "contare" gli elementi al loro interno- si usa un metodo di confronto di ordini. Si possono infatti confrontare le cardinalità di due insiemi (in particolare quelli infiniti) utilizzando la seguente definizione. Due insiemi X e Y si dicono equipotenti– o della stessa cardinalità- se sono in corrispondenza biunivoca, ossia se esiste una funzione f da X a valori in Y che sia biiettiva. Una cardinalità molto importante – e che si è meritata il nome di ℵ0 (leggi "Alef 0", prima lettera dell'alfabeto ebraico) – è quella dell'insieme dei numeri naturali. Un insieme equipotente ai numeri naturali (quindi di cardinalità ℵ0) si dice numerabile. Gli insiemi numerabili (in inglese "countable") si chiamano così perché, in base alla definizione appena data, possono essere visti come l'insieme dei punti di un'opportuna successione. In ogni insieme numerabile si possono quindi ordinare gli elementi e definirne per ciascuno un successivo, in modo da poterli "contare".
Si può dimostrare (e lo faremo in seguito) che ogni insieme infinito contiene un sottoinsieme numerabile. Il ragionamento sembra essere controintuitivo se si pensa che si possono trovare insiemi infiniti strettamente contenuti nell'insieme dei numeri naturali e che quindi paiono contenere un minor numero di elementi.
Formalizziamo ora meglio il concetto di insieme infinito. Un insieme X si dice infinito se è equipotente a un suo sottoinsieme proprio: ossia se esistono un sottoinsieme A di X, con A diverso da X, e una applicazione f da X a valori in A biiettiva. Si vede facilmente che se X contiene Y e Y è un insieme infinito, allora anche X è infinito.
Facciamo qualche esempio.
- L'insieme N dei numeri naturali è un insieme infinito. Prendiamo in considerazione l'insieme 2N dei numeri pari. L'applicazione f:N ->2N definita da f(n)= 2n è biiettiva, pertanto N è equipotente a un suo sottoinsieme proprio.
- N è equipotente all'insieme dei numeri interi Z (equivalentemente: Z è numerabile). Prendiamo l'applicazione f: N->Z tale che f(n)= -n/2 quando n è pari e f(n)= (n+1)/2 quando n è dispari. Risulta facilmente che f è biiettiva.
- L'insieme dei numeri razionali Q è numerabile. La dimostrazione è dovuta a Georg Cantor e l'applicazione biiettiva ivi usata può essere rappresentata graficamente tramite una "tabella infinita" contenente tutti i possibili rapporti di numeri interi. La dimostrazione quindi si basa sul dare un ordine ai numeri razionali (e dunque definire un "successivo") in modo da metterli in relazione uno a uno con i numeri naturali.
- L'insieme dei numeri reali R non è numerabile. Anche questa dimostrazione è dovuta a Cantor. Si basa sul fatto che R sia equipotente a 2N (che è l'insieme delle successioni a valori in {0,1}) e che non esista nessuna applicazione iniettiva da 2N a valori in N.
Vediamo il risultato centrale della risposta.
Teorema: Un insieme X è infinito se e solo se contiene un sottoinsieme numerabile.
Dimostrazione: Ovviamente se X contiene un insieme numerabile (che è infinito) allora X è infinito.
Vediamo l'implicazione non banale, ossia che, se X è infinito, esso contiene un sottoinsieme numerabile. Per definizione di inisieme infinito esistono Y sottoinsieme proprio di X e un'applicazione g: X->Y biiettiva. Allora, poichè l'insieme X∖Y è non vuoto, scegliamo x0 in X∖Y. Definiamo quindi una applicazione f: N ->X utilizzando il teorema di ricorsione nel seguente modo: poniamo f(0):= x0 e per ogni n naturale f(n+1):=g(f(n)). Dimostriamo che f è iniettiva. Supponiamo per assurdo che non lo sia e sia n0 il più piccolo numero naturale tale che f(n0)=f(k) per qualche k>n0. Siccome f(0)=x0 non appartiene a Y, mentre per ogni n>0 f(n) appartiene a Y (essendo l'immagine tramite g di qualche elemento di X), risulta che n0>0. Allora n0-1 è ancora un numero naturale e g(f(n0-1))=f(n0)=f(k)=g(f(k-1)). Siccome g è biiettiva, in particolare è iniettiva, e quindi risulta che f(n0-1)=f(k-1). E questo, essendo n0-1 < k-1, va contro la minimalità di n0. Allora f è iniettiva e quindi biiettiva da N a f(N). Abbiamo quindi trovato un sottoinsieme di X -che è f(N)- numerabile.
Questo teorema ci dice che tra il finito e ℵ0 non c'è nulla di "intermedio" dal punto di vista della cardinalità. Ci si può porre un quesito simile confrontando gli insiemi numerabili e l'insieme R dei numeri reali. Esistono insiemi con cardinalità intermedia? Cantor tentò di dimostrare il seguente fatto:
Non esistono insiemi con cardinalità strettamente compresa tra quella dei numeri naturali e quella dei numeri reali. In altre parole, non esiste nulla di strettamente compreso tra ℵ0 e 2ℵ0.
Tale affermazione è nota come Ipotesi del Continuo. E' stato dimostrato da Kurt Gödel nel 1940 che nella Teoria degli insiemi di Zermelo-Fraenkel comprensiva dell'assioma della scelta, l'ipotesi del continuo è un fatto indecidibile. Quindi non è possibile rispondere nè sì nè no alla domanda posta sopra. (Attenzione: non possiamo rispondere non perché è un problema difficile a cui non si sa dare risposta, ma perché il problema è stato risolto e la risposta ottenuta è appunto l'indecidibilità). Alla luce di questo risultato, la Teoria degli Insiemi di Zermelo-Fraenkel comprensiva dell'assioma della scelta è non contraddittoria se e solo se è non contraddittoria con l'aggiunta dell'ipotesi del continuo.
Bibliografia:
-M.C.Tamburini, Appunti di Algebra, Edizioni ISU, Brescia 1998