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

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

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

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

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

${\displaystyle y\not \in B}$  oppure ${\displaystyle y\in B.}$ 

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

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

In entrambi i casi si ottiene una contraddizione. Quindi ${\displaystyle 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