Argomento diagonale di Cantor

L'argomento diagonale di Cantor è una tecnica dimostrativa con cui Georg Cantor ha dimostrato la non numerabilità dei numeri reali. La tecnica di Cantor è stata usata in numerose varianti per ottenere risultati nell'ambito della logica matematica e della teoria della calcolabilità.

Non numerabilità dei numeri reali

Innanzitutto possiamo considerare, invece dell'intero insieme $\mathbb {R}$ dei numeri reali, l'intervallo [0,1]; se quest'intervallo non è numerabile a maggior ragione non potrà esserlo $\mathbb {R}$ .

La dimostrazione procede per assurdo nel modo seguente:

1. Supponiamo per assurdo che l'intervallo [0,1] sia numerabile.

2. Questo significa che gli elementi di [0,1] possono essere posti in corrispondenza biunivoca con i numeri naturali, dando luogo a una successione di numeri reali {r₁, r₂, r₃, ...} che esaurisce tutti i numeri reali compresi tra 0 e 1.

3. Possiamo rappresentare ciascun numero della successione in forma decimale e visualizzare la successione di numeri reali come una matrice infinita che avrà più o meno quest'aspetto:

r₁ = 0, 5 1 0 5 1 1 0 ...

r₂ = 0, 4 1 3 2 0 4 3 ...

r₃ = 0, 8 2 4 5 0 2 6 ...

r₄ = 0, 2 3 3 0 1 2 6 ...

r₅ = 0, 4 1 0 7 2 4 6 ...

r₆ = 0, 9 9 3 7 8 3 8 ...

r₇ = 0, 0 1 0 5 1 3 5 ...

...

In realtà ci sono numeri che hanno più di una rappresentazione decimale: quelli che terminano con una sequenza infinita di 9 o di 0 ne hanno due. In tal caso conveniamo di prendere la rappresentazione che termina con 0.

4. Ora concentriamo la nostra attenzione sulle cifre lungo la diagonale della matrice, cioè sulla successione il cui k-esimo elemento è la k-esima cifra decimale di r_k, come mostra la figura:

r₁ = 0, 5 1 0 5 1 1 0 ...

r₂ = 0, 4 1 3 2 0 4 3 ...

r₃ = 0, 8 2 4 5 0 2 6 ...

r₄ = 0, 2 3 3 0 1 2 6 ...

r₅ = 0, 4 1 0 7 2 4 6 ...

r₆ = 0, 9 9 3 7 8 3 8 ...

r₇ = 0, 0 1 0 5 1 3 5 ...

...

5. Questa successione di cifre sulla diagonale, vista come un'espansione decimale, definisce il numero reale 0,5140235... . Ora consideriamo un nuovo numero reale x le cui cifre siano tutte differenti da quelle della sequenza sulla diagonale. Un modo per definire un numero siffatto è il seguente: x è il numero reale compreso tra 0 e 1 tale che

se la k-esima cifra decimale di r_k è 5 allora la k-esima cifra di x è 4
se la k-esima cifra di r_k non è 5 allora la k-esima cifra decimale di x è 5

Nell'esempio otteniamo:

x = 0 , 4 5 5 5 5 5 4 ...

In realtà ci sono diversi modi di definire numeri con tutte le cifre diverse dalla diagonale: per esempio si potrebbe prendere la cifra successiva modulo 9. Ai fini della dimostrazione l'importante è che non si possa ottenere un x che termina con 9 periodico (perché in tal caso la sua differenza dai numeri elencati della matrice potrebbe essere solo apparente).

6. All'inizio dell'argomento avevamo supposto che la nostra lista {r₁, r₂, r₃, ... } enumerasse tutti i numeri reali compresi tra 0 e 1, quindi dovremmo avere r_n = x per qualche n e poiché x non ha dei 9 tra le cifre decimali la sua rappresentazione è unica. Tale unica rappresentazione dovrà quindi essere quella presente nella riga n-esima della tabella.

7. A questo punto emerge una contraddizione: sia a la n-esima cifra decimale di r_n = x. Essa può essere 4 o 5. Per come è definito x la cifra a deve essere 4 se e solo se è uguale a 5 e 5 se e solo se è diversa da 5. Questo è impossibile e ne segue che l'ipotesi di partenza è falsa e cioè [0,1] non è numerabile.

Il teorema sulla cardinalità

L'idea appena esposta per i numeri reali si può generalizzare per dimostrare che dato un qualunque insieme $A$ e il suo insieme delle parti ${\mathcal {P}}(A)$ (contenente tutti e soli i sottoinsiemi di A) non può esistere una corrispondenza biunivoca tra $A$ e ${\mathcal {P}}(A)$ . Come prima si ragiona per assurdo:

supponiamo per assurdo che $f:A\to {\mathcal {P}}(A)$ sia una corrispondenza biunivoca.
costruiamo un nuovo sottoinsieme $D$ di $A$ in maniera che questo non possa essere nessuno degli insiemi $f(a)$ per ogni $a\in A$ : il modo più ovvio è quello di dire che per ogni $a$ il nuovo sottoinsieme $D$ contiene $a$ se e solo se $a\notin f(a)$ , ovvero $D=\{a\in A|a\notin f(a)\}$ , che equivale a dire $a\in D\iff a\notin f(a)$ (che corrisponde a prendere l'insieme "antidiagonale")
per come abbiamo definito $D$ questo non può essere un insieme $f(a)$ per nessun $a\in A$ , infatti se c'è un $d\in A$ per cui $D=f(d)$ avremmo $d\in D=f(d)\iff d\notin f(d)$ , che è una contraddizione.

Osserviamo che in questo caso non si può "visualizzare" l'ipotetica corrispondenza biunivoca (come accadeva prima) perché l'insieme $A$ potrebbe essere non numerabile, tuttavia si può immaginare anche in questo caso che $f$ definisca idealmente una matrice infinita con $|A|$ (cardinalità di $A$ ) righe per $|A|$ colonne, con valori 0 e 1 e che ha una riga per ogni $a\in A$ composta da una sequenza di 0 e 1: 1 in corrispondenza degli elementi $x\in A$ che sono in $f(a)$ e 0 per quelli che non ci sono. Anche in questo caso si può individuare una "diagonale" composta dagli elementi di "coordinate" $(a,f(a))$ e costruire una "riga" che sia l'opposto della diagonale (cioè contenga uno 0 per ogni 1 sulla diagonale e viceversa) e il risultato è precisamente l'insieme $D$ che abbiamo definito sopra.

Altri usi dell'argomento diagonale

Altre dimostrazioni ottenute mediante l'argomento diagonale si trovano soprattutto nell'ambito della logica matematica e della teoria della computabilità. Esse sono l'indecidibilità del problema della terminazione, l'esistenza di una funzione calcolabile che non è primitiva ricorsiva (vedi anche la funzione di Ackermann), l'indecidibilità dell'aritmetica di Peano e pure nel teorema di Ascoli-Arzelà se ne fa uso. L'argomento diagonale è anche alla base del paradosso di Richard.

Costruttivismo e argomento diagonale

La dimostrazione indicata sopra non è costruttiva: è vero che il numero diagonale viene costruito, ma l'assunto iniziale di avere una lista di tutti i numeri non costruisce effettivamente tale lista o, se si preferisce, non dà un algoritmo per calcolare in tempo finito qual è la posizione di un numero dato. Essa è quindi rifiutata dalla scuola costruttivista. La maggior parte dei matematici però accetta questa dimostrazione come valida.