Iniezioni
Propongo questo problema che mi sono posto a cui non sono riuscito a dare una risposta:
Siano $A$ e $B$ due insiemi e siano $f:A\to B$, $g:B\to A$ due applicaizoni iniettive. Esiste una corrispondenza biunivoca tra $A$ e $B$?
Siano $A$ e $B$ due insiemi e siano $f:A\to B$, $g:B\to A$ due applicaizoni iniettive. Esiste una corrispondenza biunivoca tra $A$ e $B$?
Risposte
Chiedo scusa ho detto in parte una sciocchezza madornale, comunque il lemma rimane verissimo e la mia terminologia corretta.
[quote]Beh scusate se $A \subset B \subset C$ e $ \exists f:A \leftrightarrow C$
allora si ha che $f: A \leftrightarrow B$ è banale, o no?
No, non è vero: $A=4NN$, $B=2NN$, $C=NN$; se $f:A\to C$ è la divisione per $4$ allora $f$ è una biiezione tra $A$ e $C$, ma $f(A)$ non è contenuto in $B$, quindi $f$ non può essere una biiezione tra $A$ e $B$.[/quote]
Giusto non è vero. Quello che avresti dovuto scrivere Maxos era che se se $A \subset B \subset C$ e $ \exists f:A \leftrightarrow C$ allora si ha che esiste $g: A \leftrightarrow B$, la qual cosa non è banale ed è da dimostrare.
"Maxos":
No guarda ficus, la terminologia che uso è corretta, la moltiplicazione per 2 è una iniezione di $NN$ in se stesso.
Ovviamente non è una biezione tra $NN$ e se stesso. Ma io non ho scritto nulla di simile.
Tu hai scritto che l'iniezione $g\circ f:A \leftrightarrow g\circ f(A)$ è biunivoca perchè manda un insieme in se stesso:
"Maxos":
oppure in generale più banalmente $A \leftrightarrow g\circ f(A) \leftrightarrow f\circ g(B) \leftrightarrow B$ dove la seconda corrispondenza biunivoca è data tramite f o tramite g che su tali restrizioni sono suriettive e iniettive per definizione e costruzione, mentre la prima e la terza sono banali, in quanto iniezioni di insiemi in se stessi.
invece è biunivoca perchè inietta un insieme nella sua immagine.
"Maxos":
Beh scusate se $A \subset B \subset C$ e $ \exists f:A \leftrightarrow C$
allora si ha che $f: A \leftrightarrow B$ è banale, o no?
No, non è vero: $A=4NN$, $B=2NN$, $C=NN$; se $f:A\to C$ è la divisione per $4$ allora $f$ è una biiezione tra $A$ e $C$, ma $f(A)$ non è contenuto in $B$, quindi $f$ non può essere una biiezione tra $A$ e $B$.
Ma dico, scusate....
f è biettiva in C e dunque è iniettiva in C quindi iniettiva in B, poi f è suriettiva in C, dunque è suriettiva in B, dato che B è un sottoinsieme di C, quindi santo dio, è banale e la mia dimostrazione regge perfettamente!
f è biettiva in C e dunque è iniettiva in C quindi iniettiva in B, poi f è suriettiva in C, dunque è suriettiva in B, dato che B è un sottoinsieme di C, quindi santo dio, è banale e la mia dimostrazione regge perfettamente!
Io dimostrerei il tutto nel seguente modo.
Sia $f:A\to B$ iniettiva e $g:B\to A$ iniettiva. E' chiaro che esiste una biettività $h:A\to g(f(A))$: basta porre $h=g\circ f$. Inoltre chiaramente $g(f(A))\sube g(B)$. Se troviamo una biettività $k$ fra $g(B)$ e $A$ abbiamo la tesi.
Definiamo $C=A-g(B)$. Definiamo inoltre per induzione $h^n(C)$: $h^1(C)=h(C)$ e $h^(n+1)(C)=h(h^n(C))$.
Sia $k:g(B)\to A$ la seguente funzione: $k(x)=h^(-1)(x)$ se esiste $n\in NN$ tale che $x\in h^n(C)$; in caso contrario, $k(x)=x$.
E' banale verificare che $k$ è iniettiva e suriettiva, dunque è una biettività. Poiché $g(B)$ è in biettività con $B$, abbiamo la tesi.
Sia $f:A\to B$ iniettiva e $g:B\to A$ iniettiva. E' chiaro che esiste una biettività $h:A\to g(f(A))$: basta porre $h=g\circ f$. Inoltre chiaramente $g(f(A))\sube g(B)$. Se troviamo una biettività $k$ fra $g(B)$ e $A$ abbiamo la tesi.
Definiamo $C=A-g(B)$. Definiamo inoltre per induzione $h^n(C)$: $h^1(C)=h(C)$ e $h^(n+1)(C)=h(h^n(C))$.
Sia $k:g(B)\to A$ la seguente funzione: $k(x)=h^(-1)(x)$ se esiste $n\in NN$ tale che $x\in h^n(C)$; in caso contrario, $k(x)=x$.
E' banale verificare che $k$ è iniettiva e suriettiva, dunque è una biettività. Poiché $g(B)$ è in biettività con $B$, abbiamo la tesi.
Beh scusate se $A \subset B \subset C$ e $ \exists f:A \leftrightarrow C$
allora si ha che $f: A \leftrightarrow B$ è banale, o no?
E' banale se assumiamo vero ciò che dobbiamo dimostrare..
No guarda ficus, la terminologia che uso è corretta, la moltiplicazione per 2 è una iniezione di $NN$ in se stesso.
Ovviamente non è una biezione tra $NN$ e se stesso. Ma io non ho scritto nulla di simile.
Beh scusate se $A \subset B \subset C$ e $ \exists f:A \leftrightarrow C$
allora si ha che $f: A \leftrightarrow B$ è banale, o no?
Ovviamente non è una biezione tra $NN$ e se stesso. Ma io non ho scritto nulla di simile.
Beh scusate se $A \subset B \subset C$ e $ \exists f:A \leftrightarrow C$
allora si ha che $f: A \leftrightarrow B$ è banale, o no?
"Maxos":
è vero invece che:
$A \leftrightarrow g\circ f(A)$ e $g(B) \leftrightarrow B$
ma allora siccome $g \circ f (A) \subset g(B) \subset A$ si chiude la catena di rel. biunivoche.
Non vedo cosa tu possa concludere con questa osservazione...
"Maxos":
La correzione non è rigorosamente necessaria, per esempio il doppio è una iniezione di $NN$ in se stesso.
No, invece, la correzione è necessaria, perchè una iniezione di un insieme in se non è in generale una biiezione, e il caso della moltiplicazione per 2 da $NN$ in $NN$ ne è un controesempio.
"Maxos":
Comunque riguardo all'ultima obiezione, sì, è falso, ho concluso troppo in fretta, è vero invece che:
$A \leftrightarrow g\circ f(A)$ e $g(B) \leftrightarrow B$
ma allora siccome $g \circ f (A) \subset g(B) \subset A$ si chiude la catena di rel. biunivoche.
cosa vuol dire che "si chiude la catena di rel. biunivoche"?
La correzione non è rigorosamente necessaria, per esempio il doppio è una iniezione di $NN$ in se stesso.
Comunque riguardo all'ultima obiezione, sì, è falso, ho concluso troppo in fretta, è vero invece che:
$A \leftrightarrow g\circ f(A)$ e $g(B) \leftrightarrow B$
ma allora siccome $g \circ f (A) \subset g(B) \subset A$ si chiude la catena di rel. biunivoche.
Comunque riguardo all'ultima obiezione, sì, è falso, ho concluso troppo in fretta, è vero invece che:
$A \leftrightarrow g\circ f(A)$ e $g(B) \leftrightarrow B$
ma allora siccome $g \circ f (A) \subset g(B) \subset A$ si chiude la catena di rel. biunivoche.
"ficus2002":
Del resto non è chiaro perchè la restrizione di $f$ a $g\circ f(A)\to f\circ g(B)$ sia suriettiva
Infatti è falso...
"Maxos":
Stai scherzando?
$NN$ non è in corrispondenza biunivoca con i numeri pari???
Questo lo dici tu, io ti ho soltanto fatto notare che non puoi dire che un'applicazione iniettiva da un insieme in se è suriettiva.
Quindi la tua frase
"Maxos":
oppure in generale più banalmente $A \leftrightarrow g\circ f(A) \leftrightarrow f\circ g(B) \leftrightarrow B$ dove la seconda corrispondenza biunivoca è data tramite f o tramite g che su tali restrizioni sono suriettive e iniettive per definizione e costruzione, mentre la prima e la terza sono banali, in quanto iniezioni di insiemi in se stessi.
va corretta
"ficus2002":
oppure in generale più banalmente $A \leftrightarrow g\circ f(A) \leftrightarrow f\circ g(B) \leftrightarrow B$ dove la seconda corrispondenza biunivoca è data tramite f o tramite g che su tali restrizioni sono suriettive e iniettive per definizione e costruzione, mentre la prima e la terza sono banali, in quanto iniezioni di insiemi nelle loro immagini.
Del resto non è chiaro perchè la restrizione di $f$ a $g\circ f(A)\to f\circ g(B)$ sia suriettiva; a priori puoi dire solo che $f(g\circ f (A))\subseteq f\circ g(B)$; come mostri l'altra inclusione?
Sì ma io stavo parlando di A e di un suo sottoinsieme.
Qualunque funzione è suriettiva nella sua immagine, per definizione, io sto parlando di rel. biunivoca tra $A$ e $g\circ f(A)$ che è l'immagine di A tramite la composizione di due funzioni iniettive, dunque iniettiva e suriettiva; non sto parlano di A in rel con se stesso tramite la composizione, non avrei certo bisogno di dimostrare questo fatto, vero?
Qualunque funzione è suriettiva nella sua immagine, per definizione, io sto parlando di rel. biunivoca tra $A$ e $g\circ f(A)$ che è l'immagine di A tramite la composizione di due funzioni iniettive, dunque iniettiva e suriettiva; non sto parlano di A in rel con se stesso tramite la composizione, non avrei certo bisogno di dimostrare questo fatto, vero?
"Maxos":
dunque, se gli insiemi sono finiti dimostriamo che f e g sono biiettive: A è in corrispondenza biunivoca con la sua immagine tramite f, ora supponiamo per assurdo che f non sia suriettiva, allora $B \backslash Im(f) != \0$ allora consideriamo $g\circ f$, essa è biettiva perché funzione iniettiva di un insieme finito in se stesso, cioè $Im(g)_[Im(f)]=A$ a questo punto, siccome g è iniettiva non saprei che farmene di quei poveri punti che stanno fuori dall'immagine di f, in quanto g non può mandarli in un punto di A che è già immagine di qualcun altro di $Im(f)$, ma i punti di A sono già tutti impegnati e dunque g non sarebbe definita, assurdo.
Ok, per il caso in cui gli insiemi sono finiti, vale l'implicazione e sono d'accordo. Per il caso generale, tu dici che
"Maxos":
oppure in generale più banalmente $A \leftrightarrow g\circ f(A) \leftrightarrow f\circ g(B) \leftrightarrow B$ dove la seconda corrispondenza biunivoca è data tramite f o tramite g che su tali restrizioni sono suriettive e iniettive per definizione e costruzione, mentre la prima e la terza sono banali, in quanto iniezioni di insiemi in se stessi.
ma, in generale, una iniezione di un insieme in sè può non essere biunivoca, ad esempio la moltiplicazione per 2 come applicazione da $NN$ a $NN$ è iniettiva ma non suriettiva...
dunque, se gli insiemi sono finiti dimostriamo che f e g sono biiettive: A è in corrispondenza biunivoca con la sua immagine tramite f, ora supponiamo per assurdo che f non sia suriettiva, allora $B \backslash Im(f) != \0$ allora consideriamo $g\circ f$, essa è biettiva perché funzione iniettiva di un insieme finito in se stesso, cioè $Im(g)_[Im(f)]=A$ a questo punto, siccome g è iniettiva non saprei che farmene di quei poveri punti che stanno fuori dall'immagine di f, in quanto g non può mandarli in un punto di A che è già immagine di qualcun altro di $Im(f)$, ma i punti di A sono già tutti impegnati e dunque g non sarebbe definita, assurdo.
oppure in generale più banalmente $A \leftrightarrow g\circ f(A) \leftrightarrow f\circ g(B) \leftrightarrow B$ dove la seconda corrispondenza biunivoca è data tramite f o tramite g che su tali restrizioni sono suriettive e iniettive per definizione e costruzione, mentre la prima e la terza sono banali, in quanto iniezioni di insiemi in se stessi.
oppure in generale più banalmente $A \leftrightarrow g\circ f(A) \leftrightarrow f\circ g(B) \leftrightarrow B$ dove la seconda corrispondenza biunivoca è data tramite f o tramite g che su tali restrizioni sono suriettive e iniettive per definizione e costruzione, mentre la prima e la terza sono banali, in quanto iniezioni di insiemi in se stessi.
"Maxos":
certo che sì
come lo dimostri?
certo che sì
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo