Cantor, teorema di
Cantor, teorema di in teoria degli insiemi, stabilisce che in un qualsiasi insieme X l’insieme dei suoi sottoinsiemi (detto anche insieme delle parti di X), indicato con ℘(X), ha cardinalità maggiore di X: |℘(X)| > |X|. Cantor dimostrò il teorema nel modo seguente: si supponga che le cose non stiano così e che quindi esista una corrispondenza biunivoca tra un certo insieme X e ℘(X). Se ƒ è la funzione che istituisce tale corrispondenza fra X e ℘(X), dato un qualsiasi elemento b di X, o b è elemento della sua immagine ƒ(b) (che è un sottoinsieme di X) o non lo è. Si formi allora l’insieme Y di tutti gli elementi di X che non appartengono alla loro immagine:
La formazione dell’insieme “diagonale” Y condurrà a una contraddizione: Y é un sottoinsieme di X; quindi, per ipotesi, esso sarà l’immagine di un elemento d di X: Y = ƒ(d). Ci si chieda allora: d appartiene o meno alla sua immagine: ƒ(d) = d? Se d appartiene a Y, cioè all’insieme di tutti gli elementi di X che non appartengono alla loro immagine, d non vi appartiene; se non vi appartiene, se cioè d non appartiene all’insieme Y di tutti gli elementi di X che non appartengono alla loro immagine, d vi appartiene. In entrambi i casi, vi è contraddizione, e quindi si deve respingere l’ipotesi iniziale e considerare il teorema dimostrato per assurdo.