Teorema di Cantor

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 è più che 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: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

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica