# Insieme numerabile

In matematica, e più in particolare nella teoria degli insiemi, un insieme viene detto numerabile se i suoi elementi sono in numero finito oppure se possono essere messi in corrispondenza biunivoca con i numeri naturali.
Se un insieme numerabile possiede un numero infinito di elementi, viene detto infinito numerabile, e dato che può essere messo in corrispondenza biunivoca con i numeri naturali, si può dire che un insieme è infinito numerabile se ha la cardinalità di $\mathbb {N}$. La cardinalità degli insiemi infiniti numerabili viene usualmente denotata con il simbolo $\aleph _{0}$.
Si può dimostrare che ogni sottoinsieme infinito di un insieme numerabile è anch'esso numerabile, e che ogni insieme infinito contiene un sottoinsieme numerabile.
Esempi di insiemi numerabili sono l'insieme dei numeri interi e quello dei numeri razionali. Il più semplice esempio di insieme non numerabile è dato dall'insieme dei numeri reali la cui non numerabilità è stata dimostrata per la prima volta da Cantor tramite il suo argomento diagonale.

## Definizione

Un insieme $S$ è detto numerabile se esiste una funzione iniettiva
    $f\colon S\to \mathbb {N}$
da $S$ all'insieme dei numeri naturali $\mathbb {N} =\{0,1,2,3,\ldots \}.$
Se $f$ è anche una funzione suriettiva (quindi $f$ è biunivoca), allora $S$ è chiamato insieme infinito numerabile.
Questa terminologia non è universale: qualche autore definisce un insieme numerabile in modo da non includere gli insiemi finiti, definendo quindi unicamente la corrispondenza con una funzione biunivoca (qui considerato come un caso speciale e chiamato infinito numerabile).

### Altre definizioni

Possono essere date delle definizioni alternative ma equivalenti di insieme numerabile, in termini di funzioni biettive o suriettive, grazie ad alcuni teoremi. Una dimostrazione di questi può essere trovata nei testi di Lang.
Si possono riassumere i vari teoremi che dimostrano l'equivalenza delle definizioni alternative in uno solo. Sia $S$ un insieme. Le seguenti affermazioni sono equivalenti:
* $S$ è numerabile, cioè esiste una funzione iniettiva
    $f\colon S\to \mathbb {N}$
* $S$ è l'insieme vuoto oppure esiste una funzione suriettiva
    $g\colon \mathbb {N} \to S$
* $S$ è finito oppure esiste una biiezione
    $h\colon \mathbb {N} \to S$

## L'insieme dei numeri razionali

Per dimostrare che l'insieme dei numeri razionali è numerabile (ci limitiamo ai razionali positivi, sebbene la generalizzazione sia banale), osserviamo che tutti i razionali positivi si possono scrivere nella forma ${\tfrac {a}{b}}$ con $a$ e $b$ interi positivi. Possiamo creare la seguente tabella delle frazioni ${\tfrac {a}{b}}$:
    ${\begin{matrix}{\tfrac {1}{1}}&{\tfrac {2}{1}}&{\tfrac {3}{1}}&{\tfrac {4}{1}}&{\tfrac {5}{1}}&\dots \\{\tfrac {1}{2}}&{\tfrac {2}{2}}&{\tfrac {3}{2}}&{\tfrac {4}{2}}&{\tfrac {5}{2}}&\dots \\{\tfrac {1}{3}}&{\tfrac {2}{3}}&{\tfrac {3}{3}}&{\tfrac {4}{3}}&{\tfrac {5}{3}}&\dots \\{\tfrac {1}{4}}&{\tfrac {2}{4}}&{\tfrac {3}{4}}&{\tfrac {4}{4}}&{\tfrac {5}{4}}&\dots \\{\tfrac {1}{5}}&{\tfrac {2}{5}}&{\tfrac {3}{5}}&{\tfrac {4}{5}}&{\tfrac {5}{5}}&\dots \\\dots &\dots &\dots &\dots &\dots &\end{matrix}}$
Per costruire una funzione biunivoca con i numeri naturali si può procedere per diagonali nel seguente modo:
    ${\begin{matrix}{\tfrac {1}{1}}&&{\tfrac {2}{1}}&&{\tfrac {3}{1}}&&{\tfrac {4}{1}}&&{\tfrac {5}{1}}&\dots \\{\tfrac {1}{2}}&^{\nearrow }&{\tfrac {2}{2}}&^{\nearrow }&{\tfrac {3}{2}}&^{\nearrow }&{\tfrac {4}{2}}&^{\nearrow }&{\tfrac {5}{2}}&\dots \\{\tfrac {1}{3}}&^{\nearrow }&{\tfrac {2}{3}}&^{\nearrow }&{\tfrac {3}{3}}&^{\nearrow }&{\tfrac {4}{3}}&&{\tfrac {5}{3}}&\dots \\{\tfrac {1}{4}}&^{\nearrow }&{\tfrac {2}{4}}&^{\nearrow }&{\tfrac {3}{4}}&&{\tfrac {4}{4}}&&{\tfrac {5}{4}}&\dots \\{\tfrac {1}{5}}&^{\nearrow }&{\tfrac {2}{5}}&&{\tfrac {3}{5}}&&{\tfrac {4}{5}}&&{\tfrac {5}{5}}&\dots \\\dots &&\dots &&\dots &&\dots &&\dots &\end{matrix}}$
Ottenendo quindi la seguente lista:
    ${\frac {1}{1}},\ {\frac {1}{2}},\ {\frac {2}{1}},\ {\frac {1}{3}},\ {\frac {2}{2}},\ {\frac {3}{1}},\ {\frac {1}{4}},\ {\frac {2}{3}},\ {\frac {3}{2}},\ {\frac {4}{1}},\ {\frac {1}{5}},\ {\frac {2}{4}},\ {\frac {3}{3}},\ {\frac {4}{2}},\ {\frac {5}{1}},\dots$
Se da questa lista cancelliamo le frazioni che non sono ridotte ai minimi termini ci rimane la seguente successione:
    ${\begin{array}{cccccccccccc}1,&{\tfrac {1}{2}},&2,&{\tfrac {1}{3}},&3,&{\tfrac {1}{4}},&{\tfrac {2}{3}},&{\tfrac {3}{2}},&4,&{\tfrac {1}{5}},&5,&\dots \\\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\\1&2&3&4&5&6&7&8&9&10&11&\dots \end{array}}$
che contiene esattamente tutti i numeri razionali. Questa sequenza tuttavia non rispetta l'ordine dei numeri razionali (ovvero non è detto che, tra due numeri che si presentano consecutivamente in questa lista, il secondo sia il più grande); anzi, è impossibile costruire una lista completa dei numeri razionali che ne rispetti l'ordine.

## Prodotto cartesiano di insiemi numerabili

Con la stessa tecnica utilizzata per l'insieme dei numeri razionali, si può dimostrare che se $A$ e $B$ sono due insiemi numerabili anche il prodotto cartesiano $A\times B$ è un insieme numerabile e più in generale il prodotto cartesiano di un numero finito di insiemi numerabili è anch'esso un insieme numerabile.

### Dimostrazione

Dato che $A$ è un insieme numerabile può essere messo in corrispondenza biunivoca con l'insieme dei numeri naturali, e quindi gli elementi di $A$ possono essere indicizzati nel seguente modo:
    $a_{1},\ a_{2},\ a_{3},\ a_{4},\ a_{5},\dots$
e lo stesso vale per l'insieme $B$:
    $b_{1},\ b_{2},\ b_{3},\ b_{4},\ b_{5},\dots$
Si ricorda che il prodotto cartesiano $A\times B$ è l'insieme formato da tutti gli elementi del tipo $(a,b)$ con $a$ appartenente ad $A$ e $b$ appartenente a $B$. Si può quindi disporre gli elementi di $A\times B$ in un modo simile a quello utilizzato per gli elementi di $\mathbb {Q}$:
    ${\begin{matrix}(a_{1},b_{1})&(a_{2},b_{1})&(a_{3},b_{1})&(a_{4},b_{1})&(a_{5},b_{1})&\dots \\(a_{1},b_{2})&(a_{2},b_{2})&(a_{3},b_{2})&(a_{4},b_{2})&(a_{5},b_{2})&\dots \\(a_{1},b_{3})&(a_{2},b_{3})&(a_{3},b_{3})&(a_{4},b_{3})&(a_{5},b_{3})&\dots \\(a_{1},b_{4})&(a_{2},b_{4})&(a_{3},b_{4})&(a_{4},b_{4})&(a_{5},b_{4})&\dots \\(a_{1},b_{5})&(a_{2},b_{5})&(a_{3},b_{5})&(a_{4},b_{5})&(a_{5},b_{5})&\dots \\\dots &\dots &\dots &\dots &\dots &\end{matrix}}$
In questo modo abbiamo disposto in una tabella tutti gli elementi di $A\times B$ e procedendo per diagonali come nel caso dei numeri razionali possiamo creare la seguente successione:
    ${\begin{array}{cccccccccccccccc}(a_{1},b_{1})&(a_{1},b_{2})&(a_{2},b_{1})&(a_{1},b_{3})&(a_{2},b_{2})&(a_{3},b_{1})&(a_{1},b_{4})&(a_{2},b_{3})&(a_{3},b_{2})&(a_{4},b_{1})&(a_{1},b_{5})&(a_{2},b_{4})&(a_{3},b_{3})&(a_{4},b_{2})&(a_{5},b_{1})&\dots \\\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\\1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&\dots \end{array}}$
che è ovviamente un'applicazione biunivoca tra l'insieme $A\times B$ e $\mathbb {N}$.
Ora siano $A_{1},A_{2},A_{3},\dots ,A_{n}$ insiemi numerabili, per quanto detto sopra, abbiamo quindi che $A_{1}\times A_{2}$ è un insieme numerabile, e quindi anche l'insieme
    $(A_{1}\times A_{2})\times A_{3}=A_{1}\times A_{2}\times A_{3}$
è numerabile e, in generale, ripetendo $n$ volte il ragionamento abbiamo che l'insieme
    $A_{1}\times A_{2}\times A_{3}\times \dots \times A_{n}$
è numerabile e quindi il prodotto cartesiano di un numero finito di insiemi numerabili è un insieme numerabile.