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[modifica | modifica wikitesto]

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. In particolare, la cardinalità dell'insieme delle parti di $A$ è maggiore della cardinalità di $A$ perché la funzione $g\colon A\to {\mathcal {P}}(A)$ definita come $g(a)=\{a\}$ è chiaramente iniettiva.