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:

1. $S$ è numerabile, cioè esiste una funzione iniettiva

   $f\colon S\to \mathbb {N}$

2. $S$ è l'insieme vuoto oppure esiste una funzione suriettiva

   $g\colon \mathbb {N} \to S$

3. $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.

Bibliografia

• Richard Courant e Herbert Robbins, Che cos'è la matematica?, Seconda edizione, Torino, Universale Bollati Boringhieri, 2000, ISBN 88-339-1200-0.
• Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi e Luigi Laura, Linguaggi, Modelli, Complessità, Milano, FrancoAngeli, 2003, ISBN 88-464-4470-1.
• (EN) W.S. Brainerd e L.H. Landweber, Theory of Computation, New York, Wiley, 1974, ISBN 04-710-9585-0.
• (EN) Serge Lang, Real and Functional Analysis, Berlino, Springer Verlag, 1993, ISBN 0-387-94001-4.

Voci correlate

• Argomento diagonale di Cantor
• Cardinalità
• Cardinalità del continuo
• Ipotesi del continuo
• Insieme finito
• Funzione coppia

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su insieme numerabile

Collegamenti esterni

• (EN) Eric W. Weisstein, countable set, su MathWorld, Wolfram Research.