Teorema di Cantor

Il teorema di Cantor dice che l’insieme delle parti dei numeri naturali $P(\mathbb{N})$ non è numerabile , quindi che non esiste una funzione biunivoca da $P(\mathbb{N})$ a $\mathbb{N}$.

Dimostrazione ( per assurdo )

Supponiamo ( per assurdo ) che esiste una funzione biunivoca , tale che ad ogni numero naturale $n\in \mathbb{N}$ gli venga associato un sottoinsieme di $\mathbb{N}$ , chiamiamolo $A_n\subseteq \mathbb{N}$ . Quindi siccome la funzione è suriettiva , per ogni sottoinsieme $S\subseteq \mathbb{N}$ dovrà esistere un $n\in \mathbb{N}$ tale che $A_n=S$. Ora notiamo che siccome $A_n$ è un sottoinsieme di numeri naturali , $A_n$ può contenere o meno $n$ stesso , ma allora definiamo un insieme di tutti gli $n$ tale che $n$ non appartiene ad $A_n$ :

$$C=\{n\in \mathbb{N}:n\notin A_n\}$$

Ora siccome $C\subset \mathbb{N}$ , allora secondo la definizione della funzione biunivoca , dovrà esistere un certo $k\in \mathbb{N}$ tale che $C=A_k$ , beh ora ci chiediamo se $k\in C$ o no :

• se $k\notin C\underset{C=A_k}{\underbrace{⟹}}k\notin A_k⟹k\in C$ , ( dove nell’ultimo abbiamo usato la definizione di $C$ ) quindi non possono essere tutte e due , quindi $k\in C$
• se $k\in C\underset{C=A_k}{\underbrace{⟹}}k\in A_k⟹k\notin C$ , ma anche qua non possono essere tutte e due , quindi necessariamente $k\notin C$ .

ma quindi nella prima otteniamo $k\in C$ e nella seconda $k\notin C$ , e quindi per contraddizione ( siccome è assurdo e una roba non appartiene a uno e poi ci appartiene ) non può esistere la funzione biunivoca.