Teorema di Cantor
Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti. |
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 , l'insieme delle parti di (cioè l'insieme formato da tutti i possibili sottoinsiemi di ) ha sempre cardinalità maggiore di quella di .
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[modifica | modifica wikitesto]
Sia una generica funzione da nell'insieme delle parti di :
Per provare il teorema si deve mostrare che è necessariamente non suriettiva. A tal fine è sufficiente individuare un elemento di che non è nell'immagine di . Questo elemento è:
Per dimostrare che non è nell'immagine di , si suppone per assurdo che lo sia. Per qualche , si ha allora . Si considerano ora i due casi possibili:
- oppure
Se allora per la definizione di si ha , assurdo.
Se allora per la definizione di si ha , assurdo.
In entrambi i casi si ottiene una contraddizione. Quindi e il suo insieme potenza non sono equipotenti.