Dimostrazione con Lemma dei cassetti
Altro dubbio prima della prova in itinere... Allora l'esercizio richiede questo:
usando il lemma dei cassetti, si dimostri il seguente risultato:
Lemma. Siano X,Y due insiemi finiti con lo stesso numero di elementi e f: X $ rarr $ Y una funzione. Allora f è iniettiva se e solo se è suriettiva.
Per comodità vi riporto anche il lemma dei cassetti:
Lemma. Siano X,Y due insiemi finiti tali che |X|>|Y|. Sia f: X $ rarr $ Y una funzione. Allora f non è iniettiva.
Dunque, non so se c'è sotto qualcosa di più sottile ma io l'ho pensata così:
per il lemma dei cassetti ho che se |X|>|Y| f non può essere iniettiva (pertanto è suriettiva). Se invece ho |X|<|Y| f è iniettiva. Per cui se voglio che sia contemporaneamente iniettiva e suriettiva (biiettiva) la cardinalità di X deve essere per forza uguale a quella di Y (|X|=|Y|) altrimenti può essere solo una o l'altra...
Il punto è che non credo che la dimostrazione sia così ovvia, per cui se non ho dimostrato niente datemi una mano per favore!
usando il lemma dei cassetti, si dimostri il seguente risultato:
Lemma. Siano X,Y due insiemi finiti con lo stesso numero di elementi e f: X $ rarr $ Y una funzione. Allora f è iniettiva se e solo se è suriettiva.
Per comodità vi riporto anche il lemma dei cassetti:
Lemma. Siano X,Y due insiemi finiti tali che |X|>|Y|. Sia f: X $ rarr $ Y una funzione. Allora f non è iniettiva.
Dunque, non so se c'è sotto qualcosa di più sottile ma io l'ho pensata così:
per il lemma dei cassetti ho che se |X|>|Y| f non può essere iniettiva (pertanto è suriettiva). Se invece ho |X|<|Y| f è iniettiva. Per cui se voglio che sia contemporaneamente iniettiva e suriettiva (biiettiva) la cardinalità di X deve essere per forza uguale a quella di Y (|X|=|Y|) altrimenti può essere solo una o l'altra...
Il punto è che non credo che la dimostrazione sia così ovvia, per cui se non ho dimostrato niente datemi una mano per favore!
Risposte
"~Rose":
Lemma. Siano X,Y due insiemi finiti con lo stesso numero di elementi e f: X $ rarr $ Y una funzione. Allora f è iniettiva se e solo se è suriettiva.
[...]
per il lemma dei cassetti ho che se |X|>|Y| f non può essere iniettiva (pertanto è suriettiva). Se invece ho |X|<|Y| f è iniettiva. Per cui se voglio che sia contemporaneamente iniettiva e suriettiva (biiettiva) la cardinalità di X deve essere per forza uguale a quella di Y (|X|=|Y|) altrimenti può essere solo una o l'altra...
Tu parti dall'ipotesi seguente: $|X| = |Y|$.
Perché distingui i casi in cui $|X| > |Y|$ e viceversa?
"~Rose":
per il lemma dei cassetti ho che se |X|>|Y| f non può essere iniettiva (pertanto è suriettiva).
Anche questo non mi convince.
Prendi in esame la seguente situazione: $X = { 1, 2 , 3 }$ e $Y = { a , b }$ e prendi la funzione $f : X -> Y $ così definita:
$f(1) = f(2) = f(3) = a$
Questa non è iniettiva e nemmeno suriettiva.
Effettivamente a questo non avevo pensato.... Allora forse ho capito:
Se |X|=|Y|, abbiamo supposto che se è suriettiva allora è anche iniettiva e la cosa è vera perchè la $f : X -> Y $ esaurisce tutto lo spazio d'arrivo con immagini tutte differenti, e vale anche il viceversa (se non ho capito male).
Per esempio:
$X = { 1, 2 , 3 }$ e $Y = { a , b , c}$
f(1)=a
f(2)=c
f(3)=b
Ogni elemento di X è associato ad un diverso elemento di Y quindi ho una funzione iniettiva, ed è anche suriettiva perchè esaurisce lo spazio d'arrivo... E così il viceversa.... In teoria ho capito, mi date una mano a scriverlo in un linguaggio "più da dimostrazione"? (se così si può chiamare
)
Se |X|=|Y|, abbiamo supposto che se è suriettiva allora è anche iniettiva e la cosa è vera perchè la $f : X -> Y $ esaurisce tutto lo spazio d'arrivo con immagini tutte differenti, e vale anche il viceversa (se non ho capito male).
Per esempio:
$X = { 1, 2 , 3 }$ e $Y = { a , b , c}$
f(1)=a
f(2)=c
f(3)=b
Ogni elemento di X è associato ad un diverso elemento di Y quindi ho una funzione iniettiva, ed è anche suriettiva perchè esaurisce lo spazio d'arrivo... E così il viceversa.... In teoria ho capito, mi date una mano a scriverlo in un linguaggio "più da dimostrazione"? (se così si può chiamare
)
Dimostrazione:
1) Se supponiamo che $f$ sia suriettiva deve essere una biezione perché se non lo fosse esisterebbero almeno due elementi di $X$ che finiscono nello stesso trasformato in $Y$. Dunque non potrei più far corrispondere ad ogni elemento di $X$ un ben determinato elemento di $Y$ avendo $X$ e $Y$ la medesima cardinalità.
2) Se supponiamo viceversa che $f$ sia iniettiva, deve essere anche suriettiva; se non lo fosse esisterebbe un elemento $y_0 in Y$ che non è immagine di alcun elemento di $X$. Allora potrei restringere il codominio considerando l'insieme $Y - {y_0}$. Il lemma dei cassetti applicato alla funzione $f^* : X -> Y-{y_0}$ conclude l'assurdo.
Linguaggio più formale!
1) Se supponiamo che $f$ sia suriettiva deve essere una biezione perché se non lo fosse esisterebbero almeno due elementi di $X$ che finiscono nello stesso trasformato in $Y$. Dunque non potrei più far corrispondere ad ogni elemento di $X$ un ben determinato elemento di $Y$ avendo $X$ e $Y$ la medesima cardinalità.
2) Se supponiamo viceversa che $f$ sia iniettiva, deve essere anche suriettiva; se non lo fosse esisterebbe un elemento $y_0 in Y$ che non è immagine di alcun elemento di $X$. Allora potrei restringere il codominio considerando l'insieme $Y - {y_0}$. Il lemma dei cassetti applicato alla funzione $f^* : X -> Y-{y_0}$ conclude l'assurdo.
in un linguaggio "più da dimostrazione"? (se così si può chiamare
Linguaggio più formale!
Ecco, non mi veniva il termine..... Grazie di tutto, son contenta che ci sono arrivata con la mia testa
Figurati...
Buongiorno, riprendo questa discussione perché vorrei capire se la dimostrazione che posterò possa definirsi valida.
Partiamo dal fatto che il testo su cui sto studiando enuncia il lemma dei cassetti in questo modo:
Siano A e B insiemi finiti con lo stesso numero di elementi ( $ | A| =| B| $ ). Sia $ f:Ararr B $ una mappa. Dimostrare che:
1) se f è iniettiva, allora è anche suriettiva;
2) se f è suriettiva, allora è anche iniettiva.
La dimostrazione che segue sul testo è sintetica e di difficile comprensione; ho pensato di elaborarne una personale, ma ho il dubbio che non sia "universale", cioè che non valga sempre.
Dimostrazione parte 1
Per la definizione di funzione iniettiva, ogni elemento di A ha un solo elemento corrispondente (immagine) in B (e il loro legame è la funzione f). Inoltre, presi due elementi qualsiasi di A diversi fra loro, le loro immagini in B saranno anche diverse fra loro, ovvero se per due elementi di A, si ha la stessa immagine in B, allora i due elementi coincidono:
$ AA a(i),a(j)in A:a(i)!= a(j)rArr f(a(i))!= f(a(j)) $
$ AA a(i),a(j)in A:f(a(i))=f(a(j))rArr a(i)=a(j) $
Ci chiediamo se f è suriettiva. Per $ | A| =| B| =1 $ è evidente. Ho un elemento per parte e tra questi sussiste un legame a causa del fatto che è iniettiva. Nello specifico la funzione è anche biiettiva e per la definizione di funzione biiettiva, f è anche suriettiva.
Se invece la cardinalità è >1, per la definizione di funzione suriettiva, ogni elemento di B è immagine di almeno un elemento di A:
$ AA bin B, EE ain A:f(a)=b $
Supponiamo però che non sia così, e che quindi esista un elemento di B che non sia immagine di alcun elemento di A:
$ AA ain A, EE bin B:b!= f(a) $
A questo punto, essendo la cardinalità degli insiemi la stessa, si hanno due situazioni:
1) esiste un elemento di A che non è associato ad alcun elemento di B:
$ EE ain A:f(a)!= b, AA bin B $
2) esistono almeno due elementi di A che sono associati ad un unico elemento b di B:
$ EE a(i),a(j)in A, a(i)!= a(j):f(a(i))=f(a(j))=b $
Ma in entrambe le situazioni, si è in contraddizione con la definizione di funzione iniettiva e quindi con l'ipotesi iniziale. Pertanto f è anche suriettiva.
Per non appesantire il messaggio dimostro la seconda parte nel post successivo.
Partiamo dal fatto che il testo su cui sto studiando enuncia il lemma dei cassetti in questo modo:
Siano A e B insiemi finiti con lo stesso numero di elementi ( $ | A| =| B| $ ). Sia $ f:Ararr B $ una mappa. Dimostrare che:
1) se f è iniettiva, allora è anche suriettiva;
2) se f è suriettiva, allora è anche iniettiva.
La dimostrazione che segue sul testo è sintetica e di difficile comprensione; ho pensato di elaborarne una personale, ma ho il dubbio che non sia "universale", cioè che non valga sempre.
Dimostrazione parte 1
Per la definizione di funzione iniettiva, ogni elemento di A ha un solo elemento corrispondente (immagine) in B (e il loro legame è la funzione f). Inoltre, presi due elementi qualsiasi di A diversi fra loro, le loro immagini in B saranno anche diverse fra loro, ovvero se per due elementi di A, si ha la stessa immagine in B, allora i due elementi coincidono:
$ AA a(i),a(j)in A:a(i)!= a(j)rArr f(a(i))!= f(a(j)) $
$ AA a(i),a(j)in A:f(a(i))=f(a(j))rArr a(i)=a(j) $
Ci chiediamo se f è suriettiva. Per $ | A| =| B| =1 $ è evidente. Ho un elemento per parte e tra questi sussiste un legame a causa del fatto che è iniettiva. Nello specifico la funzione è anche biiettiva e per la definizione di funzione biiettiva, f è anche suriettiva.
Se invece la cardinalità è >1, per la definizione di funzione suriettiva, ogni elemento di B è immagine di almeno un elemento di A:
$ AA bin B, EE ain A:f(a)=b $
Supponiamo però che non sia così, e che quindi esista un elemento di B che non sia immagine di alcun elemento di A:
$ AA ain A, EE bin B:b!= f(a) $
A questo punto, essendo la cardinalità degli insiemi la stessa, si hanno due situazioni:
1) esiste un elemento di A che non è associato ad alcun elemento di B:
$ EE ain A:f(a)!= b, AA bin B $
2) esistono almeno due elementi di A che sono associati ad un unico elemento b di B:
$ EE a(i),a(j)in A, a(i)!= a(j):f(a(i))=f(a(j))=b $
Ma in entrambe le situazioni, si è in contraddizione con la definizione di funzione iniettiva e quindi con l'ipotesi iniziale. Pertanto f è anche suriettiva.
Per non appesantire il messaggio dimostro la seconda parte nel post successivo.
Dimostrazione parte 2
Riprendiamo la definizione di funzione suriettiva:
$ AA bin B, EE ain A:f(a)=b $
Si può definire anche iniettiva? Se la cardinalità è 1, sì, per lo stesso motivo visto sopra.
Se invece la cardinalità è >1?
Se f fosse anche iniettiva si avrebbe:
$ AA a(i),a(j)in A:a(i)!= a(j), EE b(i),b(j)in B,b(i)!= b(j):f(a(i))=b(i),f(a(j))=b(j) $
Supponiamo che non sia così, cioè che:
$ AA a(i),a(j)in A:a(i)!= a(j), EE bin B:f(a(i))=f(a(j))=b $
questo non va in contrasto con la definizione di funzione suriettiva, ma dal momento che A e B contengono lo stesso numero di elementi, allora si avrebbe un elemento di B che non è associato ad alcun elemento di A e pertanto la funzione non sarebbe più suriettiva. Di conseguenza f è anche iniettiva.
Grazie per l'aiuto e chiedo scusa se ho commesso degli errori nello scrivere le formule.
Riprendiamo la definizione di funzione suriettiva:
$ AA bin B, EE ain A:f(a)=b $
Si può definire anche iniettiva? Se la cardinalità è 1, sì, per lo stesso motivo visto sopra.
Se invece la cardinalità è >1?
Se f fosse anche iniettiva si avrebbe:
$ AA a(i),a(j)in A:a(i)!= a(j), EE b(i),b(j)in B,b(i)!= b(j):f(a(i))=b(i),f(a(j))=b(j) $
Supponiamo che non sia così, cioè che:
$ AA a(i),a(j)in A:a(i)!= a(j), EE bin B:f(a(i))=f(a(j))=b $
questo non va in contrasto con la definizione di funzione suriettiva, ma dal momento che A e B contengono lo stesso numero di elementi, allora si avrebbe un elemento di B che non è associato ad alcun elemento di A e pertanto la funzione non sarebbe più suriettiva. Di conseguenza f è anche iniettiva.
Grazie per l'aiuto e chiedo scusa se ho commesso degli errori nello scrivere le formule.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo