Insiemi numerabili

La numerabilità di un insieme è una sorta di equivalente della grandezza degli insiemi, perché con gli insiemi infiniti non si può ragionare in termini di numero di elementi, dato che il numero di elementi è, sorprendentemente… infinito. La grandezza di un insieme si chiama anche cardinalità.

Grandezza di un insieme infinito

Determinare la grandezza di un insieme finito è semplice: contiamo gli elementi. Quindi l’insieme M = {a, b, c, d, e} ha grandezza 5, e scriviamo |M| = 5.

Con gli insiemi infiniti la situazione è decisamente più complicata. Come potremmo confrontare la grandezza di insiemi infiniti? È possibile farlo, oppure tutti gli insiemi infiniti sono «ugualmente grandi»?

Come esempio prendiamo l’insieme dei numeri naturali (diversi da zero) e l’insieme dei numeri naturali pari. Abbiamo così gli insiemi ℕ^* = {1, 2, 3, 4, 5, 6, …} e S = {2, 4, 6, …}. Verrebbe da dire che l’insieme dei numeri naturali è più grande dell’insieme dei numeri pari, perché i numeri naturali contengono tutti i numeri pari e in più altri elementi: i numeri dispari.

Potremmo quindi scrivere che vale S ⊂ ℕ^*: l’insieme S è un sottoinsieme proprio dell’insieme ℕ^*. E potremmo dire che, se S ⊂ ℕ^*, allora l’insieme ℕ^* è più grande: contiene pur sempre più elementi dell’insieme S.

Una delle ragioni per cui non possiamo misurare gli insiemi con la relazione di inclusione è che due insiemi possono avere grandezze diverse anche se nessuno dei due è sottoinsieme dell’altro. Lo si può mostrare anche con insiemi finiti: A = {1, 3, 4, 9} e B = {b, u, r, z, m}. Vale |A| = 4 e |B| = 5. L’insieme B è più grande dell’insieme A, eppure non vale A ⊂ B. Nel caso degli insiemi infiniti lo vediamo con i numeri pari e i numeri dispari: nessuno dei due insiemi è sottoinsieme dell’altro.

La relazione di inclusione quindi non è un candidato ideale per decidere se un insieme è più grande di un altro.

Biiezione

Proviamo un altro approccio. Abbiamo due insiemi, A e B. Possiamo dire che hanno la stessa grandezza se tra di essi esiste una funzione biiettiva. Che cosa significa? Che prendiamo un elemento dell’insieme A, un elemento dell’insieme B e formiamo la coppia (a; b). Togliamo questi elementi dagli insiemi e proseguiamo. Se riusciamo a «svuotare» entrambi gli insiemi, abbiamo trovato una funzione biiettiva.

Esempio con insiemi finiti: A = {a, b, c} e B = {1, 2, 3}. La prima coppia potrebbe essere (a; 1), la successiva (b; 2) e infine (c; 3). Abbiamo esaurito tutti gli elementi di entrambi gli insiemi, abbiamo trovato una funzione biiettiva. L’importante è che questa non è l’unica funzione biiettiva. Anche questa è una soluzione valida: (a; 3), (b; 1), (c; 2).

Con gli insiemi infiniti la cosa diventa un po’ più interessante. Proviamo con i numeri naturali dispari e pari. Intuitivamente sentiamo che dovrebbero essere tanti gli uni quanti gli altri. Proviamo. Prendiamo il primo numero dispari e lo associamo al primo numero pari: (1; 2). Poi il secondo dispari e il secondo pari: (3; 4). E così via. Otteniamo così le coppie (1; 2), (3; 4), (5; 6), (7; 8), … Potremmo scrivere che ogni numero dispari l viene associato al numero pari l + 1 e che ogni numero pari s è l’immagine del numero dispari s − 1. Per ogni numero dispari e per ogni numero pari abbiamo quindi una coppia che contiene quel numero. Gli insiemi dei numeri dispari e dei numeri pari hanno dunque la stessa grandezza.

Numeri pari e numeri naturali

Ora proviamo lo stesso procedimento e confrontiamo l’insieme dei numeri naturali e quello dei numeri pari. Abbiamo così gli insiemi ℕ^* = {1, 2, 3, 4, 5, 6, …} e S = {2, 4, 6, …}. Intuitivamente ci aspettiamo che l’insieme dei numeri naturali sia più grande.

Proviamo però a cercare la funzione biiettiva in questione. Possiamo dire che ogni numero naturale n viene associato al suo doppio, a 2n. In questo modo otteniamo le coppie (1; 2), (2; 4), (3; 6), (4; 8), (5; 10), … Per ogni numero naturale n abbiamo quindi la coppia (n; 2n) e per ogni numero pari s abbiamo la coppia (s/2; s). Abbiamo trovato una funzione biiettiva: l’insieme dei numeri pari e l’insieme dei numeri naturali hanno quindi la stessa grandezza, hanno la stessa cardinalità.

Tutto questo può sembrare strano, perché i numeri naturali contengono pur sempre più elementi dei numeri pari. I numeri naturali contengono tutti i numeri pari e in più tutti i numeri dispari. Tuttavia siamo in grado di trovare una biiezione, quindi i due insiemi hanno la stessa grandezza.

Confronto con i numeri naturali

I numeri naturali in realtà determinano la più piccola grandezza di un insieme infinito. Se un altro insieme abbia la stessa grandezza dell’insieme dei numeri naturali si può spesso scoprire con relativa facilità: basta trovare una biiezione con i numeri naturali, il che in pratica significa che basta riuscire a numerare, a ordinare gli elementi del nostro insieme M.

Quindi, se riusciamo a mettere in fila gli elementi di un insieme in modo da decidere quale elemento è il primo, quale il secondo, il terzo, il quarto, il decimo ecc., allora l’insieme è grande quanto ℕ^*. Di un insieme così diciamo che è numerabile.

Vediamo facilmente che i numeri naturali pari e dispari sono numerabili, perché sappiamo indicare il primo, il secondo, il terzo ecc. numero pari o dispari. E i numeri interi pari? Cioè l’insieme S = {…, −4, −2, 0, 2, 4, …}. Riusciamo a ordinarli? Sì, basta prendere lo stesso ordine di prima e subito dopo ogni numero pari positivo scrivere anche la sua versione negativa: S = {0, 2, −2, 4, −4, 6, −6, …}. Similmente, ad esempio, per i numeri interi.

Grandezza dei numeri razionali

Un esempio più interessante sono i numeri razionali, le frazioni. Riusciamo a ordinarli? Sì, ma sarà un po’ più complicato. Costruiamo una tabella con infinite righe e colonne. In ogni cella ci sarà una frazione. Nella colonna n e nella riga m avremo la frazione n/m. Quindi nella 1ª colonna e nella 2ª riga abbiamo $\frac{1}{2}$ e nella terza colonna e nella quarta riga abbiamo 3/4.

$$\begin{array}{ccccc}1/1& 2/1& 3/1& 4/1& \dots \\ 1/2& 2/2& 3/2& 4/2& \dots \\ 1/3& 2/3& 3/3& 4/3& \dots \\ 1/4& 2/4& 3/4& 4/4& \dots \\ \dots & \dots & \dots & \dots & \dots \end{array}$$

Come ordinare, numerare ora questi numeri? Non possiamo numerarli per righe o per colonne, perché ci perderemmo subito dentro quella riga o colonna. Prendiamo invece i numeri lungo le diagonali: (prima diagonale:) 1/1, (seconda diagonale:) 2/1, 1/2, (terza diagonale:) 3/1, 2/2, 1/3, (quarta diagonale:) 4/1, 3/2, 2/3, 1/4, … Ci sono ancora molte frazioni duplicate, ma non importa. Quello che importa di più è che mancano i numeri negativi. Si risolve facilmente: ogni volta che scriviamo una frazione, mettiamo subito dopo la sua versione negativa. E poi all’inizio ci manca ancora lo zero. Ed è tutto: abbiamo tutti i numeri razionali in una successione.

In totale otteniamo la successione: 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …

Grandezza dei numeri reali

I numeri reali sono tanti quanti i numeri naturali? La decisione sarà ancora più complicata che nel caso dei numeri razionali. Faremo una dimostrazione per assurdo. Supponiamo che i numeri reali siano numerabili e che esista una funzione biiettiva con i numeri naturali. Supponiamo quindi che si possano ordinare. E poniamo che la tabella seguente sia proprio quell’ordinamento:

$$\begin{array}{ccccccccc}0,& 3& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& 9& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& 3& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& 7& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& 7& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& 6& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& 0& \dots \\ \dots \end{array}$$

Nella tabella ci sono i primi sette numeri reali del nostro ordinamento. Questo ordinamento naturalmente può essere qualsiasi, non deve per forza essere ordinato per grandezza dei numeri.

Per ipotesi, in questa tabella infinita sono ordinati tutti i numeri reali. (La tabella è di nuovo infinita, qui ci sono solo i primi sette elementi.) Ora cercheremo di trovare, di costruire un numero che è reale ma non compare in questa tabella. Se troviamo un tale numero, otteniamo una contraddizione con il fatto che nella tabella ci sono tutti i numeri reali, da cui possiamo concludere che l’insieme dei numeri reali non è numerabile.

Il numero che non è nella tabella lo costruiamo così:

$$\begin{array}{ccccccccc}0,& \boxed{\text{3}}& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& \boxed{\text{9}}& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& \boxed{\text{3}}& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& \boxed{\text{7}}& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& \boxed{\text{7}}& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& \boxed{\text{6}}& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& \boxed{\text{0}}& \dots \\ \dots \end{array}$$

Cominciamo scrivendo 0,… Così inizierà il nostro nuovo numero reale. Come prima cifra decimale metteremo una cifra che non è al primo posto nel primo numero reale del nostro ordinamento (nella tabella è evidenziata con un riquadro). Lì c’è la cifra 3, quindi scegliamo ad esempio 1 e otteniamo il numero 0,1…

Proseguiamo. Al secondo posto ci sarà una cifra che non è al secondo posto del secondo numero reale. Lì c’è 9, quindi ad esempio 2. Otteniamo il numero 0,12… Al terzo posto ci sarà una cifra diversa dalla terza cifra del terzo numero reale. Lì c’è 3, quindi scegliamo ad esempio 7. Otteniamo 0, 127…

E così via, e così via. In posizione n del nuovo numero ci sarà sempre una cifra diversa dalla cifra che si trova in posizione n dell’n-esimo numero del nostro ordinamento.

Che cosa otteniamo? Otteniamo un numero che differisce da tutti i numeri del nostro ordinamento almeno per una cifra. Prendiamo l’ultimo risultato provvisorio: 0,127… Questo numero differisce di sicuro dal primo numero del nostro ordinamento almeno nella prima cifra, perché lo abbiamo costruito così. Dal secondo numero differisce almeno nella seconda cifra. Dal terzo nella terza cifra. In generale, questo nuovo numero differisce dal numero che occupa l’n-esimo posto nell’ordinamento almeno nella cifra in posizione n.

Questo numero appena costruito quindi non lo troveremo nella tabella che doveva simboleggiare la biiezione tra i numeri naturali e i numeri reali. I numeri reali sono quindi più dei numeri naturali. I numeri reali non sono numerabili, sono non numerabili.