Insieme numerabile

Disambiguazione – "Numerabile" rimanda qui. Se stai cercando il concetto linguistico, vedi Nome 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.^[1]

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 ${\displaystyle \mathbb {N} }$. La cardinalità degli insiemi infiniti numerabili viene usualmente denotata con il simbolo ${\displaystyle \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.

Un insieme ${\displaystyle S}$ è detto numerabile se esiste una funzione iniettiva

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

da ${\displaystyle S}$ all'insieme dei numeri naturali ${\displaystyle \mathbb {N} =\{0,1,2,3,\ldots \}.}$^[2]

Se ${\displaystyle f}$ è anche una funzione suriettiva (quindi ${\displaystyle f}$ è biunivoca), allora ${\displaystyle 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).

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.^[3]

Si possono riassumere i vari teoremi che dimostrano l'equivalenza delle definizioni alternative in uno solo. Sia ${\displaystyle S}$ un insieme. Le seguenti affermazioni sono equivalenti:

1. ${\displaystyle S}$ è numerabile, cioè esiste una funzione iniettiva

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

2. ${\displaystyle S}$ è l'insieme vuoto oppure esiste una funzione suriettiva

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

3. ${\displaystyle S}$ è finito oppure esiste una biiezione

   ${\displaystyle h\colon \mathbb {N} \to S}$

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 ${\displaystyle {\tfrac {a}{b}}}$ con ${\displaystyle a}$ e ${\displaystyle b}$ interi positivi. Possiamo creare la seguente tabella delle frazioni ${\displaystyle {\tfrac {a}{b}}}$:

${\displaystyle {\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:

${\displaystyle {\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:

${\displaystyle {\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:

${\displaystyle {\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.

Con la stessa tecnica utilizzata per l'insieme dei numeri razionali, si può dimostrare che se ${\displaystyle A}$ e ${\displaystyle B}$ sono due insiemi numerabili anche il prodotto cartesiano ${\displaystyle 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.

Dato che ${\displaystyle A}$ è un insieme numerabile può essere messo in corrispondenza biunivoca con l'insieme dei numeri naturali, e quindi gli elementi di ${\displaystyle A}$ possono essere indicizzati nel seguente modo:

${\displaystyle a_{1},\ a_{2},\ a_{3},\ a_{4},\ a_{5},\dots }$

e lo stesso vale per l'insieme ${\displaystyle B}$:

${\displaystyle b_{1},\ b_{2},\ b_{3},\ b_{4},\ b_{5},\dots }$

Si ricorda che il prodotto cartesiano ${\displaystyle A\times B}$ è l'insieme formato da tutti gli elementi del tipo ${\displaystyle (a,b)}$ con ${\displaystyle a}$ appartenente ad ${\displaystyle A}$ e ${\displaystyle b}$ appartenente a ${\displaystyle B}$. Si può quindi disporre gli elementi di ${\displaystyle A\times B}$ in un modo simile a quello utilizzato per gli elementi di ${\displaystyle \mathbb {Q} }$:

${\displaystyle {\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 ${\displaystyle A\times B}$ e procedendo per diagonali come nel caso dei numeri razionali possiamo creare la seguente successione:

${\displaystyle {\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 ${\displaystyle A\times B}$ e ${\displaystyle \mathbb {N} }$.

Ora siano ${\displaystyle A_{1},A_{2},A_{3},\dots ,A_{n}}$ insiemi numerabili, per quanto detto sopra, abbiamo quindi che ${\displaystyle A_{1}\times A_{2}}$ è un insieme numerabile, e quindi anche l'insieme

${\displaystyle (A_{1}\times A_{2})\times A_{3}=A_{1}\times A_{2}\times A_{3}}$

è numerabile e, in generale, ripetendo ${\displaystyle n}$ volte il ragionamento abbiamo che l'insieme

${\displaystyle 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.

• 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.

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

• Wikimedia Commons contiene immagini o altri file su insieme numerabile

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

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica