Teorema di Cantor

In matematica, e in particolare nella teoria degli insiemi di Zermelo - Fraenkel (ZF), il teorema di Cantor, sviluppato dall'omonimo matematico tedesco Georg Cantor, è un teorema che afferma che per ogni insieme ${\displaystyle A}$, di qualsiasi cardinalità (finita o infinita), il suo insieme delle parti ${\displaystyle {\mathcal {P}}(A)}$ ha sempre cardinalità strettamente maggiore: ${\displaystyle \mathrm {card} ({\mathcal {P}}(A))>\mathrm {card} (A)}$.

Per quanto riguarda gli insiemi finiti, il teorema di Cantor si dimostra semplicemente enumerando gli elementi dei due insiemi e confrontandone la cardinalità. La cardinalità di ${\displaystyle A}$ è ${\displaystyle n}$. La cardinalità di ${\displaystyle {\mathcal {P}}(A)}$, contando l'insieme vuoto ${\displaystyle \varnothing }$ e ${\displaystyle A}$ stesso come sottoinsiemi di ${\displaystyle A}$, vale ${\displaystyle 2^{n}}$. Di conseguenza il teorema vale, perché ${\displaystyle 2^{n}>n}$ per ogni intero non negativo.

Il vero e proprio teorema di Cantor specifica che questa proprietà degli insiemi finiti non si estingue quando la loro cardinalità diviene infinita. Come conseguenza importante, si ha che l'insieme delle parti dei numeri naturali ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$, dove ${\displaystyle \mathbb {N} }$ è un infinito numerabile con cardinalità ${\displaystyle \aleph _{0}=\mathrm {card} (\mathbb {N} )}$, è un infinito non numerabile, con cardinalità uguale alla cardinalità dei numeri reali ${\displaystyle \mathbb {R} }$, spesso definita come cardinalità del continuo.

La relazione che lega la cardinalità di ${\displaystyle {\mathcal {P}}(A)}$ con quella di ${\displaystyle A}$ è espressa dalla disequazione ${\displaystyle 2^{\aleph _{0}}>\aleph _{0}}$. In particolare, l'insieme delle parti di un insieme numerabile (o non numerabile) è un insieme non numerabile.

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 insieme. Di conseguenza, i livelli gerarchici delle cardinalità infinite sono anch'esse infinite.^[1]

Dimostrazione

Sia ${\displaystyle f}$  una generica funzione da ${\displaystyle A}$  nell'insieme delle parti di ${\displaystyle A}$ :

${\displaystyle f\colon A\to {\mathcal {P}}(A).}$ 

Per provare il teorema si deve mostrare che ${\displaystyle f}$  è necessariamente non suriettiva. A tal fine è sufficiente individuare un elemento di ${\displaystyle {\mathcal {P}}(A)}$  che non è nell'immagine di ${\displaystyle f}$ . Questo elemento è:

${\displaystyle B=\left\{x\in A:x\not \in f(x)\right\}\in {\mathcal {P}}(A).}$  . (Notare che se B è vuoto la dimostrazione continua a essere valida)

Per dimostrare che ${\displaystyle B}$  non è nell'immagine di ${\displaystyle f}$ , si suppone per assurdo che lo sia. Per qualche ${\displaystyle y\in A}$ , si ha allora ${\displaystyle f(y)=B}$ . Si considerano ora i due casi possibili:

${\displaystyle y\not \in B}$  oppure ${\displaystyle y\in B.}$ 

Se ${\displaystyle y\not \in B=f(y)}$  allora per la definizione di ${\displaystyle B}$  si ha ${\displaystyle y\in B}$ , assurdo.

Se ${\displaystyle y\in B=f(y)}$  allora per la definizione di ${\displaystyle B}$  si ha ${\displaystyle y\not \in B}$ , assurdo.

In entrambi i casi si ottiene una contraddizione. Quindi ${\displaystyle A}$  e il suo insieme potenza non sono equipotenti. In particolare, la cardinalità dell'insieme delle parti di ${\displaystyle A}$  è maggiore della cardinalità di ${\displaystyle A}$  perché la funzione ${\displaystyle g\colon A\to {\mathcal {P}}(A)}$  definita come ${\displaystyle g(a)=\{a\}}$  è chiaramente iniettiva.

Per una trattazione della tecnica di dimostrazione usata da Cantor si veda la voce argomento diagonale di Cantor.

Voci correlate

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

Collegamenti esterni

• Cantor, teorema di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.  
• (EN) William L. Hosch, Cantor’s theorem, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.  
• (EN) Eric W. Weisstein, Cantor's Theorem, su MathWorld, Wolfram Research.  

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

1. ^ Marco Bramanti, Pagani Carlo Domenico e Sandro Salsa, Analisi Matematica 1.