Insieme numerabile
Da Wikipedia, l'enciclopedia libera.
Un insieme si dice numerabile quando ha la stessa cardinalità dell'insieme degli interi naturali N, ossia quando è possibile stabilire una corrispondenza biunivoca tra tale insieme e l'insieme dei numeri naturali. In caso contrario si parla di insieme non numerabile. La cardinalità degli insiemi numerabili viene usualmente denotata con il simbolo 
.
Un insieme numerabile X è un insieme infinito, cioè si può porre in corrispondenza biunivoca con un suo sottoinsieme proprio. Infatti l'insieme N può porsi in corrispondenza biunivoca con il suo sottoinsieme costituito dai soli numeri pari: possiamo associare ad ogni numero il suo doppio stabilendo la corrispondenza voluta:
- 0 ↔ 0, 1 ↔ 2, 2 ↔ 4, 3 ↔ 6, ...
Lo stesso può farsi con X servendosi della sua corrispondenza biunivoca con N. Viceversa si dimostra che ogni insieme infinito possiede 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.
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 a/b con a e b interi positivi. Possiamo creare la seguente tabella delle frazioni a/b:
1/1, 2/1, 3/1, 4/1, 5/1, ... 1/2, 2/2, 3/2, 4/2, 5/2, ... 1/3, 2/3, 3/3, 4/3, 5/3, ... 1/4, 2/4, 3/4, 4/4, 5/4, ... 1/5, 2/5, 3/5, 4/5, 5/5, ...
E così via. Tramite la cosiddetta diagonalizzazione si può quindi ottenere la seguente lista:
1/1, 2/1, 1/2, 1/3, 2/2, 3/1, 4/1, 3/2, 2/3, 1/4, 1/5, 2/4, 3/3, 4/2, 5/1, ... ecc.
Se da questa lista cancelliamo le frazioni che non sono ridotte ai minimi termini ci rimane la seguente successione:
1, 2, 1/2, 1/3, 3, 4, 3/2, 2/3, 1/4, 1/5, 5, ...
che contiene esattamente tutti i numeri razionali. Non è superfluo osservare che questa sequenza non è ordinata (nel senso numerico di "ogni numero è maggiore del precedente") e, anzi, è impossibile costruire una lista ordinata dei numeri razionali.
[modifica] Voci correlate
- Argomento diagonale di Cantor
- Insieme numerabile, definizione costruttiva
- Tipologia delle elaborazioni e delle procedure
- Elaborazione con risorse illimitate e infinito potenziale
- Cardinalità e composizione di insiemi numerabili
- Cardinalità
- Ipotesi del continuo
[modifica] 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
