Teorema di Cantor

Da Wikipedia, l'enciclopedia libera.

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 potenza 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 potenza 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.

[modifica] La dimostrazione

Sia f una generica funzione da A nell'inseme potenza di A. Per provare il teorema si deve mostrare che f è necessariamente non suriettiva. A tal fine è sufficiente individuare un sottoinsieme di A che non è nell'immagine di f. questo sottoinsieme è

per dimostrare che B non è nell'immagine di f, supponiamo che lo sia. Per qualche y ∈ A, si ha allora f(y) = B. Consideriamo ora i due casi possibili: y ∈ B o y ∉ B. Se y ∈ B, allora y ∈ f(y), ma ciò implica, per la definizione di B, che y ∉ B. D'altra parte se y ∉ B, allora y ∉ f(y) e quindi y ∈ B. In entrambi i casi si ottiene una contraddizione. Quindi A e il suo insieme potenza non sono equipollenti.

[modifica] Voci correlate

• Paradosso dell'ipergioco.