Teorema. Sia $X$ un insieme e $f: X-> P(X)$. Esiste $N\subseteq X$ che non appartiene all'immagine di $f$.
Prova.
Definizione Una traccia e' una sequenza (finita o infinita) di elementi di $X$ $s_0,s_1,s_2,...$ tale che, per ogni $i\in NN$, $s_{i+1}\in f(s_i)$.
Un elemento $s\in X$ si dice semplice se ogni traccia che inizia con $s$ e' finita.
Sia $N$ l'insieme degli elementi semplici. Supponiamo per assurdo che esista $n\in X$ tale che $f(n)=N$. Osserviamo che $n$ e' semplice, perche' il secondo elemento di ogni traccia che inizia con $n$ e' semplice, e quindi la detta traccia e' finita; dunque $n\in N=f(n)$. Ma allora la sequenza $n,n,n,....$ e' una traccia infinita: assurdo.
Il teorema di Cantor e' uno dei piu' profondi di sempre: merita.
) motivo molti la presentano per assurdo.