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:
- Supponiamo per assurdo che l'intervallo [0,1] sia numerabile.
- 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 {r1, r2, r3, ...} che esaurisce tutti i numeri reali compresi tra 0 e 1.
- 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:
- r1 = 0 . 5 1 0 5 1 1 0 ...
- r2 = 0 . 4 1 3 2 0 4 3 ...
- r3 = 0 . 8 2 4 5 0 2 6 ...
- r4 = 0 . 2 3 3 0 1 2 6 ...
- r5 = 0 . 4 1 0 7 2 4 6 ...
- r6 = 0 . 9 9 3 7 8 3 8 ...
- r7 = 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.
- 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 rk, come mostra la figura:
- r1 = 0 . 5 1 0 5 1 1 0 ...
- r2 = 0 . 4 1 3 2 0 4 3 ...
- r3 = 0 . 8 2 4 5 0 2 6 ...
- r4 = 0 . 2 3 3 0 1 2 6 ...
- r5 = 0 . 4 1 0 7 2 4 6 ...
- r6 = 0 . 9 9 3 7 8 3 8 ...
- r7 = 0 . 0 1 0 5 1 3 5 ...
- ...
- 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 rk è 5 allora la k-esima cifra di x è 4
- se la k-esima cifra di rk 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).
- All'inizio dell'argomento avevamo supposto che la nostra lista {r1, r2, r3, ... } enumerasse tutti i numeri reali compresi tra 0 e 1, quindi dovremmo avere rn = x per qualche n.
- A questo punto emerge una contraddizione: x è diverso da r1 perché differiscono almeno per la prima cifra decimale, x è diverso anche da r2 da cui differisce almeno per la seconda cifra decimale, e analogamente sarà diverso da r3, r4 e così via. In altre parole x è diverso da ogni rn; dunque abbiamo trovato un numero x in [0,1] che non fa parte della successione di partenza, ma questo contraddice la nostra ipotesi che {r1, r2, r3, ...} 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.