OliForum Matematico

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!

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...

Davide90 ha scritto:Forse ho capito male il testo....
L'insieme A contiene $ $ n $ elementi

Credo che Carlein intendesse che l'insieme A può essere infinito

[@Carlein: l'hai trovato da te o l'hai visto ad Algebra 1?]

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 ...]

Mi sembrava troppo semplice...
Ho letto la soluzione su Wikipedia, in effetti è fattibile... Do un hint:

Wikipedia ha scritto: L'argomento diagonale di Cantor mostra che l'insieme delle parti di un insieme (infinito o no) ha sempre cardinalità strettamente più alta di quella dell'inseme stesso.

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

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!

Beh, calma! Finora nessuno ha scritto esplicitamente nulla, nemmeno io! Il problema non è "rovinato", credo.

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 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.

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.

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". Perché contengono in pochi simboli rigorosi e chiari a tutti quello che dovrebbe essere detto in una frase.