Dimostrare che non esiste alcuna funzione suriettiva da un generico insieme A a P(A): dove per P(A) intendiamo l'insieme delle parti di A.
Per chi non ce l'avesse presente:una funzione f da A a B si definisce suriettiva quando per ogni b di B esiste almeno un a di A tale che f(a)=b.
Questo è un esercizio che ho trovato sull Herstein, e l'ho trovato anche molto bello: da persone più dotte di me mi è stato detto essere un teorema molto famoso. Assicuro che esiste una soluzione che fa uso di cose essenzialmente elementari ed è secondo me davvero carina! Spero che i mod non lo considerino fuori luogo in questo forum: ammetto che magari non potrebbe essere un problema da olimpiadi però il tipo di idea a mio parere si...nel caso mi sbagli ovviamente cancellerete...
Buon lavoro
Ciao!
Le Parti sono più del Tutto
Le Parti sono più del Tutto
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
Forse ho capito male il testo.... 
L'insieme A contiene $ $ n $ elementi, invece $ \mathbb{P} (A) $ ne contiene $ $ 2^n $ . Poichè una funzione associa ad ogni elemento di A uno e un solo elemento di B, il codominio della funzione può avere al più n elementi. Ora, $ $ 2^n > n \quad \forall n \in \mathbb N $ (bisogna dimostrarlo o si può dare per buono?), perciò non può esistere una funzione suriettiva $ $ A \rightarrow \mathbb P (A) $ .
Può in generale, direi che non esista una funzione suriettiva da un insieme ad un altro di cardinalità maggiore del primo.
Correggetemi se ho scritto fesserie...
L'insieme A contiene $ $ n $ elementi, invece $ \mathbb{P} (A) $ ne contiene $ $ 2^n $ . Poichè una funzione associa ad ogni elemento di A uno e un solo elemento di B, il codominio della funzione può avere al più n elementi. Ora, $ $ 2^n > n \quad \forall n \in \mathbb N $ (bisogna dimostrarlo o si può dare per buono?), perciò non può esistere una funzione suriettiva $ $ A \rightarrow \mathbb P (A) $ .
Può in generale, direi che non esista una funzione suriettiva da un insieme ad un altro di cardinalità maggiore del primo.
Correggetemi se ho scritto fesserie...
Si ovviamente come dice Ale90 A è un generico insieme, quindi può essere anche infinito.
[@Ale90:l'ho trovato da me, lo scorsi tra gli esercizi dell'Herstein(a fine primo capitolo)...e ci ho passato su un pomeriggio: ma ne è valsa la pena
...]
[@Ale90:l'ho trovato da me, lo scorsi tra gli esercizi dell'Herstein(a fine primo capitolo)...e ci ho passato su un pomeriggio: ma ne è valsa la pena
...]Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
Scusa non mi è chiaro perchè dai un hint? ......in fondo sta qui solo da un giorno...e gli altri magari non lo hanno ancora letto...mah...
Poi non è nemmeno una cosa che hai pensato tu in parte...cioè non è un idea che ti è venuta in mente e vuoi proporre...ma è un copia e incolla...di nuovo:mah
......in fondo sta qui solo da un giorno...e gli altri magari non lo hanno ancora letto...mah...Poi non è nemmeno una cosa che hai pensato tu in parte...cioè non è un idea che ti è venuta in mente e vuoi proporre...ma è un copia e incolla...di nuovo:mah
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
Oh, è un classico... alla fine un modo è considerare questo (è un suggerimento... in effetti confesso che nemmeno io ci sono arrivato da solo nel corso dei miei studi, ma d'altra parte si tratta proprio di un trucchetto... 
)
)...
chiamalo trucchetto...ma arrivarci è pur sempre divertente...e io l'avevo messo qua proprio perchè qualcuno provasse ad arrivarci, e non perchè così quelli che lo conoscevano già, postavano la soluzione o quantomeno l'idea principale, non da loro trovata ma letta altrove, per il gusto di bruciarlo:beh che dire, grazie tante!
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
Scusa, forse sarebbe stato meglio non postarlo, comunque quello che ho suggerito io era la strada che ho pensato io e sulla quale ho provato a lavorare da solo; non sono riuscito a risolverlo, ho letto su wikipedia e ho postato quella semplice indicazione copiandola per essere sicuro di scriverla in modo corretto....
La soluzione è ancora tutta da fare; il suggerimento di ani-sama indica la soluzione, ma bisogna cliccare per vederlo, chi lo vuole risolvere può ancora farlo benissimo. Comunque la prox volta non scriverò suggerimenti subito....
La soluzione è ancora tutta da fare; il suggerimento di ani-sama indica la soluzione, ma bisogna cliccare per vederlo, chi lo vuole risolvere può ancora farlo benissimo. Comunque la prox volta non scriverò suggerimenti subito....
La dimostrazione che ho trovato è simile a quella per dimostrare che i numeri reali sono più dei razionali.
Supponiamo per assurdo che ci sia una funzione suriettiva dall'insieme $ A $ all'insieme $ P(A) $. Allora tutti gli elementi di $ P(A) $, ovvero tutti i sottoinsiemi di A, sono raggiunti dalla funzione. E invece ecco come costruire un sottoinsieme non raggiunto dalla funzione: per ogni elemento $ x $ di $ A $, si guarda se è contenuto nel sottoinsieme in cui è trasformato nella funzione, ovvero se $ x \in f(x) $. Se sì, allora non si mette $ x $ nel sottoinsieme che vogliamo formare, se no allora si mette $ x $ nel sottoinsieme di $ A $ che vogliamo formare. In altri termini: prendiamo il sottoinsieme di $ A $ che contiene tutti e soli gli elementi non contenuti nelle rispettive funzioni.
Allora nessun elemento $ x $ di $ A $ finisce in questo sottoinsieme, perché questo sottoinsieme differisce da tutti gli altri per almeno un elemento, proprio per come è stato creato.
Supponiamo per assurdo che ci sia una funzione suriettiva dall'insieme $ A $ all'insieme $ P(A) $. Allora tutti gli elementi di $ P(A) $, ovvero tutti i sottoinsiemi di A, sono raggiunti dalla funzione. E invece ecco come costruire un sottoinsieme non raggiunto dalla funzione: per ogni elemento $ x $ di $ A $, si guarda se è contenuto nel sottoinsieme in cui è trasformato nella funzione, ovvero se $ x \in f(x) $. Se sì, allora non si mette $ x $ nel sottoinsieme che vogliamo formare, se no allora si mette $ x $ nel sottoinsieme di $ A $ che vogliamo formare. In altri termini: prendiamo il sottoinsieme di $ A $ che contiene tutti e soli gli elementi non contenuti nelle rispettive funzioni.
Allora nessun elemento $ x $ di $ A $ finisce in questo sottoinsieme, perché questo sottoinsieme differisce da tutti gli altri per almeno un elemento, proprio per come è stato creato.
Sono il cuoco della nazionale!
L'idea è questa, sì. Ma forse puoi essere più sintetico e nello stesso tempo più preciso. Cioè, semplicemente: in matematica le formule sono sempre preferibili ai "racconti".Anér ha scritto:E invece ecco come costruire un sottoinsieme non raggiunto dalla funzione: per ogni elemento $ x $ di $ A $, si guarda se è contenuto nel sottoinsieme in cui è trasformato nella funzione, ovvero se $ x \in f(x) $. Se sì, allora non si mette $ x $ nel sottoinsieme che vogliamo formare, se no allora si mette $ x $ nel sottoinsieme di $ A $ che vogliamo formare. In altri termini: prendiamo il sottoinsieme di $ A $ che contiene tutti e soli gli elementi non contenuti nelle rispettive funzioni.
Allora nessun elemento $ x $ di $ A $ finisce in questo sottoinsieme, perché questo sottoinsieme differisce da tutti gli altri per almeno un elemento, proprio per come è stato creato.
Perché contengono in pochi simboli rigorosi e chiari a tutti quello che dovrebbe essere detto in una frase. 
...