Argomento diagonale di Cantor

Da Wikipedia, l'enciclopedia libera.

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à.

[modifica] Non numerabilità dei numeri reali

Innanzitutto possiamo considerare invece dell'intero insieme R dei numeri reali, l'intervallo [0,1]; se questo intervallo non è numerabile a maggior ragione non potrà esserlo 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 ad 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.

1. 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 ...

   ...

2. Questa successione di cifre sulla diagonale, vista come un'espansione decimale, definisce un numero reale 0.5140235... . Ora consideriamo un nuovo numero reale x che abbia invece tutte le cifre differenti dalla 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).

3. 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.
4. A questo punto emerge una contraddizione: x è diverso da r₁ perché differiscono almeno per la prima cifra decimale, x è diverso anche da r₂ da cui differisce almeno per la seconda cifra decimale, e analogamente sarà diverso da r₃, r₄ e così via. In altre parole x è diverso da ogni r_n; dunque abbiamo trovato un numero x in [0,1] che non fa parte della successione di partenza, ma questo contraddice la nostra ipotesi che {r₁, r₂, r₃, ...} fosse una enumerazione di tutti gli elementi di [0,1] e dunque siamo giunti ad un assurdo; ne segue che l'ipotesi di partenza è falsa e cioè [0,1] non è numerabile.

[modifica] 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 potenza P(A) (contenente tutti e soli i sottoinsiemi di A) non può esistere una corrispondenza biunivoca tra A e . Come prima si ragiona per assurdo :

• supponiamo per assurdo che 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 : il modo più ovvio è quello di dire che per ogni a il nuovo sottinsieme D contiene a se e solo se , ovvero , che equivale a dire (che corrisponde a prendere l'insieme "antidiagonale")
• per come abbiamo definito D questo non può essere un insieme f(a) per nessun , infatti se c'è un per cui D = f(d) avremmo , 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 composta da una sequenza di 0 e 1: 1 in corrispondenza degli elementi 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.

[modifica] 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à sono l'indecidibilità del problema della fermata, l'esistenza di una funzione calcolabile che non è primitiva ricorsiva (vedi anche la funzione di Ackermann), l'indecidibilità dell'aritmetica di Peano. L'argomento diagonale è anche alla base del paradosso di Richard.