La cardinalità

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

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

Messaggio da psion_metacreativo »

Aggiungo altra carne al fuoco in questo caldo pomeriggio:
<BR>
<BR>Sempre dal Courant-Robbins esercizio pag 130
<BR>
<BR>\"Se A contiene n elementi, con n intero positivo, dimostrare che B, l\'insieme delle parti di A, contiene 2^n elementi.
<BR>Se A è l\'insieme di tutti i numeri interi positivi, dimostrare che B è equivalente al continuo reale da 0 a 1.\"
publiosulpicio
Messaggi: 774
Iscritto il: 01 gen 1970, 01:00

Messaggio da publiosulpicio »

Ma sbaglio o la seconda richiesta è la famosa ipotesi del continuo?! In questo caso possiamo anche smettere di cercare di risolverla, poiché è stato dimostrato che essa è indedicibile. Si può comunque dimostrare che B contiene più elementi di A, anche se essi hanno un numero infinito di elementi.
publiosulpicio
Messaggi: 774
Iscritto il: 01 gen 1970, 01:00

Messaggio da publiosulpicio »

E infatti mi sbaglio, non è quella l\'ipotesi del continuo.
Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Messaggio da psion_metacreativo »

La seconda richiesta non è equivalente alla famosa ipotesi del continuo, in quanto Cantor ipotizzò che tutti i numeri cardinali formassero una successione che chiamò ת , e l\'ipotesi del continuo afferma che la cardinalità del numerabile è quella immediatamente precedente a quella del continuo, mentre la seconda richiesta del problema afferma che l\'insieme delle parti di Z+ ha la stessa cardinalità di R, non sta chiedendo di dimostrare che non c\'è nessuna cardinalità tra quella di Z+ e quella del suo insieme delle parti. Almeno così ho capito. Cmq la prima richiesta come si dimostra?
publiosulpicio
Messaggi: 774
Iscritto il: 01 gen 1970, 01:00

Messaggio da publiosulpicio »

No infatti, un piccolo (piccolo, insomma) lapsus.
<BR>La prima per induzione è davvero immediata infatti per un insieme di cardinalità 1 ci sono due sottonsiemi (quello vuoto e lui stesso) inoltre se in insieme di cardinalità n ha 2^n sottoinsiemi un insieme di cardinalità n+1 ne deve avere il doppio (tutti quelli di prima più tutti quelli di prima a cui è aggiunto il buovo elemento) da cui segue la tesi.
<BR>Anche il secondo è piuttosto immediato (faccio il figo ma fino a 10 min fa pensavo fosse irrisolvibile) infatti prendi tutti i possibili sotto insiemi e li scrivi così: il sotto insieme (12,15) lo scrivi 0,12015 dove ci metti uno 0 tra il 12 e il 15, se il sottoinsieme fosse (12,15,16) scriveresti 0,12015016. Questo è una corispondenza biunivoca, per dimostrarlo basta osservare che essa è invertibile, infatti se conosci il decimale puoi risalire all\'insieme di partenza, inoltre a ogni decimale corrisponde un qualche insieme di partenza. Esistendo una corrispondenza biunivoca fra i due insiemi essi hanno la stessa cardinalità.
<BR>Spero di non aver fatto errori
Avatar utente
Antimateria
Messaggi: 651
Iscritto il: 01 gen 1970, 01:00
Località: Vergate sul Membro

Messaggio da Antimateria »

Publio, credo che la tua costruzione abbia qualche problema. Infatti la funzione che hai creato non è iniettiva, perchè (1,2) e (102) vanno entrambi in 0,102; inoltre non è nemmeno surgettiva, perchè 0,1111... non appartiene all\'immagine.
<BR>
<BR>Suggerisco di fare così: anzichè considerare lo sviluppo decimale dei reali, consideriamo la loro scrittura in base 2. Ogni reale tra 0 e 1 può essere scritto in modo unico come una successione di 0 e 1. L\'unica ambiguità è 1, che può essere scritto sia come 1,0000... che come 0,1111...: noi scegliamo la seconda espressione. In questo modo abbiamo veramente una bigezione tra reali tra 0 e 1 e successioni di 0 e 1. Ora, ad una successione x di 0 e 1 associamo un sottoinsieme A di N in questo modo: l\'intero i appartiene ad A se e solo se la cifra i-esima di x è 1. Si verifica facilmente che questa è una bigezione tra i sottoinsiemi di N e le successioni di 0 e 1, quindi i 2 insiemi sono equipotenti. Dunque sono equipotenti anche le parti di N e i reali tra 0 e 1.[addsig]
publiosulpicio
Messaggi: 774
Iscritto il: 01 gen 1970, 01:00

Messaggio da publiosulpicio »

Doh.. non avevo pensato a (1,2) e (102)... che sveglio! bhè 0,11111... potrebbe essere il sottonsime contentente solo il numero 1111111....
publiosulpicio
Messaggi: 774
Iscritto il: 01 gen 1970, 01:00

Messaggio da publiosulpicio »

Potresti spiegare un po\' meglio come associ i sottoinsiemi alle successioni?
publiosulpicio
Messaggi: 774
Iscritto il: 01 gen 1970, 01:00

Messaggio da publiosulpicio »

Lacia stare, ho capito, mi sembra giusto anche a me.
Avatar utente
Antimateria
Messaggi: 651
Iscritto il: 01 gen 1970, 01:00
Località: Vergate sul Membro

Messaggio da Antimateria »

<!-- 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 2003-07-04 15:51, publiosulpicio wrote:
<BR>Doh.. non avevo pensato a (1,2) e (102)... che sveglio! bhè 0,11111... potrebbe essere il sottonsime contentente solo il numero 1111111....
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Piccolo dettaglio: 1111... non è un numero naturale. <IMG SRC="images/forum/icons/icon_wink.gif">
Fede_HistPop
Messaggi: 576
Iscritto il: 01 gen 1970, 01:00
Località: Tuenno, TN
Contatta:

Messaggio da Fede_HistPop »

<!-- 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 2003-07-04 15:57, publiosulpicio wrote:
<BR>[...] mi sembra giusto anche a me.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>A me, invece, pare assai errato! Rileggi...
Co-founder and leader of Historiae Populorum.
0 A.D. Historian, Game Designer and Scenario Designer; maker of 0 A.D.'s Learning Campaign
Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Messaggio da psion_metacreativo »

ok grazie 1000 a Publio e ad Anti x aver risolto la questione.
Mathema
Messaggi: 124
Iscritto il: 01 gen 1970, 01:00
Località: Torino

Messaggio da Mathema »

<!-- 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 2003-07-03 17:56, publiosulpicio wrote:
<BR>No infatti, un piccolo (piccolo, insomma) lapsus.
<BR>La prima per induzione è davvero immediata infatti per un insieme di cardinalità 1 ci sono due sottonsiemi (quello vuoto e lui stesso) inoltre se in insieme di cardinalità n ha 2^n sottoinsiemi un insieme di cardinalità n+1 ne deve avere il doppio (tutti quelli di prima più tutti quelli di prima a cui è aggiunto il buovo elemento) da cui segue la tesi.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Non mi sembra che questa dimostrazione sia corretta. Nel problema originale, infatti, posto A l\'insieme di cardinalità n, l\'insieme B non necessariamente deve avere cardinalità n+1, ma deve essere l\'insieme delle parti di A. Ciò significa che in B sono contenuti tutti gli elementi di A, tutti i sottoinsiemi di A contenenti 2 elementi, tutti i sottoinsiemi di A contenenti 3 elementi,...tutti i sottoinsiemi di A contenenti n-1 elementi, e il \"sottoinsieme\" A contenente gli n elementi di A, oltre all\'insieme vuoto. In generale, il numero di sottoinsiemi di A contenenti i elementi è dato da C(n,i), dove C è il coefficiente binomiale. Pertanto gli elementi di B saranno dati dalla formula
<BR>sum[k=0..n]C(n,i), ma il risultato di questa sommatoria è appunto 2^n.
Avatar utente
Antimateria
Messaggi: 651
Iscritto il: 01 gen 1970, 01:00
Località: Vergate sul Membro

Messaggio da Antimateria »

Mathema, leggi meglio quello che ha scritto publio. La sua dimostrazione è per induzione, e secondo me è perfetta, ed è anche la migliore di quelle che conosco.
Mathema
Messaggi: 124
Iscritto il: 01 gen 1970, 01:00
Località: Torino

Messaggio da Mathema »

Mi sono accorto or ora di aver scritto una cagata, e me ne scuso con Publio. Mannaggia, mi sono pure dovuto riconnettere perchè me ne sono accorto studiando altro per la maturità, visto che non sono ancora passato <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif">
Bloccato