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 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 sorgente]

Sia f una generica funzione da A nell'insieme delle parti di A:

f: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 sorgente]

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