Teorema di Cantor
Non esiste un insieme A con una corrispondenza biunivoca fra A e l'insieme di tutti i suoi sottoinsiemi A*.

DIMOSTRAZIONE

1. IPOTESI: assumiamo che esista un insieme A con una corrispondenza biunivoca fra A e l'insieme dei suoi sottoinsiemi A*. Chiamiamo tale corrispondenza s e, per ogni elemento x appartenente ad A, indichiamo con s(x) il sottoinsieme di A che gli corrisponde tramite s ;
2. per ogni x appartenente ad A, o x appartiene al suo corrispondente s(x), o x non appartiene al suo corrispondente s(x) :
perché, per l'ipotesi (1), per ogni x, s(x) è un sottoinsieme di A. (O, più semplicemente, (2) vale per la legge logica del III escluso);
3. sia C l'insieme di tutti gli elementi x di A che non appartengono al proprio corrispondente s(x) :
si noti che, a causa di (2), l'insieme C è ben definito ;
4. C è un sottoinsieme di A :
perché, per (3), tutti gli elementi di C sono anche elementi di A ;
5. C appartiene ad A* :
perché, per (4), C è un sottoinsieme di A, e, per l'ipotesi (1), A* è l'insieme di tutti i sottoinsiemi di A ;
6. esiste un elemento x_C di A tale che il suo corrispondente s(x_C) è C;
perché, per (5), C appartiene ad A* e, per l'ipotesi (1), la corrispondenza s fra A e A* è biunivoca ;
7. o x_C appartiene a C, o x_C non appartiene a C :
perchè, per (6), x_C appartiene ad A e C è il suo corrispondente s(x_C). Dunque, per (2), o x_C appartiene a C, o x_C non appartiene a C. (O, più semplicemente, (7) vale per la legge logica del III escluso);
1. SOTTO-IPOTESI : assumiamo che x_C appartenga a C ;
2. x_C non appartiene al suo corrispondente s(x_C) :
per (a), x_C appartiene a C. Ma, per (3), ogni elemento di C non appartiene al suo corrispondente. Dunque, x_C non appartiene al suo corrispondente s(x_C) ;
3. x_C non appartiene a C :
perché, per (b), x_C non appartiene al suo corrispondente s(x_C) e, per (6), tale corrispondente è C ;
8. x_C non appartiene a C :
siccome (c) contraddice la sottoipotesi (a), essa è falsa; quindi, per (7),  x_C non appartiene a C ;
9. x_C appartiene al suo corrispondente s(x_C) :
se x_C non appartenesse al suo corrispondente s(x_C), allora, per (3), x_C apparterrebbe a C. Ma, per (8), x_C non appartiene a C. Dunque, x_C appartiene al suo corrispondente s(x_C) ;
10. x_C appartiene a C :
perché, per (9), x_C appartiene al suo corrispondente s(x_C) e, per (6), tale corrispondente è C ;
11. non esiste un insieme A con una corrispondenza biunivoca fra A e l'insieme di tutti i suoi sottoinsiemi A* :
perché (10) contraddice (8). Dunque, l'ipotesi (1) è falsa, e quindi non esiste un insieme A con una corrispondenza biunivoca fra A e l'insieme di tutti i suoi sottoinsiemi A*.                c.v.d.