Il procedimento diagonale di Cantor

Domenico Luminati

Teorema 0.1 (Cantor)   Ogni funzione $f:\mathbb N\to\mathbb R$ non è suriettiva.

Dimostrazione. Data $f:\mathbb N\to\mathbb R$, per ogni $n\in\mathbb N$ sia $\{\epsilon^{(n)}_i\}_{i\in\mathbb N}$ la successione delle cifre decimali dello sviluppo decimale infinito di f(n). Ossia ogni $\epsilon^{(n)}_i$ è un numero naturale tra 0 e 9. Sia $\delta:\mathbb N\to\{1,2\}$ la funzione definita da

$$\delta(m)=\big\langle \begin{array}{lcl} 1&&\hbox{\rm {se $... ...ari}} \\ 2&&\hbox{\rm {se $m$\space \\lq e dispari}} \end{array}$$

Sia x il numero reale che ha per sviluppo decimale infinito la successione $\{\delta(\epsilon^{(i)}_i)\}_{i\in\mathbb N}$. Questo numero è diverso da tutti gli f(n), dato che per ogni n si ha che la n-esima cifra decimale di xe la n-esima cifra decimale di f(n) sono diverse (una è pari e l'altra è dispari) e questo, per l'unicità dello sviluppo decimale infinito, basta a provare che $x\ne f(n)$.     $\square$

Lo stesso procedimento può essere utilizzato per provare che le parti dei numeri naturali non sono numerabili.

Teorema 0.2   Ogni funzione $f:\mathbb N\to 2^{\mathbb N}$ non è suriettiva.

Dimostrazione. Un sottinsieme A di $\mathbb N$, può essere descritto da una successione $\{\epsilon_i\}_{i\in\mathbb N}$ costituita da 1 e 0, basta porre

$$\epsilon_i = \big \langle \begin{array}{lcl} 1 && \hbox{\rm... ... }} i \in A \\ 0&& \hbox{\rm {se }} i \notin A \end{array}$$

Chiaramente la corrispondenza tra parti di $\mathbb N$ e successioni di 0 e 1 è biunivoca (dimostrarlo!).

Sia allora $f:\mathbb N\to 2^{\mathbb N}$ e per ogni n sia $\{\epsilon^{(n)}_i\}_{i\in\mathbb N}$ la successione che rappresenta f(n). Detta $\delta:\{0,1\}\to'\{0,1\}$ la funzione definita da

$$\delta(0)=1\qquad\delta(1)=0$$

si consideri la successione $\{\epsilon_i\}$ ottenuta ponendo $\epsilon_i=\delta(\epsilon^{i}_i)$ per ogni i. Come nel caso precedente, la successione $\epsilon_i$ è diversa da tutte le precedenti, e quindi definisce un insieme diverso da tutti gli f(n).     $\square$

Osservazione 0.3   In realtà si può dimostrare che $\mathbb R$ e $2^{\mathbb N}$ sono in bigezione.

Osservazione 0.4   Osserviamo che l'insieme A definito dalla successione $\epsilon_i$ nella dimostarzione precedente, può essere descritto anche in un altro modo:

$$A =\{ i \in \mathbb N\mid i \notin f(i) \}$$

dato che

$$i \in A \iff \epsilon_i = 1 \iff \epsilon^{(i)}_i = 0 \iff i \notin f(i).$$

Questa descrizione, permette di generalizzare il teorema appena dimostrato:

Teorema 0.5 (Cantor)   Se X è un insieme, allora ogni funzione $f:X\to 2^{X}$ non è suriettiva.

Dimostrazione. Sia $f:X\to 2^{X}$ e si consideri l'insieme

$$A = \{ x\in X\mid x \notin f(x) \}.$$

Proviamo che A non è nell'immagine di f. Infatti se A=f(z) si ha un assurdo. Infatti, per definizione di A, $z\in A$ se e solo se $z\notin f(z)=A$.     $\square$