L'insieme di Cantor ha la stessa cardinalità di R
Per una semplice dimostrazione di questo fatto conviene richiamare una proprietà della scrittura decimale dei reali (puoi cercare i collegamenti a questo argomento sull'indice alfabetico del sito): ogni razionale si può, mediante l'algoritmo della divisione, scrivere in forma decimale finita o periodica con periodo diverso da 9; ogni numero decimale finito (cioè con periodo zero) si può anche scrivere sotto forma di numero decimale con periodo 9. Per quest'ultimo fatto si può osservare che, in un decimale, l'eventuale gruppo terminale di cifre 1000... si può sostituire con 0999..., il gruppo terminale 2000... si può sostituire con 1999..., il gruppo terminale 3000... si può sostituire con 2999... . La stessa proprietà vale se si usano altre basi di numerazione, al posto della base dieci. Poiché ci serviremo di diverse basi per scrivere i numeri, quando sarà necessario evitare confusioni scriveremo esplicitamente la base come pedice: per esempio scriveremo (11)3 per indicare il numero che, in base 10, si scrive con la sola cifra 4, cioè il numero (4)10.
Il discorso è particolarmente semplice in base 2, dove le uniche cifre ammesse sono 0 e 1: in questo caso si può dire che l'eventuale gruppo terminale di cifre 1000... si può sostituire con 0111... . Per esempio il numero (1/2)10 (che ha, in base dieci, le due scritture decimali 0,5000... e 0,04999..) ha, in base due, le due scritture decimali 0,1000... e 0,0111... . Per visualizzare la scrittura in base due dei "numeri con la virgola" si può utilizzare la seguente figura, ricordando che in questa base l'unità deve venire, successivamente, divisa in due, quattro, otto, ..., parti:
In maniera analoga si può ragionare in base tre, dove le cifre ammesse sono 0, 1, 2: in questo caso l'eventuale gruppo terminale di cifre 1000... si può sostituire con 0222..., l'eventuale gruppo terminale 2000... si può sostituire con 1222... . In maniera analoga a quanto fatto per la base due, per capire la scrittura in base tre dei "numeri con la virgola" si può utilizzare la seguente figura, ricordando che ora l'unità deve venire successivamente divisa in tre, nove, ventisette, ..., parti:
(abbiamo riportato solo alcune etichette, per non appesantire troppo la figura).
Nel trattare l'insieme di Cantor la scrittura in base tre è particolarmente utile. Riesaminando il procedimento indicato per costruire questo insieme si capisce immediatamente che, al primo passo, vengono eliminati tutti i numeri compresi tra (0,1)3 e (0,2)3, cioè tutti i numeri che hanno 1 al primo posto dopo la virgola, tranne (0,1)3; poiché però (0,1)3=(0,0222...)3, possiamo dire che sono stati tolti tutti i numeri, compresi tra zero e uno, che hanno 1 al primo posto dopo la virgola nella loro scrittura in base 3. Allo stesso modo si vede facilmente che, al secondo passo, vengono eliminati tutti quelli che hanno la cifra 1 al secondo posto dopo la virgola, e così via. Se si osserva che si ha anche (1)3=(0,222...)3, si può concludere che i numeri che rimangono, cioè gli elementi dell'insieme di Cantor, saranno quelli del tipo (0,a1a2a3...)3, dove le cifre a1, a2, a3, ecc., possono essere solo zero o due.
Per concludere che l'insieme di Cantor non è numerabile basta ora applicare il procedimento diagonale che lo stesso Cantor utilizzò per dimostrare la non numerabilità dei reali. Se supponiamo per assurdo che l'insieme sia numerabile, potremo stabilire una corrispondenza biunivoca tra C e l'insieme dei naturali, ovvero elencare gli elementi di C chiamandoli, per esempio, γ1, γ2, γ3, ecc. Potremo dunque costruire una tabella dove sono inseriti tutti gli elementi dell'insieme di Cantor, scritti sempre in base tre:
| γ1 | = | 0,a1a2a3a4... |
| γ2 | = | 0,b1b2b3b4... |
| γ3 | = | 0,c1c2c3c4... |
| γ4 | = | 0,d1d2d3d4... |
| ... | = | ... |
dove le cifre a1, a2, a3, ecc., possono essere solo zero o due. Prendiamo ora in esame il numero del tipo 0,α1α2α3..., così costruito: se a1=0 poniamo α1=2, se a1=2 poniamo α1=0, se b2=0 poniamo α2=2, se b2=2 poniamo α2=0, ecc.. Questo numero è, per costruzione, diverso da tutti i numeri γ1, γ2, γ3, ecc., eppure appartiene all'insieme di Cantor perché il suo sviluppo in base tre contiene solo le cifre 0 e 2. Siamo caduti in un assurdo. Non ci resta che concludere che l'insieme C è non numerabile.