Insieme numerabile

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica sorgente]

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} = \{1,2,3,...\}.[1]

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[modifica | modifica sorgente]

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.[2]

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 biiezione
    h\colon \mathbb{N} \to S.

L'insieme dei numeri razionali[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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.

Note[modifica | modifica sorgente]

  1. ^ Dal momento che c'è una ovvia biezione tra \mathbb{N} e \mathbb{N}^* = \{1,2,3,...\}, non c'è alcuna differenza se si considera 0 un numero naturale o meno. In ogni caso questo articolo segue l'ISO 31-11 e la convenzione standard in logica matematica, secondo la quale 0 è un numero naturale.
  2. ^ Vedere Lang 1993, op. cit., §2 of Chapter I.

Bibliografia[modifica | modifica sorgente]

Voci correlate[modifica | modifica sorgente]

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