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 infinito 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,...\}.$

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. O $S$ è l'insieme vuoto oppure esiste una funzione suriettiva

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

3. O $S$ è finito oppure esiste una biezione

   $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

• R. Courant e H. Robbins, Che cos'è la matematica? Seconda edizione, Universale Bollati Boringhieri, Torino, 2000, ISBN 8833912000
• Giorgio Ausiello, Fabrizio d'Amore, Giorgio Gambosi; FrancoAngeli Editore: Linguaggi, Modelli, Complessità (2003) (ISBN 88-464-4470-1)
• Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley, ISBN 0471095850
• Serge Lang, Real and Functional Analysis, Berlino, New York, Springer Verlag, 1993. ISBN 0387940014

Voci correlate

• Argomento diagonale di Cantor
• Cardinalità
• Ipotesi del continuo

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