Teorema di Cantor

In matematica, e in particolare nella teoria degli insiemi di Zermelo - Fraenkel (ZF), il teorema di Cantor afferma che, dato un insieme di qualsiasi cardinalità (numero di elementi), esiste sempre un insieme di cardinalità maggiore. In particolare, dato un insieme $X$, l'insieme delle parti di $X$ (cioè l'insieme formato da tutti i possibili sottoinsiemi di $X$) ha sempre cardinalità maggiore di quella di $X$.

Il teorema di Cantor è ovvio per insiemi finiti, ma continua a valere anche per insiemi infiniti. In particolare, l'insieme delle parti di un insieme numerabile è non numerabile.

Per una trattazione della tecnica di dimostrazione usata da Cantor si veda la voce argomento diagonale di Cantor.

La dimostrazione

Sia $f$ una generica funzione da $A$ nell'insieme delle parti di $A$:

$f\colon A\to {\mathcal {P}}(A).$

Per provare il teorema si deve mostrare che $f$ è necessariamente non suriettiva. A tal fine è sufficiente individuare un elemento di ${\mathcal {P}}(A)$ che non è nell'immagine di $f$. Questo elemento è:

$B=\left\{x\in A:x\not \in f(x)\right\}\in {\mathcal {P}}(A).$

Per dimostrare che $B$ non è nell'immagine di $f$, si suppone per assurdo che lo sia. Per qualche $y\in A$, si ha allora $f(y)=B$. Si considerano ora i due casi possibili:

$y\not \in B$ oppure $y\in B.$

Se $y\not \in B=f(y)$ allora per la definizione di $B$ si ha $y\in B$, assurdo.

Se $y\in B=f(y)$ allora per la definizione di $B$ si ha $y\not \in B$, assurdo.

In entrambi i casi si ottiene una contraddizione. Quindi $A$ e il suo insieme potenza non sono equipotenti.

Voci correlate

• Teoria degli insiemi di Zermelo - Fraenkel
• Georg Cantor
• Paradosso dell'ipergioco