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.[1]
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 . La cardinalità degli insiemi infiniti numerabili viene usualmente denotata con il simbolo .
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.
Un insieme è detto numerabile se esiste una funzione iniettiva
da all'insieme dei numeri naturali [2]
Se è anche una funzione suriettiva (quindi è biunivoca), allora è 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).
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 e interi positivi. Possiamo creare la seguente tabella delle frazioni :
Per costruire una funzione biunivoca con i numeri naturali si può procedere per diagonali nel seguente modo:
Ottenendo quindi la seguente lista:
Se da questa lista cancelliamo le frazioni che non sono ridotte ai minimi termini ci rimane la seguente successione:
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.
Con la stessa tecnica utilizzata per l'insieme dei numeri razionali, si può dimostrare che se e sono due insiemi numerabili anche il prodotto cartesiano è 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 è un insieme numerabile può essere messo in corrispondenza biunivoca con l'insieme dei numeri naturali, e quindi gli elementi di possono essere indicizzati nel seguente modo:
e lo stesso vale per l'insieme :
Si ricorda che il prodotto cartesiano è l'insieme formato da tutti gli elementi del tipo con appartenente ad e appartenente a . Si può quindi disporre gli elementi di in un modo simile a quello utilizzato per gli elementi di :
In questo modo abbiamo disposto in una tabella tutti gli elementi di e procedendo per diagonali come nel caso dei numeri razionali possiamo creare la seguente successione:
che è ovviamente un'applicazione biunivoca tra l'insieme e .
Ora siano insiemi numerabili, per quanto detto sopra, abbiamo quindi che è un insieme numerabile, e quindi anche l'insieme
è numerabile e, in generale, ripetendo volte il ragionamento abbiamo che l'insieme
è numerabile e quindi il prodotto cartesiano di un numero finito di insiemi numerabili è un insieme numerabile.
Helmut Seiffert, 1, in LE BASI DELLA MATEMATICA MODERNA numeri e insiemi, Arnoldo Mondadori, Marzo 1976, pp. 25-27.
Dal momento che c'è una ovvia biezione tra e , 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.
- Richard Courant e Herbert Robbins, Che cos'è la matematica?, Seconda edizione, Torino, Universale Bollati Boringhieri, 2000, ISBN 88-339-1200-0.
- Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi e Luigi Laura, Linguaggi, Modelli, Complessità, Milano, FrancoAngeli, 2003, ISBN 88-464-4470-1.
- (EN) W.S. Brainerd e L.H. Landweber, Theory of Computation, New York, Wiley, 1974, ISBN 04-710-9585-0.
- (EN) Serge Lang, Real and Functional Analysis, Berlino, Springer Verlag, 1993, ISBN 0-387-94001-4.