Insieme numerabile

Un insieme infinito si dice numerabile quando ha la stessa cardinalità di N, ossia quando � possibile stabilire una corrispondenza biunivoca (biiezione) con l'insieme dei numeri naturali.

Esempi di insiemi numerabili sono i numeri interi e i numeri razionali. L'insieme dei numeri reali, al contrario, non � numerabile.

Per esempio, l'insieme dei numeri pari � numerabile; infatti possiamo associare ad ogni numero il suo doppio stabilendo la corrispondenza voluta:

1 ↔ 2, 2 ↔ 4, 3 ↔ 6, ...

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 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 un processo di diagonalizzazione si può quindi ottenere la seguente lista:

1/1, 2/1, 1/2, 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, 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 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.