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

Dimostriamo adesso la non-numerabilità dell'insieme dei numeri reali. Ragioniamo per assurdo. Supponiamo cioè che esista una biiezione tra i reali ed i numeri naturali. Allora è possibile costruire una lista di tutti i numeri reali:

• N₁,a₁a₂a₃a₄a₅...
• N₂,b₁b₂b₃b₄b₅...
• N₃,c₁c₂c₃c₄c₅...
• ...

Ora scegliamo un numero a diverso da a₁ e compresa tra 1 e 8 (includere 0 e 9 potrebbe provocare casi di ambiguità dovuti a rappresentazioni come 0,99999... = 1), una cifra b diversa da b₂, c diversa da c₃ e così via. Costruiamo quindi il numero reale 0,abcd... Questo numero è per costruzione diverso da ogni numero presente nella lista, e di conseguenza non fa parte di essa. Ciò costituisce un assurdo, perché avevamo supposto che la lista contenesse tutti i numeri reali. La sola supposizione di esistenza ci ha condotto a conseguenze in contrasto con le ipotesi, pertanto la lista non esiste e i reali non sono numerabili.

Questa dimostrazione non è costruttiva, e quindi è rifiutata dalla scuola intuizionista, per la quale il concetto stesso di "insieme numerabile" è fallace perché non è possibile associare materialmente un numero a tutti gli elementi di un insieme infinito. La maggior parte dei matematici però accetta come vera questa dimostrazione.

[modifica] Voci correlate

• 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

• 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