l’argomento diagonale di Cantor
Oggi sono tornato brevemente a distrarmi con un po’ di fondamenti della matematica. Non avevo mai notato nelle precedenti peregrinazioni solitarie un argomento classico come l’argomento diagonale di Cantor, che è spiegato benissimo nel solito posto che non linko neanche. L’argomento di Cantor è una specializzazione ai numeri reali del fatto che l’insieme potenza di un insieme non può essere messo in relazione biunivoca con l’insieme stesso. Ovverosia, preso un insieme A, l’insieme P(A) di tutti i sottinsiemi di A è sostanzialmente più grande di A.
L’argomento di Cantor serve a dimostrare che i numeri reali, intesi come insieme potenza dei naturali, e quindi come insieme di tutti i numeri "con infinite cifre decimali", non è numerabile, ovverosia non è possibile mettere tutti i numeri reali in fila uno per volta.
Supponiamo quindi per assurdo che sia possibile enumerare i reali. Sarà quindi possibile enumerare i reali compresi tra 0 ed 1. Scriviamo lo sviluppo decimale di questi numeri in codice binario, come se dovessimo programmare un computer (cambiare base non cambia l’essenza del ragionamento) ed enumeriamoli. Ad esempio si può avere:
1) 0 1 0 0 1 1 0 0 1 …
2) 1 1 1 0 0 1 0 0 0 …
3) 0 0 1 1 0 0 1 0 1 …
4) 0 1 0 0 0 1 1 1 0 …
5) 1 1 0 0 1 1 0 1 0 …
Prendiamo in considerazione le cifre diagonali. Queste formeranno lo sviluppo decimale di un numero reale x compreso in [0,1]:
x = 0.01101 …
Costruiamo ora un numero y scambiando nello sviluppo decimale di x gli 0 con 1 e gli 1 con 0:
y = 0.10010 …
Questo è ancora un numero reale compreso tra 0 ed 1, e quindi sarà enumerato tra gli altri. Supponiamo che sia in posizione k.
1) 0 1 0 0 1 1 0 0 1 …
2) 1 1 1 0 0 1 0 0 0 …
3) 0 0 1 1 0 0 1 0 1 …
4) 0 1 0 0 0 1 1 1 0 …
5) 1 1 0 0 1 1 0 1 0 … …k) 1 0 0 1 0 … 0 1 ? 1 0
Ora è facile convincersi che la k-esima cifra decimale di y e la k-esima cifra diagonale, ovverosia la k-esima cifra decimale di x, sono la medesima cifra. Ma sono anche cifre opposte, per definizione di y! Questo è un assurdo, quindi l’ipotesi è falsa: i numeri reali non sono numerabili.
Questo ragionamento è basato sul paradosso del mentitore:
io mento.
Se mento dico la verità, e se dico la verità mento. Si costruisce una variabile booleana i cui valori di verità sono interdipendenti. Lo stesso procedimento è alla base della dimostrazione del teorema di Goedel, in cui a partire da un insieme di assiomi sufficientemente forte da permettere la caratterizzazione dei numeri naturali si costruisce una proposizione della forma
questa proposizione non è dimostrabile.
Se falsa, allora dovrebbe esserne dimostrabile la verità, il che è assurdo. Quindi è vera. Ma se vera, allora non è dimostrabile, e quindi esistono proposizioni con un valore di verità definito all’interno della teoria ma che la teoria non permette di dimostrare. Inoltre segue come corollario che la proposizione che esprime la consistenza della teoria assiomatica è falsa: ovverosia la teoria stessa non può garantire di non portare a risultati contraddittori.
- - -
Devo confessare di essere scettico nei confronti di questo argomento, come del fatto che non esistano modelli numerabili dei numeri reali. Non che non ci creda, è che non ne sono convinto, e finché non vedo non credo. Ma non sono pronto a sostenere delle tesi, ci devo ragionare (e studiare) un po’. Per quanto riguarda il ragionamento di Cantor, quello che è fallace è la caratterizzazione dei numeri reali come numeri "di infinite cifre decimali". Per specificare una quantità continua di tali numeri serve infinita informazione. Ma se ammettiamo che la logica tratti solo predicati finiti, il numero diagonale non è definibile, e quindi non è possibile sapere quale è la sua enumerazione. I corretti assiomi dei reali sono quelli di Dedekind, e la mia preoccupazione è che non sono sicuro che coincidano con la comprensione euristica di numero reale come numero di infinite cifre decimali.
Ciao,
ho due piccole critiche: una è che l’argomento diagonale di Cantor non è per assurdo. Quello che fai è dimostrare ogni insieme numerabile di reali è strettamente contenuto nei reali stessi; cioè che ogni funzione dai naturali ai reali è non surgettiva. Quindi (per definizione) i reali sono più dei naturali.
La seconda: la possibilità di definire il numero diagonale dipende semplicemente dall’assioma della scelta. Conta in base n e definisci I_n:={0,1, … , n}(x_nn)
Adesso, per l’assioma della scelta (numerabile!) puoi scegliere una successione y_n tale che y_n è in I_n. La successione è il numero reale che cerchi (ad esempio, puoi usarli come coefficienti di una serie convergente).
L’unico punto che a me sembra dubbio è se è vero che ogni reale ha una rappresentazione come successione di decimali, ma questo mi sembra plausibile se costruisci i reali come chiusura topologica di Q.
PS: a me, peraltro, chiudere topologicamente Q mi sembra più geometrico della costruzione diretta di Dedekind
PPS: l’articolo di wiki è veramente bello
Comment by Stefano — February 7, 2009 @ 10:00 pm
Ciao,
mi fa piacere che ci sia un lettore matematico - io ho passioni borderline.
Non so se il ragionamento originale di Cantor fosse un assurdo o fosse dimostrato in modus ponendo ponens come la metti tu (le due cose sono spesso quasi indistinguibili), ma sono abbastanza convinto che nella versione qui sopra si assume la negazione della tesi e si arriva a conclusioni contraddittorie (ovviamente per dire che i reali sono di più dei naturali manca la dimostrazione che esiste almeno un’iniezione dai naturali nei reali, il che è banale). Ma forse il ragionamento non è blindato e una dimostrazione diretta è preferibile.
Sui miei dubbi, devo approfondire, per cui non mi cimento in una discussione in cui parlerei a sensazioni. Prometto un post prossimamente. Le risorse di Wikipedia sull’argomento sono fatte veramente bene. Se l’assioma della scelta pone rimedio alla situazione, allora non mi stupisco del fatto che sia così dibattuto. La mia preoccupazione è questa: noi fisici abbiamo a che fare con informazione finita (principio di indeterminazione, aumento dell’entropia, decoerenza quantistica etc.), e la finitezza dell’informazione gioca un ruolo non marginale nell’evoluzione dei sistemi; una cosa analoga a quella che succede con il teorema di Goedel ai sistemi assiomatici (vedi argomenti di Chaitin). Il che pone la domanda, una sorta di principio antropico debole: le cose ci sono senza osservatore? Aggiungo che non sono affatto un soggettivista: l’albero è caduto, anche se nessuno l’ha visto. Però mi chiedo: cosa succede se l’informazione che serve a caratterizzare ogni insieme è finita? Posso per esempio costruire un modello dei reali con soli algoritmi finiti? Quanti sarebbero questi reali, numerabili, continui, una via di mezzo a seconda della validità dell’ipotesi del continuo? O magari questo è un problema indecidibile? Ma, ripeto, spero presto di essere più preciso e convincente.
Sul PS, ho l’impressione che l’assioma di Dedekind per cui l’elemento separatore di sottinsiemi dei reali è reale sia in un certo senso la chiusura “topologica” dei razionali, in quanto si assume sostanzialmente che successioni convergenti abbiano limite in R. D’altra parte questi fatti precedono la topologia.
Comment by Administrator — February 8, 2009 @ 9:08 am
Cosa intendi con “modello numerabile dei reali”?
A me sembra che l’argomento diagonale di Cantor sia formulabile anche senza la rappresentazione decimale, che viene usata solo per visualizzarlo meglio. O sbaglio?
Comment by Stefano — February 12, 2009 @ 10:12 am
Mettiti i feed per i commenti! Se no impazzisco a ricordarmi dove sto discutendo…
Comment by Stefano — February 12, 2009 @ 10:13 am
Caro Stefano, se scopro come si fa, aggiungo i feed. Ma temo che blogsome non me lo permetta.
Quanto al modello numerabile dei reali, lo so che è una bestemmia, ma non capisco perché e devo convincermene. Le risorse on-line che ho consultato non sono sufficienti, per cui dovrò armarmi di pazienza e libri. Sii indulgente.
In primo luogo, osservo che tutte le dimostrazioni che sono riuscito a trovare del fatto che i reali siano un continuo, compreso l’argomento di Cantor, in qualche modo più o meno raffinato PRESUMONO che ci sia infinita informazione contenuta in un numero reale, per esempio nel suo sviluppo decimale (un infinito numerabile di cifre arbitrarie). E quindi poi è facile arrivare alla conclusione che sono quante le biiezioni dei naturali in se stessi. Forse si può raffinare l’argomento di Cantor, ma la polvere và a finire da qualche parte sotto il tappeto. Se conosci una dimostrazione “topologica” a partire dai meri assiomi di Dedekind, smetterei di farneticare.
Il ragionamento euristico è questo: supponiamo che esista un modello dei reali numerabile. Allora, dirai, li metto in fila e produco con l’argomento di Cantor un assurdo. Ma solo se è possibile metterli in fila: potrebbe essere impossibile assegnare una numerazione.
Considera ad esempio i numeri definibili da formule di lunghezza finita (supponiamo sempre finita informazione) in una qualche logica (primo, second’ordine o altro, a seconda di dove fai viaggiare i quantificatori e quante variabili assumi). Tra questi vi sono numeri non computabili con una macchina di Turing (il numero di Chaitin ad esempio), di cui non posso conoscere la numerazione di Goedel. Quindi l’argomento di Cantor fallisce. Ma fin qua abbiamo solo stabilito che non è detto che i numeri definibili in qualche modo non siano numerabili, pur contenendo tutti i numeri di cui abbiamo bisogno per vivere, e per definizione non contenendo nessun controesempio esprimibile in quello stesso linguaggio.
Ora mi chiedo se però non vi siano insiemi numerabili di numeri definibili “in qualche modo” ben ordinati che comprendano tutti i tagli di Dedekind dell’insieme. Questi costituirebbero un modello numerabile dei reali.
Altrimenti, mi piacerebbe sapere che esiste una dimostrazione che i tagli di Dedekind di un insieme di numeri definiti in un certo linguaggio finito non sono mai tutti definiti in quello stesso linguaggio. Sarebbe un fatto meraviglioso.
Ma ancora più meraviglioso sarebbe se tutte queste questioni fossero indecidibili. E’ il mio sogno, che tutto sia sotto sotto indecidibile, comprese le “teorie del tutto” in fisica teorica, il problema della misura in quantistica, l’espansione accelerata dell’Universo in cosmologia.
Comment by Administrator — February 12, 2009 @ 2:00 pm
Guardate che questo blog ha il feed dei commenti, anche se penso di essere l’unico iscritto: http://tomate.blogsome.com/comments/feed
Comment by masaccio — February 12, 2009 @ 6:11 pm
@masaccio: grazie per il consiglio
sui modelli numerabili dei reali: quello che dici è interessante, tanto più che esiste una dimostrazione topologica (molto semplice, ma non me la ricordo, forse è da qualche parte sul mio blog) che i numeri naturali sono infiniti. A occhio e croce mi sembra unaconseguenza di un qualche teorema di Baira. Ci penso su e ti faccio sapere.
Comment by Stefano — February 17, 2009 @ 8:21 am
Ci ho messo un po’, ma ho due dimostrazioni.
La prima secondo Baire, semplice semplice: uno spazio metrico completo non può essere l’unione numerabile di insiemi mai densi. Se R fosse numerabile, allora sarebbe l’unione numerabile dei suoi punti isolati, che sono ovviamente insiemi mai densi. Ne deduciamo che R non è numerabile.
La seconda è più diretta, ed è nota come la prima dimostrazione di incontabilità di Cantor. Usa solo la definizione di Dedekind di numero realie. La trovi su Wiki a
http://en.wikipedia.org/wiki/Cantor%27s_first_uncountability_proof
Nonostante che questa dimostrazione sia diretta, preferisco Baire che mi sembra più semplice. È vero che Baire dipende dall’assioma della scelta dipendente, ma mi chiedevo se è possibile dimostrare che i reali esistono solo in ZF, cosa che renderebbe la seconda dimostrazione comunque dipendente da qualche assioma della scelta.
Comment by Stefano — February 17, 2009 @ 7:41 pm
Ti ringrazio, mi prendo un po ‘di tempo per guardarle bene e riflettere. Un paio di osservazioni preliminari riguardo alla dimostrazione di Cantor.
In primo luogo, dimostrare che R non è numerabile non significa che sia necessariamente continuo; questo dipende dall’ipotesi del continuo che è indipendente da ZF + assioma della scelta. La corrispondenza biunivoca tra reali e l’insieme delle parti dei naturali in qualche modo sembra attingere comunque all’idea intuitiva dei reali come successioni di infinite cifre decimali arbitrarie.
In secondo luogo, la numerabilità viene impiegata mettendo in successione tutti gli elementi di R, come nell’argomento diagonale. Sicuramente un modello dei reali numerabili non potrebbe permettere l’esistenza di una tale successione (altrimenti l’argomento diagonale è gia più che sufficiente), e a questo proposito tiravo in ballo la differenza tra numeri definibili e computabili. In soldoni, il fatto che esista una corrispondenza biunivoca con i naturali (definizione di numerabilità) non implica necessariamente che questa corrispondenza sia esplicitabile. Situazione paradossale, sicuramente, ma verosimile. E’ analoga alla situazione che si crea quando si dimostra che non è computabile la numerazione di Goedel della proposizione vera “questa proposizione non è dimostrabile”. Ci sono numeri reali perfettamente ben definiti ma non computabili, come il numero di Chaitin che incorpora l’essenza del teorema di Goedel, e anche numeri naturali definibili e non computabili, come i numeri generati dalle funzioni busy-beaver. Se per ipotesi includessi un tale numero nella successione che compare nella dimostrazione di Cantor, starei in pratica negando il teorema di Goedel.
Forse pensare di poter costruire un modello numerabile dei reali è azzardato. Ma comincio a credere (del tutto fideisticamente) che possa essere impossibile dimostrare che non esistono modelli numerabili.
Comment by Administrator — February 17, 2009 @ 11:03 pm
Ciao,
leggendomi ieri la discussione sull’articolo della wikipedia inglese sui numeri reali, mi sono anche imbattuto su questo commento
http://en.wikipedia.org/wiki/Talk:Real_number#Local_field
dove Michael Hardy (che è un PhD in logica) spiega qualcosa riguardo all’esistenza di modelli numerabili dei reali. Non ci capisco molto, ma magari a te interessa.
Buona giornata
Stefano
Comment by Stefano — February 18, 2009 @ 8:12 am
masaccio, siamo almeno in due
Comment by hronir — February 18, 2009 @ 9:09 am