Nella discussione su questo post di tomate, ci si chiedeva se ci fosse una dimostrazione topologica, non basata sull'argomento diagonale di Cantor, del fatto che i numeri reali sono sovrannumerabili.
Sicuramente ve n'è una, nota come prima dimostrazione di non contabilità di Cantor, che è dovuta allo stesso Cantor. Leggasi la dimostrazione su Wikipedia.
Una dimostrazione più rapida è basata sul teorema di Baire. Il teorema di Baire afferma che uno spazio metrico completo non può essere unione numerabile di insiemi mai densi.
Un insieme mai denso è un insieme la cui chiusura ha insieme complementare denso.
Torniamo alla dimostrazione del teorema "R è sovrannumeabile". Ovviamente R è l'unione dei suoi punti. Ognuno dei suoi punti è evidentemente un insieme mai denso. Dato che R è completo, dal teorema di Baire si deduce che non è numerabile.
Faccio notare che la facilità della dimostrazione di questo teorema rispetto alla dimostrazione originale di Cantor è dovuta al fatto che il teorema di Baire è equivalente all'assioma della scelta dipendente.
Visualizzazione post con etichetta numeri reali. Mostra tutti i post
Visualizzazione post con etichetta numeri reali. Mostra tutti i post
martedì, marzo 03, 2009
sabato, maggio 24, 2008
Più infinito
Qualche giorno fa ho spiegato i concetti di equipotenza e di infinito. In particolare, ho mostrato che i due concetti sono strettamente legati perchè un insieme è infinito se e solo se è equipotente ad una sua parte propria.
Ad esempio, i naturali sono equipotenti ai quadrati perfetti, essi sono una parte propria dei naturali, quindi l'insieme dei naturali è infinito.
La questione fondamentale è, ripeto, se i due insiemi infiniti dei quadrati perfetti e dei naturali siano equipotenti.
Sorge spontanea la domanda:
Domanda
Ogni due insiemi infiniti sono tra loro equipotenti?
La risposta è molto semplice:
Risposta
No. Controesempio: i numeri reali sono di più dei numeri naturali.
Dimostrazione
Dato che ogni naturale è reale, è chiaro che i reali sono almeno quanto i naturali. Dobbiamo quindi dimostrare l'impossibilità di trovare una funzione suriettiva dai naturali ai reali. È sufficiente dimostrare che non esiste una funzione biettiva da N all'intervallo (0,1) che è strettamente contenuto nei reali.
Consideriamo funzione iniettiva dai naturali ai reali. Per ogni naturale n, abbiamo un reale r, che provvederemo a scrivere nella sua notazione decimale, possibilmente infinita. Adesso abbiamo una lista numerata di tutti i reali scritti in notazione decimale.
Ad esempio:
1 --> 0.333333.........
2 --> 0.25000000000....
3 --> 0.23417171717....
4 --> 0.10000000000....
5 --> 0.1245389457[...]
e così via. I punti normali ... significano che il periodo viene ripetuto per sempre, i puntini nelle parentesi [...] significano che il numero non è periodico.
Adesso costruiamo un numero c in questa maniera:
- come cifra intera prendiamo lo 0;
- come prima cifra decimale prendiamo 0, se la prima cifra decimale del primo numero della lista non è 0 e prendiamo 1 se la prima cifra decimale del primo numero della lista è 0;
- come seconda cifra decimale prendiamo 0, se la prima cifra decimale del secondo numero della lista non è 0 e prendiamo 1 se la seconda cifra decimale del secondo numero della lista è 0;
- e così via per tutti i naturali...
nel caso precedente c avrà la seguente forma
c = 0.00010[...]
Adesso notiamo che c è un numero reale fra 0 e 1, dato che ha una notazione decimale ben definita. Per verificare che la nostra lista sia suriettiva, dobbiamo verificare che c sia nella lista. Immaginiamo che c sia il 125° numero della lista. Adesso vediamo che la 125° cifra di c è 0 se la 125° cifra del 125° numero non era 0 e 1 se era 0. Quindi essi differiscono nel loro sviluppo decimale e quindi, risparmiandoci i dettagli tecnici sul fatto che due numeri diversi possano avere lo stesso sviluppo decimale, abbiamo dimostrato che c non può essere nella lista.
Riassumendo: abbiamo appena trovato un reale c che non è contenuto nella lista, cioè non è immagine di nessun numero naturale per la nostra funzione iniettiva. Quindi la funzione non è suriettiva. Q.e.d.
Quello che avete appena visto in azione è il temibile argomento diagonale di Cantor del 1891, una delle armi matematiche più terribili mai sviluppate al mondo.
La cosa più inquietante, è che fino al 1891, ripeto: milleottocentonovantuno!, non si erano accorti di questo fenomeno che adesso è possibile spiegare a chiunque...
Ad esempio, i naturali sono equipotenti ai quadrati perfetti, essi sono una parte propria dei naturali, quindi l'insieme dei naturali è infinito.
La questione fondamentale è, ripeto, se i due insiemi infiniti dei quadrati perfetti e dei naturali siano equipotenti.
Sorge spontanea la domanda:
Domanda
Ogni due insiemi infiniti sono tra loro equipotenti?
La risposta è molto semplice:
Risposta
No. Controesempio: i numeri reali sono di più dei numeri naturali.
Dimostrazione
Dato che ogni naturale è reale, è chiaro che i reali sono almeno quanto i naturali. Dobbiamo quindi dimostrare l'impossibilità di trovare una funzione suriettiva dai naturali ai reali. È sufficiente dimostrare che non esiste una funzione biettiva da N all'intervallo (0,1) che è strettamente contenuto nei reali.
Consideriamo funzione iniettiva dai naturali ai reali. Per ogni naturale n, abbiamo un reale r, che provvederemo a scrivere nella sua notazione decimale, possibilmente infinita. Adesso abbiamo una lista numerata di tutti i reali scritti in notazione decimale.
Ad esempio:
1 --> 0.333333.........
2 --> 0.25000000000....
3 --> 0.23417171717....
4 --> 0.10000000000....
5 --> 0.1245389457[...]
e così via. I punti normali ... significano che il periodo viene ripetuto per sempre, i puntini nelle parentesi [...] significano che il numero non è periodico.
Adesso costruiamo un numero c in questa maniera:
- come cifra intera prendiamo lo 0;
- come prima cifra decimale prendiamo 0, se la prima cifra decimale del primo numero della lista non è 0 e prendiamo 1 se la prima cifra decimale del primo numero della lista è 0;
- come seconda cifra decimale prendiamo 0, se la prima cifra decimale del secondo numero della lista non è 0 e prendiamo 1 se la seconda cifra decimale del secondo numero della lista è 0;
- e così via per tutti i naturali...
nel caso precedente c avrà la seguente forma
c = 0.00010[...]
Adesso notiamo che c è un numero reale fra 0 e 1, dato che ha una notazione decimale ben definita. Per verificare che la nostra lista sia suriettiva, dobbiamo verificare che c sia nella lista. Immaginiamo che c sia il 125° numero della lista. Adesso vediamo che la 125° cifra di c è 0 se la 125° cifra del 125° numero non era 0 e 1 se era 0. Quindi essi differiscono nel loro sviluppo decimale e quindi, risparmiandoci i dettagli tecnici sul fatto che due numeri diversi possano avere lo stesso sviluppo decimale, abbiamo dimostrato che c non può essere nella lista.
Riassumendo: abbiamo appena trovato un reale c che non è contenuto nella lista, cioè non è immagine di nessun numero naturale per la nostra funzione iniettiva. Quindi la funzione non è suriettiva. Q.e.d.
Quello che avete appena visto in azione è il temibile argomento diagonale di Cantor del 1891, una delle armi matematiche più terribili mai sviluppate al mondo.
La cosa più inquietante, è che fino al 1891, ripeto: milleottocentonovantuno!, non si erano accorti di questo fenomeno che adesso è possibile spiegare a chiunque...
giovedì, aprile 03, 2008
Teoremi di Baire (III)
Signore e signori, oggi un'applicazione spettacolare del teorema di Baire-Hausdorff.
È noto a tutti che l'insieme dei numeri razionali Q, dotato della distanza d(x,y)=|x-y| non è uno spazio metrico completo. Per chiarire questo problema si porta di solito il seguente
1. Esempio
La radice di 2 è reale e non razionale. La radice di 2 può essere approssimata tramite numeri razionali. Quindi lo spazio metrico dei razionali non è completo.
Questo esempio in forma sillogistica è corretto, tuttavia ha un problema; il secondo termine non è così semplice da dimostrare; la maniera più semplice mi pare quella di definire la funzione radice, dimostrare che è continua et cetera.
Tuttavia questo approccio ha lo svantaggio che bisogna utilizzare uno strumento raffinato (l'analisi) per dimostrare una proposizione di una disciplina più primitiva (la topologia).
Guardate invece cosa si ottiene col teorema di Baire-Hausdorff.
2. Teorema
Lo spazio metrico (Q, d) non è completo.
Dimostrazione
Si noti che la topologia indotta dalla metrica d è esattamente ciò che si aspetta; un insieme è aperto se ogni suo punto contiene una palla di numeri razionali.
Osserviamo che un insieme ridotto ad un punto singolo q è mai denso; infatti ogni palla aperta di Q contiene infiniti elementi.
Questo si vede così: sia q in Q e r un numero reale e si consideri la palla di raggio r e centro q. Si scelga adesso un numero razionale s compreso fra 0 e r; è possibile farlo dato che ogni numero reale ha uno sviluppo decimale. Quindi q-s, q e q+s sono nella palla; ergo la palla non può essere contenuta nell'insieme costituito dal solo elemento q.
Ricordiamo che Q è numerabile; questo perchè Q è l'insieme di tutte le frazioni e quindi è isomorfo a un sottoinsieme di N x N.
Dunque Q è uno spazio metrico ed è l'unione numerabile di insiemi mai densi. Quindi non può essere completo.
Si ricordi ora l'esempio; la facevamo vedere che esistono alcune successioni di Cauchy di razionali (quelle convergenti a radice di 2) che non convergono ad un numero razionale. Facevamo quindi vedere che Q è localmente non completo intorno a radice di 2.
L'attento lettore avrà notato che la dimostrazione precedente può essere generalizzata per dimostrare che Q è mai completo!
3. Definizione
Unp spazio metrico (X,d) è mai completo se per nessun numero reale r strettamente positivo e nessun elemento x lo spazio metrico (B(r,x),d) è completo.
Qua B(r,x) è la palla di centro x e raggio r e la distanza d è la stessa distanza dello spazio metrico ambiente.
4. Teorema
Lo spazio metrico (B(r,x),d) è mai completo.
Dimostrazione
Come nella precedente dimostrazione, ogni insieme ridotto ad un solo punto è mai denso. B(r,x) è numerabile in quanto sottoinsieme di un insieme numerabile. Quindi B(r,x) non è completo.
È noto a tutti che l'insieme dei numeri razionali Q, dotato della distanza d(x,y)=|x-y| non è uno spazio metrico completo. Per chiarire questo problema si porta di solito il seguente
1. Esempio
La radice di 2 è reale e non razionale. La radice di 2 può essere approssimata tramite numeri razionali. Quindi lo spazio metrico dei razionali non è completo.
Questo esempio in forma sillogistica è corretto, tuttavia ha un problema; il secondo termine non è così semplice da dimostrare; la maniera più semplice mi pare quella di definire la funzione radice, dimostrare che è continua et cetera.
Tuttavia questo approccio ha lo svantaggio che bisogna utilizzare uno strumento raffinato (l'analisi) per dimostrare una proposizione di una disciplina più primitiva (la topologia).
Guardate invece cosa si ottiene col teorema di Baire-Hausdorff.
2. Teorema
Lo spazio metrico (Q, d) non è completo.
Dimostrazione
Si noti che la topologia indotta dalla metrica d è esattamente ciò che si aspetta; un insieme è aperto se ogni suo punto contiene una palla di numeri razionali.
Osserviamo che un insieme ridotto ad un punto singolo q è mai denso; infatti ogni palla aperta di Q contiene infiniti elementi.
Questo si vede così: sia q in Q e r un numero reale e si consideri la palla di raggio r e centro q. Si scelga adesso un numero razionale s compreso fra 0 e r; è possibile farlo dato che ogni numero reale ha uno sviluppo decimale. Quindi q-s, q e q+s sono nella palla; ergo la palla non può essere contenuta nell'insieme costituito dal solo elemento q.
Ricordiamo che Q è numerabile; questo perchè Q è l'insieme di tutte le frazioni e quindi è isomorfo a un sottoinsieme di N x N.
Dunque Q è uno spazio metrico ed è l'unione numerabile di insiemi mai densi. Quindi non può essere completo.
Si ricordi ora l'esempio; la facevamo vedere che esistono alcune successioni di Cauchy di razionali (quelle convergenti a radice di 2) che non convergono ad un numero razionale. Facevamo quindi vedere che Q è localmente non completo intorno a radice di 2.
L'attento lettore avrà notato che la dimostrazione precedente può essere generalizzata per dimostrare che Q è mai completo!
3. Definizione
Unp spazio metrico (X,d) è mai completo se per nessun numero reale r strettamente positivo e nessun elemento x lo spazio metrico (B(r,x),d) è completo.
Qua B(r,x) è la palla di centro x e raggio r e la distanza d è la stessa distanza dello spazio metrico ambiente.
4. Teorema
Lo spazio metrico (B(r,x),d) è mai completo.
Dimostrazione
Come nella precedente dimostrazione, ogni insieme ridotto ad un solo punto è mai denso. B(r,x) è numerabile in quanto sottoinsieme di un insieme numerabile. Quindi B(r,x) non è completo.
venerdì, luglio 06, 2007
impressioni
legend has it that the discovery was made at sea and that hippasus' fellow pythagoreans threw him overboard.
wikipedia su ippaso da metaponto
ieri sono stato ad un talk di barbara hammer: era un overview su tutto quello che si può dire sulle reti neurali ricorrenti.
di questo bellissimo talk mi ha in particolare colpito una cosa che lei ha detto di sfuggita e che già sapevo; cioè che le macchine di turing non possono manipolare i numeri reali e che, se potessero, allora porebbero fare veramente qualcosa di più. mi si perdoni il linguaggio poco scientifico, ma sono le 8 di mattina...
quindi siamo andati alla grigliata della facoltà di informatica, e seduti ad un tavolo, gustandomi il mio buon tannenzäpfle, ho potuto assistere ad un'accesa discussione fra lei, g.p. e c.t. sul problema dei numeri reali; che, afferma sempre g.p., tanto reali non possono essere, dato che si può sopravvivere benissimo senza di essi, approssimando tutto in maniera razionale.
a quel punto mi sono ricordato di una conversazione con r.n. in cui lui mi spiegava che, se si decide di essere rigorosamente costruttivisti, allora ogni funzione su R è automaticamente continua. purtroppo non ricordo come funzionava la dimostrazione. che ci sia una connessione frai due fatti, si vede subito: accettare di approssimare tutto con razionali, è simile al punto di vista costruttivista dell'accettare solo numeri creati da un algoritmo.
e poi mi è venuto in mente che quando si esegue l'analisi di fourier, la continuità della funzione influisce sulla velocità di convergenza della sua serie di fourier. da questo punto di vista, dato che la serie di fourier è un ente fisico, o almeno oggi mi piace pensarla così, se si accetta questa serie di impressioni e analogie come fossero un ragionamento, sembra quasi che ci sia una possibilità di verificare fisicamente l'esistenza dei numeri reali.
wikipedia su ippaso da metaponto
ieri sono stato ad un talk di barbara hammer: era un overview su tutto quello che si può dire sulle reti neurali ricorrenti.
di questo bellissimo talk mi ha in particolare colpito una cosa che lei ha detto di sfuggita e che già sapevo; cioè che le macchine di turing non possono manipolare i numeri reali e che, se potessero, allora porebbero fare veramente qualcosa di più. mi si perdoni il linguaggio poco scientifico, ma sono le 8 di mattina...
quindi siamo andati alla grigliata della facoltà di informatica, e seduti ad un tavolo, gustandomi il mio buon tannenzäpfle, ho potuto assistere ad un'accesa discussione fra lei, g.p. e c.t. sul problema dei numeri reali; che, afferma sempre g.p., tanto reali non possono essere, dato che si può sopravvivere benissimo senza di essi, approssimando tutto in maniera razionale.
a quel punto mi sono ricordato di una conversazione con r.n. in cui lui mi spiegava che, se si decide di essere rigorosamente costruttivisti, allora ogni funzione su R è automaticamente continua. purtroppo non ricordo come funzionava la dimostrazione. che ci sia una connessione frai due fatti, si vede subito: accettare di approssimare tutto con razionali, è simile al punto di vista costruttivista dell'accettare solo numeri creati da un algoritmo.
e poi mi è venuto in mente che quando si esegue l'analisi di fourier, la continuità della funzione influisce sulla velocità di convergenza della sua serie di fourier. da questo punto di vista, dato che la serie di fourier è un ente fisico, o almeno oggi mi piace pensarla così, se si accetta questa serie di impressioni e analogie come fossero un ragionamento, sembra quasi che ci sia una possibilità di verificare fisicamente l'esistenza dei numeri reali.
Iscriviti a:
Post (Atom)
