Come si dimostra che R è equipotente a P(N)???
<BR>Se si tratta di una soluzione \"facile\" vi prego di non postarla completamente ma magari darmi qualche indizio...
<BR>Grazie ciao a tutti
Cardinalità
Moderatore: tutor
-
MindFlyer
-
MindFlyer
<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-10-09 18:40, HiTLeuLeR wrote:
<BR>Baaah... ci sta su tutti i libri di Analisi, Barozz, persino sul Pagani-Salsa! <IMG SRC="images/forum/icons/icon_confused.gif">
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Io non l\'ho mai vista, dev\'essere ben nascosta.
<BR>Ah, già, ma io non studio Analisi! <IMG SRC="images/forum/icons/icon_smile.gif">
<BR>On 2004-10-09 18:40, HiTLeuLeR wrote:
<BR>Baaah... ci sta su tutti i libri di Analisi, Barozz, persino sul Pagani-Salsa! <IMG SRC="images/forum/icons/icon_confused.gif">
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Io non l\'ho mai vista, dev\'essere ben nascosta.
<BR>Ah, già, ma io non studio Analisi! <IMG SRC="images/forum/icons/icon_smile.gif">
<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-10-09 23:12, MindFlyer wrote:
<BR>Io non l\'ho mai vista, dev\'essere ben nascosta.
<BR>Ah, già, ma io non studio Analisi! <IMG SRC="images/forum/icons/icon_smile.gif">
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Beh, figurati! E tu verresti a dirlo giusto a un tale che ha studiato da \"ingeniere\" fino all\'altro giorno? Ahuahuahu... <IMG SRC="images/forum/icons/icon_razz.gif">
<BR>
<BR>
<BR>\"Excusatio non petita...\" - saggezza antica
<BR>On 2004-10-09 23:12, MindFlyer wrote:
<BR>Io non l\'ho mai vista, dev\'essere ben nascosta.
<BR>Ah, già, ma io non studio Analisi! <IMG SRC="images/forum/icons/icon_smile.gif">
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Beh, figurati! E tu verresti a dirlo giusto a un tale che ha studiato da \"ingeniere\" fino all\'altro giorno? Ahuahuahu... <IMG SRC="images/forum/icons/icon_razz.gif">
<BR>
<BR>
<BR>\"Excusatio non petita...\" - saggezza antica
Secondo me non e\' proprio facillimo, se si fanno dimostrazioni che sfruttano la rappresentazione in base n bisogna tenere conto del fatto che, per esempio, 0,9999.... e 1 sono lo stesso numero (e questo fa fallire i tentativi piu\' \"ingenui\").
<BR>
<BR>Diventa invece semplice se usi il teorema di Cantor-Bernstein (l\'ho visto chiamato anche Schroeder-Bernstein), che recita:
<BR>Dati due insiemi A e B, se esistono una funzione iniettiva f da A a B e una funzione iniettiva (diversa!) g da B ad A, allora esiste anche una funzione biiettiva tra di essi (=hanno la stessa cardinalita\')
<BR>
<BR>Quindi devi solo trovare una funzione iniettiva da R a P(N) e una da P(N) a R...
<BR>
<BR>ciao,
<BR>--federico
<BR>
<BR>Diventa invece semplice se usi il teorema di Cantor-Bernstein (l\'ho visto chiamato anche Schroeder-Bernstein), che recita:
<BR>Dati due insiemi A e B, se esistono una funzione iniettiva f da A a B e una funzione iniettiva (diversa!) g da B ad A, allora esiste anche una funzione biiettiva tra di essi (=hanno la stessa cardinalita\')
<BR>
<BR>Quindi devi solo trovare una funzione iniettiva da R a P(N) e una da P(N) a R...
<BR>
<BR>ciao,
<BR>--federico
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
-
MindFlyer
<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-10-10 12:09, fph wrote:
<BR>Secondo me non e\' proprio facillimo, se si fanno dimostrazioni che sfruttano la rappresentazione in base n bisogna tenere conto del fatto che, per esempio, 0,9999.... e 1 sono lo stesso numero (e questo fa fallire i tentativi piu\' \"ingenui\").
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Ok, è l\'unica difficoltà, e si risolve dicendo che l\'insieme dei numeri che terminano con una stessa cifra ripetuta all\'infinito è numerabile.
<BR>Per Bernstein... beh, basarsi su quello mi pare un tantino sleale, visto che l\'enunciato non è così intuitivo come quello dell\'esistenza della rappresentazione in base 2.
<BR>
<BR>EDIT: stavo mispellando \"Bernstein\". <IMG SRC="images/forum/icons/icon_smile.gif"> <BR><BR>[ Questo Messaggio è stato Modificato da: MindFlyer il 10-10-2004 19:04 ]
<BR>On 2004-10-10 12:09, fph wrote:
<BR>Secondo me non e\' proprio facillimo, se si fanno dimostrazioni che sfruttano la rappresentazione in base n bisogna tenere conto del fatto che, per esempio, 0,9999.... e 1 sono lo stesso numero (e questo fa fallire i tentativi piu\' \"ingenui\").
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Ok, è l\'unica difficoltà, e si risolve dicendo che l\'insieme dei numeri che terminano con una stessa cifra ripetuta all\'infinito è numerabile.
<BR>Per Bernstein... beh, basarsi su quello mi pare un tantino sleale, visto che l\'enunciato non è così intuitivo come quello dell\'esistenza della rappresentazione in base 2.
<BR>
<BR>EDIT: stavo mispellando \"Bernstein\". <IMG SRC="images/forum/icons/icon_smile.gif"> <BR><BR>[ Questo Messaggio è stato Modificato da: MindFlyer il 10-10-2004 19:04 ]
-
MindFlyer
<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-10-10 12:09, fph wrote:
<BR>Quindi devi solo trovare una funzione iniettiva da R a P(N) e una da P(N) a R...
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Questa strada ti fa fare il doppio del lavoro, anche se alla fine forse dà una soluzione più pulita.
<BR>Funzione iniettiva da R a P(N): sia r un reale, costruiamo un sottoinsieme S di N. 0 appartiene a S se e solo se r>=0. Se r>=0, poniamo 1 in S se e solo se r>=1, e simmetricamente per 0>r. In generale, ci teniamo un intervallo e ogni volta lo dividiamo a metà se è limitato, oppure spostiamo l\'estremo di 1 verso l\'infinito, se è limitato solo da una parte. Quindi poniamo o non poniamo l\'i-esimo naturale in S a seconda se r sta a destra o a sinistra (primo premio Spiegazione Chiara 2004/2005).
<BR>Funzione iniettiva da P(N) a R: basta considerare come immagine l\'insieme di Cantor, e la funzione vien da sè...
<BR>On 2004-10-10 12:09, fph wrote:
<BR>Quindi devi solo trovare una funzione iniettiva da R a P(N) e una da P(N) a R...
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Questa strada ti fa fare il doppio del lavoro, anche se alla fine forse dà una soluzione più pulita.
<BR>Funzione iniettiva da R a P(N): sia r un reale, costruiamo un sottoinsieme S di N. 0 appartiene a S se e solo se r>=0. Se r>=0, poniamo 1 in S se e solo se r>=1, e simmetricamente per 0>r. In generale, ci teniamo un intervallo e ogni volta lo dividiamo a metà se è limitato, oppure spostiamo l\'estremo di 1 verso l\'infinito, se è limitato solo da una parte. Quindi poniamo o non poniamo l\'i-esimo naturale in S a seconda se r sta a destra o a sinistra (primo premio Spiegazione Chiara 2004/2005).
<BR>Funzione iniettiva da P(N) a R: basta considerare come immagine l\'insieme di Cantor, e la funzione vien da sè...
-
MindFlyer
Ciao. Visto che lo avete citato: chi sa la dimostrazione di Cantor-Bernstein? Io ne vidi una nel millennio scorso, durante il corso di Algebra IV, che calcolava i padri, i nonni e gli avi degli elementi degli insiemi. Era abbastanza pittoresca e, tutto sommato, \"elementare\".
<BR>
<BR>Ora non ricordo esattamente tutti i dettagli, ma l\'idea era di definire una relazione padre-figlio seguendo le frecce date da f(-) e g(-) (le due funzioni iniettive). Ossia, dire che y è figlio di x se f(x) = y e x è figlio di y se g(y) = x. Quindi di spartire i due insiemi supposti equipotenti (che chiamo X e Y) in tre: gli elementi con capostipite in X, quelli con capostipite in Y e quelli senza capostipite. Su ognuno si riusciva a definire <!-- BBCode Start --><I>in modo semplice</I><!-- BBCode End --> una nuova h(-) che fosse bigettiva.
<BR>
<BR>Have a nice day in filling the gaps...
<BR>
<BR>M.
<BR>
<BR>EDIT: corretta la notazione...
<BR>
<BR>
<BR>\"A worthy man, but his memory is like a lumber-room: thing wanted always buried.\"<BR><BR>[ Questo Messaggio è stato Modificato da: marco il 11-10-2004 08:49 ]
<BR>
<BR>Ora non ricordo esattamente tutti i dettagli, ma l\'idea era di definire una relazione padre-figlio seguendo le frecce date da f(-) e g(-) (le due funzioni iniettive). Ossia, dire che y è figlio di x se f(x) = y e x è figlio di y se g(y) = x. Quindi di spartire i due insiemi supposti equipotenti (che chiamo X e Y) in tre: gli elementi con capostipite in X, quelli con capostipite in Y e quelli senza capostipite. Su ognuno si riusciva a definire <!-- BBCode Start --><I>in modo semplice</I><!-- BBCode End --> una nuova h(-) che fosse bigettiva.
<BR>
<BR>Have a nice day in filling the gaps...
<BR>
<BR>M.
<BR>
<BR>EDIT: corretta la notazione...
<BR>
<BR>
<BR>\"A worthy man, but his memory is like a lumber-room: thing wanted always buried.\"<BR><BR>[ Questo Messaggio è stato Modificato da: marco il 11-10-2004 08:49 ]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
-
MindFlyer
-
MindFlyer
Ho trovato un\'altra dimostrazione di Cantor-Bernstein, ancora più semplice. Credo che la funzione che si costruisce sia la stessa della versione con padri e figli, ma questo è un modo molto più veloce di farla.
<BR>
<BR>Siano A e B i 2 insiemi e f e g le 2 funzioni iniettive. Formiano 2 successioni di insiemi {A<sub>n</sub>} e {B<sub>n</sub>} in modo che A<sub>0</sub>=A, B<sub>0</sub>=B, A<sub>n+1</sub>=g(B<sub>n</sub>) e B<sub>n+1</sub>=f(A<sub>n</sub>). Queste 2 successioni sono formate da insiemi incapsulati l\'uno nell\'altro.
<BR>Costruiamo la funzione h da A a B. Sugli insiemi della forma A<sub>2n</sub>\\A<sub>2n+1</sub> la poniamo uguale a f, così come nell\'intersezione di tutti gli A<sub>n</sub>. Sulla parte restante di A la poniamo uguale a g<sup>-1</sup>. E\' banale vedere che h è una bigezione.
<BR>
<BR>Siano A e B i 2 insiemi e f e g le 2 funzioni iniettive. Formiano 2 successioni di insiemi {A<sub>n</sub>} e {B<sub>n</sub>} in modo che A<sub>0</sub>=A, B<sub>0</sub>=B, A<sub>n+1</sub>=g(B<sub>n</sub>) e B<sub>n+1</sub>=f(A<sub>n</sub>). Queste 2 successioni sono formate da insiemi incapsulati l\'uno nell\'altro.
<BR>Costruiamo la funzione h da A a B. Sugli insiemi della forma A<sub>2n</sub>\\A<sub>2n+1</sub> la poniamo uguale a f, così come nell\'intersezione di tutti gli A<sub>n</sub>. Sulla parte restante di A la poniamo uguale a g<sup>-1</sup>. E\' banale vedere che h è una bigezione.
guarda te, l\'abbiamo fatto l\'altro giorno al corso interno <IMG SRC="images/forum/icons/icon_smile.gif">
<BR>
<BR>ambrosio l\'ha dimostrato basandosi su questa
<BR>
<BR>proposizione: se X può essere messo in corrispondenza biunivoca con un suo sottoinsieme V, allora può essere messo in corrispondenza biunivoca con ogni insime U tale che
<BR>
<BR>V C U C X
<BR>
<BR>(C si legge \"contenuto\")
<BR>
<BR>il teorema segue abbastanza facilmente da questa cosa, mentre è la dimostrazione della stessa a essere un po\' più artificiosa..
<BR>
<BR>beh, provateci, se volete (anche se in effetti non ha granchè di olimpico)
<BR>
<BR>ambrosio l\'ha dimostrato basandosi su questa
<BR>
<BR>proposizione: se X può essere messo in corrispondenza biunivoca con un suo sottoinsieme V, allora può essere messo in corrispondenza biunivoca con ogni insime U tale che
<BR>
<BR>V C U C X
<BR>
<BR>(C si legge \"contenuto\")
<BR>
<BR>il teorema segue abbastanza facilmente da questa cosa, mentre è la dimostrazione della stessa a essere un po\' più artificiosa..
<BR>
<BR>beh, provateci, se volete (anche se in effetti non ha granchè di olimpico)
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]