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$$X$, l'insieme delle parti di $X$$X$ (cioè l'insieme formato da tutti i possibili sottoinsiemi di $X$$X$) ha sempre cardinalità maggiore di quella di $X$$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$$f$ una generica funzione da $A$$A$ nell'insieme delle parti di $A$$A$:

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

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

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

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

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

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

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

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

Voci correlate

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