In matematica, e in particolare nella teoria degli insiemi di Zermelo - Fraenkel (ZF), il teorema di Cantor, sviluppato dall'omonimo matematico tedesco Georg Cantor, afferma che per ogni insieme di cardinalità arbitraria (finita o infinita), il suo insieme delle parti ha cardinalità strettamente maggiore:

La relazione che lega la cardinalità di con quella di è espressa dalla disequazione .

Nel caso in cui sia un insieme con cardinalità numerabile, sotto l'ipotesi del continuo, il suo insieme delle parti è un insieme con cardinalità non numerabile. Come conseguenza importante, si ha che l'insieme delle parti dei numeri naturali (dove è un infinito numerabile con cardinalità ) è un infinito non numerabile, con cardinalità uguale alla cardinalità dei numeri reali , cioè la cardinalità del continuo.

Il teorema di Cantor ha avuto un impatto immediato e importante sulla filosofia della matematica. Ad esempio, nell'applicare iterativamente l'insieme delle parti di un insieme infinito e successivamente il teorema di Cantor, otteniamo una gerarchia infinita di cardinalità infinite, ognuna strettamente maggiore della precedente. Di conseguenza, il teorema implica che non esiste una cardinalità massima per un dato insieme, o equivalentemente, che i livelli gerarchici delle cardinalità infinite sono anch'essi infiniti.

Dimostrazione Il teorema si divide in due casi, in base alla cardinalità di .

Se la cardinalità di è finita, il teorema di Cantor si dimostra direttamente enumerando gli elementi dei due insiemi e confrontandone la cardinalità.

Sia la cardinalità di . La cardinalità di corrisponde al numero di sottoinsiemi generabili a partire dagli elementi di , che risulta essere . Di conseguenza il teorema vale, dato che .

Se la cardinalità di è infinita, facciamo affidamento alla definizione stessa di cardinalità: presi due insiemi generici e , abbiamo che se e solo se tutte le funzioni da a non sono suriettive (o equivalentemente ogni funzione iniettiva non è anche suriettiva).

La dimostrazione segue nel dimostrare che nessuna funzione generica è in grado di mappare tutti gli elementi di un insieme qualsiasi a tutti gli elementi di .

Sia una generica funzione da a :

Un sottoinsieme di è dato dalla seguente costruzione, derivato dall'argomento diagonale di Cantor.

Tale sottoinsieme contiene tutti gli elementi appartenenti ad , che però non appartengono al sottoinsieme di cui sono controimmagine attraverso la generica funzione .

Intuitivamente:

Se la funzione mappa in e allora . Se la funzione mappa in e allora .

Supponiamo per assurdo quindi, che la funzione sia suriettiva da a (ossia che ogni elemento di abbia controimmagine in attraverso ).

Necessariamente deve esistere un elemento la cui funzione viene mappata a (dato che ). Ci sono ora due casi possibili:

oppure

Allora si giunge alla seguente contraddizione:

Quindi non esiste un valore tale che .

Ossia, non è nell'immagine di , e non raggiunge tutti gli elementi di . non è suriettiva. Per completare il teorema non resta che trovare una funzione iniettiva Questa funzione è molto semplice ed è definita come la funzione identità che mappa all'insieme contenente solamente stesso:

Note

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

Altri progetti

Collegamenti esterni

Categoria:Teoria degli insiemi Cantor