Cantor

Analisi, algebra lineare, topologia, gruppi, anelli, campi, ...
Rispondi
Avatar utente
dimpim
Messaggi: 300
Iscritto il: 01 gen 1970, 01:00

Cantor

Messaggio da dimpim » 28 feb 2005, 13:46

Scusate se questa non è forse la sezione più adatta per una richiesta del genere, ma non sono riuscito a trovare una collocazione migliore...
[Spostato in Matematica non elementare. M.]

Qualcuno di voi sa dirmi dove posso trovare la dimostrazione di Cantor sulla numerabilità dell'insieme dei reali (spero di aver scritto tutto giusto :roll: )? Ho provato con Google, ma non ho avuto risultati soddisfacenti...
Grazie in anticipo.

Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Re: Cantor

Messaggio da Boll » 28 feb 2005, 14:03

dimpim ha scritto:Scusate se questa non è forse la sezione più adatta per una richiesta del genere, ma non sono riuscito a trovare una collocazione migliore...

Qualcuno di voi sa dirmi dove posso trovare la dimostrazione di Cantor sulla numerabilità dell'insieme dei reali (spero di aver scritto tutto giusto :roll: )? Ho provato con Google, ma non ho avuto risultati soddisfacenti...
Grazie in anticipo.
Ehm, i reali non sono numerabili... Semmai potrai trovare la dimostrazione della non numerabilità dei reali, se poi ho tempo te la scrivo qui

Avatar utente
dimpim
Messaggi: 300
Iscritto il: 01 gen 1970, 01:00

Messaggio da dimpim » 28 feb 2005, 14:17

Boll ha scritto:Ehm, i reali non sono numerabili...
Ecco, lo sapevo che facevo la figuraccia... :oops:
Comunque grazie!

MindFlyer

Messaggio da MindFlyer » 28 feb 2005, 17:03

La dimostrazione di Cantor sulla non numerabilità di $ \mathbb R $ si basa sul cosiddetto procedimento diagonale, che è usato un po' dappertutto per dimostrare varie cose, ed ha anche delle appilcazioni nella teoria della calcolabilità.

Applicare il procedimento diagonale sui reali è molto fastidioso, per via della non unicità dell'espressione decimale (o in una qualunque base). Dimostrarlo per l'insieme delle parti di $ \mathbb N $ è più comodo, e permette di esibire il procedimento diagonale senza altri fronzoli... Dopodiché, potresti passare a dimostrare che le parti di $ \mathbb N $ sono equipotenti a $ \mathbb R $. Anche se in tal caso non è strettamente necessario ricorrere al procedimento diagonale, perché esiste la dimostrazione universale che nessun insieme è equipotente alle parti di sé stesso.

Avatar utente
pazqo
Messaggi: 155
Iscritto il: 01 gen 1970, 01:00
Località: san giorgio di nogaro
Contatta:

Messaggio da pazqo » 28 feb 2005, 18:43

Scusami, ma voglio fare il polemico. Il nostro amico dimpim non ha nemmeno la nozione di numero reale, presumo. Mi pare un po' difficile spiegargli la dimostrazione senza che sappia come è definito l'insieme dei reali, no? Ci vuole qualche nozione... è come se pretendessi di capire perché le equazioni di Shroedinger funzionano, io che di fisica sono e rimmarrò fermo alla relatività...
Purtroppo la matematica è affascinante e viene la voglia di sapere anche non sapendo:-)

Non sai quanta gente pretende di leggere la dimostrazione di Wiles del teorema di Fermat senza conoscere un po' di geometria algebrica delle curve...

purtroppo certe spiegazioni possono essere date solo a chi ah una certa familiarità con certi concetti. "Non esiste via regia alla matemematica" e "per aspera ad astra" sono due detti che a parer mio rappresentano bene la matematica...

Non è una critica a te, ma al nostro amico. prima di fare domande, è bene sapere di cosa si sta parlando. e se non si è sicuri si chiede: Come si definiscono i reali? cosa vuol dire numerabile? etc...
Stefano 'Pazqo' Pascolutti

A good mathematical joke is better, and better mathematics, than a dozen of mediocre papers -John Edensor LITTLEWOOD-

Use [tex]\LaTeX[/tex] in your math messages!

www.pazqo.altervista.org

Avatar utente
dimpim
Messaggi: 300
Iscritto il: 01 gen 1970, 01:00

Messaggio da dimpim » 28 feb 2005, 18:49

Ho iniziato da poco analisi, quindi naturalmente mi manca il 99% delle conoscenze in materia... comunque mi serviva solamente la dimostrazione di Cantor, il resto delle informazioni posso cercarmele pure da solo, senza togliere tempo a voi (perché so bene che è prezioso :wink: ). Grazie a tutti! (e non preoccupatevi: se ho dei dubbi non esiterò a chiedere :D ).

Avatar utente
pazqo
Messaggi: 155
Iscritto il: 01 gen 1970, 01:00
Località: san giorgio di nogaro
Contatta:

Messaggio da pazqo » 28 feb 2005, 19:48

il fatto è che per comprendere la dimostrazione di Cantor, devi avere alcune nozioni...
l'idea di base è la seguente.
1° passo:
$ \mathbb{R} $ e $ [0,1) $ sono omeomorfi: i.e. esiste una funzione continua con inversa continua tra $ \mathbb{R} $ e $ [0,1) $. Quindi ogni numero reale può essere rappresentato come un numero della forma $ 0,a_{1}a_{2}a_{3}\ldots $, con $ a_{i}\in{0,1,2,3,4,5,6,7,8,9} $ in modo pressoché unico (sarebbe da sistemare il caso in cui si ha il 9 periodico, come diceva MindFlyer...)
2° passo: Per assurdo: se $ \mathbb{R} $ fosse numerabile, allora potremmo sistemare tutti i numeri nel modo seguente:
$ 0,a_{11}a_{12}a_{13}\ldots a_{1n}\ldots\\ 0,a_{21}a_{22}a_{23}\ldots a_{2n}\ldots\\ 0,a_{31}a_{32}a_{33}\ldots a_{3n}\ldots\\ \vdots\\ 0,a_{m1}a_{m2}a_{m3}\ldots a_{mn}\ldots\\ \vdots\\ $

3° passo: Se questi fossero tutti i numeri reali, allora non potrei aggiungerne nessuno. Ma vediamo che questo è assurdo: Sia $ b_{ii} \neq a_{ii} $, ad esempio $ b_{ii} = 1 $ se $ a_{ii} $ è pari oppure $ b_{ii}=0 $ se $ a_{ii} $ è dispari.
Allora $ 0,b_{11}b_{22}b_{33} $ differisce da ciascuno dei numeri indicati sopra e appartiene all'insieme. Quindi prima non li avevamo elencati tutti, come da ipotesi. Assurdo.

Ci son molte cose da sistemare, eh! Ma l'idea, sostanzialmente, è questa
Stefano 'Pazqo' Pascolutti

A good mathematical joke is better, and better mathematics, than a dozen of mediocre papers -John Edensor LITTLEWOOD-

Use [tex]\LaTeX[/tex] in your math messages!

www.pazqo.altervista.org

MindFlyer

Messaggio da MindFlyer » 28 feb 2005, 21:34

Ho solo 2 cose da dire:
1) non c'è bisogno di tirare in ballo l'omeomorfismo! Basta una bigezione (che poi è la definizione di equipotenza tra insiemi). Anche se in realtà torna comoda una bigezione continua, per il semplice fatto che la si riesce a scrivere meglio, a priori questa cosa non è necessaria.
2) Per sistemare la storia del 9 periodico, basta dire che non si accettano le scritture decimali terminanti con infiniti 9. Così ogni numero in $ [0,1) $ ha un'unica espressione decimale, ed inoltre il numero che si ottiene dopo la trasformazione di pazqo è diverso da tutti gli altri, e non termina con tutti 9. Quindi prova effettivamente l'assurdo.

Avatar utente
pazqo
Messaggi: 155
Iscritto il: 01 gen 1970, 01:00
Località: san giorgio di nogaro
Contatta:

Messaggio da pazqo » 28 feb 2005, 22:15

in effetti la continuità non l'ho usata... :-)
In effetti, spesso mi son messo a pensare a cosa sia $ S_{[0,1]} $, il gruppo delle permutazioni dell'insieme $ [0,1] $. Sarebbero tutte le funzioni biettive da $ [0,1] $ in sè. Che cardinalità ha? $ 2^{\aleph_1} $?
Stefano 'Pazqo' Pascolutti

A good mathematical joke is better, and better mathematics, than a dozen of mediocre papers -John Edensor LITTLEWOOD-

Use [tex]\LaTeX[/tex] in your math messages!

www.pazqo.altervista.org

MindFlyer

Messaggio da MindFlyer » 28 feb 2005, 23:17

pazqo ha scritto:spesso mi son messo a pensare a cosa sia $ S_{[0,1]} $, il gruppo delle permutazioni dell'insieme $ [0,1] $. Sarebbero tutte le funzioni biettive da $ [0,1] $ in sè. Che cardinalità ha? $ 2^{\aleph_1} $?
Esatto, e lo puoi dimostrare in una quantità di modi.
Ad esempio, puoi usare il teorema di Cantor-Bernstein per far vedere che l'insieme di quelle funzioni ha la cardinalità di $ \mathcal P(\mathbb R) $.
Anzitutto considera le bigezioni che prendono $ x\in [0,1] $ e lo scambiano con $ 1-x $, o lo lasciano fermo. Queste hanno la cardinalità di $ \mathcal P\left(\left[0,\frac 1 2\right)\right) $, che è anche la cardinalità di $ \mathcal P(\mathbb R) $. E con questo hai dimostrato che la cardinalità delle tue funzioni è almeno $ 2^{\aleph_1} $.
D'altra parte, considerando che tali funzioni sono un sottoinsieme di $ \mathbb R^2 $, e che funzioni diverse hanno grafici diversi, hai automaticamente anche l'altra freccia, perché $ \# \mathcal P(\mathbb R^2)=\# \mathcal P(\mathbb R) $. E così hai dimostrato che la loro cardinalità è $ 2^{\aleph_1} $.

Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Messaggio da psion_metacreativo » 01 mar 2005, 01:31

Come esercizio non troppo difficile per entrare più nel merito della questione, consiglio a dimpim di dimostrare la seguente proposizione:

Denotiamo con $ \left|A\right| $ la cardinalità dell'insieme A e con $ \left|P(A)\right| $ la cardinalità dell'insieme delle parti di A. Dimostrare: se $ \left|A\right|=\left|B\right|\:\Rightarrow \:\left|P(A)\right|=\left|P(B)\right| $

Se riesci a dimostrare quanto sopra richiesto sei a posto. Infatti sfruttando $ \left|N\right|=\left|Q\right|=\aleph_{0}\:\Rightarrow\:\left|P(N)\right|=\left|P(Q)\right| $. Allora occorre trovare una funzione iniettiva da $ R\longmapsto\:P(Q) $ e una funzione iniettiva da $ P(N)\longmapsto\:R $ e concludere per il teorema di Cantor-Bernstein che $ \left|P(N)\right|=\left|R\right| $
Dunque esibiamo le due funzioni:
$ \varphi:\ $R\:\longmapsto\:P(Q)$\hspace{1cm}r\ \longmapsto\:\left\{q\in Q | q<r \right\} $
$ \psi:\ $P(N)\:\longmapsto\:R$\hspace{1cm}\left(a_{n}|n\in N\right)\ \longmapsto\:$\sum_{n\in N} \frac{a_{n}}{10^{n}}$ $

Già che ci sei completa con la dovuta attenzione la prima uguaglianza che ho scritto (la numerabilità dei razionali fatto abbastanza noto e famosa la sua dimostrazione) e dimostra che queste due funzioni sono iniettive completando come si deve la precedente dimostrazione.


P.S.
Questo è il mio battesimo... Adoro questo nuovo forum, il tex è semplicemente essenziale citate il mio messaggio per vedere come sarebbe stato scritto sul vecchio forum... I love MarxVilly...

Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Messaggio da psion_metacreativo » 01 mar 2005, 17:25

psion_metacreativo ha scritto:Come esercizio non troppo difficile per entrare più nel merito della questione, consiglio a dimpim di dimostrare la seguente proposizione:

Denotiamo con $ \left|A\right| $ la cardinalità dell'insieme A e con $ \left|P(A)\right| $ la cardinalità dell'insieme delle parti di A. Dimostrare: se $ \left|A\right|=\left|B\right|\:\Rightarrow \:\left|P(A)\right|=\left|P(B)\right| $

Se riesci a dimostrare quanto sopra richiesto sei a posto.
Credo che tu non possa dimostrare una cosa del genere perche` dovrebbe essere equivalente all'ipotesi del continuo e pertanto indimostrabile, scusami. Comunque tutto cio` che ho scritto resta vero occorre solo dimostrare che
psion_metacreativo ha scritto: $ \left|P(N)\right|=\left|P(Q)\right| $.
una cosa comunque fattibile.

MindFlyer

Messaggio da MindFlyer » 01 mar 2005, 18:05

Psion, il teorema secondo cui #A=#B implica #P(A)=#P(B) è banalmente dimostrabile, non è equivalente all'ipotesi del continuo! Prova...

Avatar utente
pazqo
Messaggi: 155
Iscritto il: 01 gen 1970, 01:00
Località: san giorgio di nogaro
Contatta:

Messaggio da pazqo » 01 mar 2005, 21:39

già, visto che $ |\mathcal{P}(A)| $ dipende solo da $ |A| $
Stefano 'Pazqo' Pascolutti

A good mathematical joke is better, and better mathematics, than a dozen of mediocre papers -John Edensor LITTLEWOOD-

Use [tex]\LaTeX[/tex] in your math messages!

www.pazqo.altervista.org

MindFlyer

Messaggio da MindFlyer » 25 set 2006, 23:08

[Ho spezzato il resto del thread. La nuova discussione si trova QUI.]

Rispondi