Teorema di Cantor

Da Wikipedia, l'enciclopedia libera.

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

Voci correlate[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica