Silly question: relazione tra insiemi equipotenti
Volevo dimostrare l'intuizione che se ho due insiemi A e B ali che
1) per ogni a in A esiste unico B in B e 2) per ogni b in B esiste unico a in A allora esiste una relazione biiettiva tra i due e quindi sono equipotenti.
Ho pensato di definire una relazione tra A e B in questo modo:
prendo $(a,b) in AxxB$ e dico che sono in relazione quando per l' a in A associo l'unico b di B, d'altra parte questa è una funzione dalla 1) stessa con cui definisco la funzione. Inoltre data l'unicità di b è iniettiva.
Per la suriettività devo mostrare che per ogni b in B esiste unico a in A tale che $f(a)=b$, e qui mi blocco stupidamente perché io potrei avere il b associato a un'altro elemento pur sempre in modo univoco.
E' facile vederlo con due elementi in un insieme A e due in B, io posso associare 1->a, 2->b con la prima proposizione, ma la seconda può dire che associo b->1 e a->2 e non avrei la funzione biunivoca.
Non so quindi come riuscire a sfruttare la 2) per creare la suriettività.
1) per ogni a in A esiste unico B in B e 2) per ogni b in B esiste unico a in A allora esiste una relazione biiettiva tra i due e quindi sono equipotenti.
Ho pensato di definire una relazione tra A e B in questo modo:
prendo $(a,b) in AxxB$ e dico che sono in relazione quando per l' a in A associo l'unico b di B, d'altra parte questa è una funzione dalla 1) stessa con cui definisco la funzione. Inoltre data l'unicità di b è iniettiva.
Per la suriettività devo mostrare che per ogni b in B esiste unico a in A tale che $f(a)=b$, e qui mi blocco stupidamente perché io potrei avere il b associato a un'altro elemento pur sempre in modo univoco.
E' facile vederlo con due elementi in un insieme A e due in B, io posso associare 1->a, 2->b con la prima proposizione, ma la seconda può dire che associo b->1 e a->2 e non avrei la funzione biunivoca.
Non so quindi come riuscire a sfruttare la 2) per creare la suriettività.
Risposte
La condizione 1) (che è equivalente alla condizione 2, quindi quest'ultima è ridondante), è praticamente la definizione di biiezione...
"Per ogni $a in A$ esiste un unico $b in B$" non vuol dire niente, o meglio è equivalente a dire "esiste un unico $b in B$" in altre parole $B$ ha un unico elemento, cioè $|B|=1$. Ovviamente non è questo che vuoi dire, quindi devi riformulare (1) e (2) in modo che esprimano correttamente quello che vuoi dire.
Sì, la condizione è anche mal formata, ma è anche chiaro che l@i vuole dire che ogni elemento in A ha un unico corrispondente in B.
Dato che mi pare siate tutti sulla stessa linea di risposta faccio un post unico: ho espresso male con i quantificatori e ho sbagliato, avete ragione.
L'idea era quella ipotizzata, vorrei dire che ogni elemento di A ha un unico corrispondente in B, insomma una sorta di iniettività, però senza scomodare ancora il concetto di funzione. Poi che ci fosse un viceversa, da quello poi volevo mostrare che in effetti potendosi costruire una funzione iniettiva e suriettiva era biiezione.
Siccome @ Martino mi hai fatto notare che ho cannato in pieno, perché nel mio scrittto come hai datto notare tutti gli elementi di A finiscono in un unico di B, chiedo: come potrei dire che
- ogni elemento di A ha un unico corrispondente in B
- ogni elemento di B ha un unico corrispondente in A
Detto cio, formalizzato per bene mi par di capire che la soluzione sia quella di ghira, che non conoscevo.
L'idea era quella ipotizzata, vorrei dire che ogni elemento di A ha un unico corrispondente in B, insomma una sorta di iniettività, però senza scomodare ancora il concetto di funzione. Poi che ci fosse un viceversa, da quello poi volevo mostrare che in effetti potendosi costruire una funzione iniettiva e suriettiva era biiezione.
Siccome @ Martino mi hai fatto notare che ho cannato in pieno, perché nel mio scrittto come hai datto notare tutti gli elementi di A finiscono in un unico di B, chiedo: come potrei dire che
- ogni elemento di A ha un unico corrispondente in B
- ogni elemento di B ha un unico corrispondente in A
Detto cio, formalizzato per bene mi par di capire che la soluzione sia quella di ghira, che non conoscevo.
PS:
"ghira":
https://it.m.wikipedia.org/wiki/Teorema_di_Cantor-Bernstein-Schr%C3%B6der
Non è così semplice come potrebbe sembrare.
CSB mi sembra diverso (fatta salva la precisazione di prima): qui OP sta assumendo che esista una relazione \(R\subseteq A\times B\) con la proprietà che per ogni \(a\in A\) l'insieme \(R_a := \{b\in B\mid (a,b)\in R\}\) sia un singoletto; quindi, $R$ è una relazione funzionale, e biiettiva. Per contro, $R$ è iniettiva se \(R_a\) ha al più un elemento.
"garson":Questo continua ad essere impreciso, non si capisce cosa vuoi dire.
Siccome @ Martino mi hai fatto notare che ho cannato in pieno, perché nel mio scrittto come hai datto notare tutti gli elementi di A finiscono in un unico di B, chiedo: come potrei dire che
- ogni elemento di A ha un unico corrispondente in B
- ogni elemento di B ha un unico corrispondente in A
Se quello che vuoi dire è che esiste una funzione iniettiva $A to B$ (primo punto) e che esiste una funzione iniettiva $B to A$ (secondo punto) allora la risposta te l'ha data ghira.
Se non è questo quello che vuoi dire, allora lo devi spiegare meglio perché non si capisce.
ok, la mia idea era imprecisa perché partivo da una intuizione grafica, cioè avevo l'idea di collegare uno a uno dei pallini da A a B, solo che intuitivamente avevo inenzione di farlo senza che fosse una vera e propria funzione inizialmente, quindi dire solo ad un elemento di A ci aggancio uno e uno solo di B, poi passo a un secondo elemento di A e ne aggancio un secondo uno e uno solo di B ecc ecc.
Ma forse l'errore è qui, nel senso che ogni volta che si cerca di collegare un elemento di A a B in modo "coda-punta" in modo unico tra primo e secondo elemento di una freccia automaticamente sto definendo una funzione per di più iniettiva?[nota]quindi l'idea era collegae che so: "la penna" a sopra "il tavolo", la "matita" sopra la "sedia"[/nota]
Quello che volevo capire era appunto se potessi slegare questo concetto di "collegamento" tra oggetti da quello di funzione e poi dire che nonostante questo si potesse comunque costruire tra A e B una funzione biiettiva e quindi che ci fosse una equipotenza nel numero di oggetti dei due insiemi.
Barbaramente detto avevo questa idea ma l'ho formalizzata malissimo.
Ma forse l'errore è qui, nel senso che ogni volta che si cerca di collegare un elemento di A a B in modo "coda-punta" in modo unico tra primo e secondo elemento di una freccia automaticamente sto definendo una funzione per di più iniettiva?[nota]quindi l'idea era collegae che so: "la penna" a sopra "il tavolo", la "matita" sopra la "sedia"[/nota]
Quello che volevo capire era appunto se potessi slegare questo concetto di "collegamento" tra oggetti da quello di funzione e poi dire che nonostante questo si potesse comunque costruire tra A e B una funzione biiettiva e quindi che ci fosse una equipotenza nel numero di oggetti dei due insiemi.
Barbaramente detto avevo questa idea ma l'ho formalizzata malissimo.
Non importa se sleghi il concetto di collegamento da quello di funzione. E' come se io decidessi di smettere di usare la parola "pane", se lo faccio il pane continua ad essere pane e per me è diventato solo più difficile di prima spiegarmi.
Se quello che fai corrisponde a considerare una funzione allora si può spiegare in termini di funzioni.
Il punto di usare la parola "funzione" non riguarda il significato di quanto dici, riguarda la convenienza, cioè se ti conviene o no spiegarti usando il concetto di funzione.
Sì, ti conviene. Spiegare quello che vuoi dire usando il concetto di funzione aiuta moltissimo perché (come hai notato dalla risposta di ghira) così facendo puoi consultare la letteratura in merito.
Ti confermo che quello che hai in mente è proprio la cosa seguente: "se esiste una funzione iniettiva $A to B$ ed esiste una funzione iniettiva $B to A$ allora esiste una funzione biiettiva $A to B$?" La risposta è sì ed è appunto il contenuto del teorema di Cantor-Schroder-Bernstein (per niente banale).
Se quello che fai corrisponde a considerare una funzione allora si può spiegare in termini di funzioni.
Il punto di usare la parola "funzione" non riguarda il significato di quanto dici, riguarda la convenienza, cioè se ti conviene o no spiegarti usando il concetto di funzione.
Sì, ti conviene. Spiegare quello che vuoi dire usando il concetto di funzione aiuta moltissimo perché (come hai notato dalla risposta di ghira) così facendo puoi consultare la letteratura in merito.
Ti confermo che quello che hai in mente è proprio la cosa seguente: "se esiste una funzione iniettiva $A to B$ ed esiste una funzione iniettiva $B to A$ allora esiste una funzione biiettiva $A to B$?" La risposta è sì ed è appunto il contenuto del teorema di Cantor-Schroder-Bernstein (per niente banale).
Se quello che fai corrisponde a considerare una funzione allora si può spiegare in termini di funzioni.Sì, credo proprio il mio errore fosse il fatto che inizialmente non mi ero accorto che di fatto, stavo definendo una funzione.
Quindi pensavo di poter dire per ogni a esiste b ecc ecc (che avevo sbagliato) e poi speravo di far discendere il concetto di fuzione da quello.
Invece il punto mi pare proprio essere che io avevo già in mente dal principio che fosse una funzione, quindi sarebbe stupdo cercare di bypassare quel conceto, perché quello è. l fatto è che non me ne ero accorto
Mi chiedevo ora, ma se invece di lavorare con insiemi infiniti lavorassi con finiti? non potrebbe essere più facile? sempre intuitivamente mi pare che con qualche "permutaizone" riesco a portarmi ad avere una biiezine fatta e finita.
Sempre col mio esempio, dicevo di avere:
1->a
2->b
e se anche avessi per la funzione iniettiva contraria:
a->2
b->1
allora componendo
1->a->2->1
2->b->1->2
quindi, introducendo lo scambio 2 in 1 e 1 in 2 mi ridurrei ad avere una identità che è biiettiva, ma essendo tutta questa composizione (identità) biiettiva mi pare di poter dedurre che (essendo composizione di funzioni biiettive => è biiettiva in ogni sua funzione): da cui, 1->a e 2->b iniziale è biiettiva.
Il punto però è che per definire quello che faccio "permutaizoni" devo sapere che sono biiezioni, quindi devo già sapere la cardinalità, quindi penso sia un idea destinata a fallire. O sbaglo?
Non pensavo che un concetto così stupido portasse a questo casino
Nel caso finito quello che dici è un esercizio, basato sui due fatti seguenti.
1. Se esiste una funzione iniettiva $A to B$ allora $|A| le |B|$.
2. Se $A$ e $B$ sono insiemi finiti della stessa cardinalità allora una funzione $A to B$ è iniettiva se e solo se è suriettiva, se e solo se è biiettiva. (In pratica questa è una formulazione del principio dei cassetti)
Ora se hai funzioni iniettive $A to B$ e $B to A$ con $A,B$ finiti allora per (1) abbiamo $|A| le |B|$ e $|B| leq |A|$ quindi $|A|=|B|$, ora per (2) qualsiasi funzione iniettiva $A to B$ è in realtà biiettiva.
1. Se esiste una funzione iniettiva $A to B$ allora $|A| le |B|$.
2. Se $A$ e $B$ sono insiemi finiti della stessa cardinalità allora una funzione $A to B$ è iniettiva se e solo se è suriettiva, se e solo se è biiettiva. (In pratica questa è una formulazione del principio dei cassetti)
Ora se hai funzioni iniettive $A to B$ e $B to A$ con $A,B$ finiti allora per (1) abbiamo $|A| le |B|$ e $|B| leq |A|$ quindi $|A|=|B|$, ora per (2) qualsiasi funzione iniettiva $A to B$ è in realtà biiettiva.
@martino: So che è una scemata perché quello che hai scritto è molto piu semplce. Ma solo per esercitamri con questi concetti volevo capire se quello che scrivo è sensato:
Se io arrivo al tuo punto in cui dimostro |A|=|B|, allora per una qualsiasi funzione f:A->B (con unica cosa nota che sia iniettiva) e data anche la funzione g:B->A, io posso comporre un numero finito di scambi su A che chiamo h,...,r tale che f∘g∘h∘...∘r=id_A, in particolare (h∘r)=j è una permutazione j e f∘g∘j=id.
In ogni caso, avendo ora f∘g∘j=id, ogni funzione componente la composizione è biiettiva => f è biiettiva.
Mi sembra funzionare, sbaglio?
Se io arrivo al tuo punto in cui dimostro |A|=|B|, allora per una qualsiasi funzione f:A->B (con unica cosa nota che sia iniettiva) e data anche la funzione g:B->A, io posso comporre un numero finito di scambi su A che chiamo h,...,r tale che f∘g∘h∘...∘r=id_A, in particolare (h∘r)=j è una permutazione j e f∘g∘j=id.
In ogni caso, avendo ora f∘g∘j=id, ogni funzione componente la composizione è biiettiva => f è biiettiva.
Mi sembra funzionare, sbaglio?
Non mi convince, come dimostri che esistono questi scambi?
Avrei detto per il seguente motivo: allora, f e g sono date di base e sappiamo che sono iniettive e fin qui non ci sono problemi. e con queste mostriamo |A|=|B|.
per quanto riguarda la parte delle permutazioni quindi j' io avrei detto che posso sempre trovare una permutazione identità A->A questo perché ogni permutazione j' si puo decomporre in cicli e a sua volta ogi ciclo in trasposizioni, ora dato che ogni trasposizione ha la sua inversa, se decompongo $j'$ in $j'=h∘r∘t∘y∘u$ trasposizioni, avrò la j=id applicando uno stesso numero di traspoziooni (che sono inverse di se stesse, quinsi è assicurato che esistono) a ritroso: $j=id=h∘r∘t∘y∘u∘u∘y∘t∘r∘h$.
Il punto è che non so come dimostrare che siano finite in numero e non che ne servano infinite per generare l'identità data una j' qualunque, mi pare sensato ma nn saprei come fare.
Ora $g:B->A$, quindi mi pare altresì sensato che $f∘g:A->A$ e $f∘g$ non fa altro che scambiare gli elementi di A, quindi è a sua volta una permutazione.
da questo $f∘g∘j' = Id$ e quindi concludevo che essendo id biiettiva lo era anche f.
Sposto qui l'editing precedente, che ho visto che nel frattempo hai risposto.
PS: in sostanza nel caso nfinito quello che perdo è che se ho una funzione iniettiva A->B non è detto che |A| sia minore (come intuitivamente viene da pensare) di |B|.
Ammetto che questa cosa mi stupisce, e non affferro pienamente il perché, si può capire inn qualche modo facile?
per quanto riguarda la parte delle permutazioni quindi j' io avrei detto che posso sempre trovare una permutazione identità A->A questo perché ogni permutazione j' si puo decomporre in cicli e a sua volta ogi ciclo in trasposizioni, ora dato che ogni trasposizione ha la sua inversa, se decompongo $j'$ in $j'=h∘r∘t∘y∘u$ trasposizioni, avrò la j=id applicando uno stesso numero di traspoziooni (che sono inverse di se stesse, quinsi è assicurato che esistono) a ritroso: $j=id=h∘r∘t∘y∘u∘u∘y∘t∘r∘h$.
Il punto è che non so come dimostrare che siano finite in numero e non che ne servano infinite per generare l'identità data una j' qualunque, mi pare sensato ma nn saprei come fare.
Ora $g:B->A$, quindi mi pare altresì sensato che $f∘g:A->A$ e $f∘g$ non fa altro che scambiare gli elementi di A, quindi è a sua volta una permutazione.
da questo $f∘g∘j' = Id$ e quindi concludevo che essendo id biiettiva lo era anche f.
Sposto qui l'editing precedente, che ho visto che nel frattempo hai risposto.
PS: in sostanza nel caso nfinito quello che perdo è che se ho una funzione iniettiva A->B non è detto che |A| sia minore (come intuitivamente viene da pensare) di |B|.
Ammetto che questa cosa mi stupisce, e non affferro pienamente il perché, si può capire inn qualche modo facile?
Ma quando dici che $f circ g$ è una permutazione (cioè è biiettiva) puoi già concludere che $f$ è biiettiva, non serve introdurre gli scambi. Il punto è: perché $f circ g$ è una permutazione?
Ah è vero, mi sono incasinato. dicevo essendo iniettiva da A ad A allora non fa altro che permutare gli oggetti nell'insieme essendo $|A|=|A|$, ma se affermo ciò questo implicitamente vuol già dire che la considero biiettiva. Non ci avevo pensato D:
Ti ringrazio.
Ma invece, per dimostrare che data una permutazione posso trovare un numero finito di scambi che composti ne danno l'identità come faccio? Il mio metodo funziona, però presuppone che io sappia che ogni permutazione è decomponibile in un numero finito, è ragionevole ma non mi viene in mente come dimostrarlo.
Ti ringrazio.
Ma invece, per dimostrare che data una permutazione posso trovare un numero finito di scambi che composti ne danno l'identità come faccio? Il mio metodo funziona, però presuppone che io sappia che ogni permutazione è decomponibile in un numero finito, è ragionevole ma non mi viene in mente come dimostrarlo.
Nel caso infinito se esiste $A to B$ iniettiva allora $|A| le |B|$, il problema è che quando si scrive "$|A| le |B|$" questo significa appunto che esiste una funzione iniettiva $f:A to B$ (cioè è una riformulazione dello stesso concetto), e se ne esiste anche una iniettiva $B to A$ questo non garantisce che $f$ sia biiettiva (invece lo garantirebbe se gli insiemi coinvolti fossero finiti).
La decomposizione di una permutazione come prodotto di scambi la trovi su qualsiasi libro di algebra. Comunque continuo a non capire a cosa ti serva la decomposizione in scambi.
La decomposizione di una permutazione come prodotto di scambi la trovi su qualsiasi libro di algebra. Comunque continuo a non capire a cosa ti serva la decomposizione in scambi.
mi sembra di capire che in sostanza il concetto di |A|≤|B| non esiste a priori e viene dato come definizione da A→B iniettiva. Inoltre quando ho le due ineittive come nel caso finito so che:
|A|≤|B| e |B|≤|A| => |A|=|B|.
Tuttavia al contrario del caso finito ciò non garatisce più che sia biiettiva (non capisco bene il perché perda questa possibilità, però penso sia qualcosa legato al fatto che non fuzniona più il principio della piccionaia?). Dovrò capire meglio
ho troppa ignoranza
Ti ringrazio perché purtroppo a ing. non c'è algebra e quindi non avevo mai visto nulla di sta roba, e l'avevo solo approcciato per curiosità, allora guarderò sui libri.
In ogni caso ho capito che non mi serve a nulla la decomposizione, ma prima mi ero confuso, mi spiego: io avevo pensato che essendo $f∘g$ iniettiva allora sapevo che per ogni a esisteva un b t.c f(a)=b (e quindi immaginavo ogni elemento di A uno colpito da una freccia che finiva in uno di B), tuttavia mi ero detto essendo il codominio della stessa dimensione di A ciò vuol dire che ogni oggetto di B "deriva" da uno di A.
A questo punto non avevo pensato che questo voleva già dire che era suriettiva, e quindi mi ero prodigato a cercare un modo per avere l'idendità componendo con $f∘g$ una serie di trasposizioni.
A questo punto dicevo furbescamente ho id => f è biiettiva.
Si beh bravo furbone, non ti eri accorto che già dall'inizio avevi asserito che $f∘g$ era biiettiva, perché dicendo che ogni elemento di B è "toccato da una freccia proveniente da un elemento di A" è automaticamente suriettiva, che assimeme al fatto che era iniettiva mi dava già subito la biiettività.
E' lo stesso errore di prima dove non ho chiamato pane il pane.
|A|≤|B| e |B|≤|A| => |A|=|B|.
Tuttavia al contrario del caso finito ciò non garatisce più che sia biiettiva (non capisco bene il perché perda questa possibilità, però penso sia qualcosa legato al fatto che non fuzniona più il principio della piccionaia?). Dovrò capire meglio
ho troppa ignoranzaTi ringrazio perché purtroppo a ing. non c'è algebra e quindi non avevo mai visto nulla di sta roba, e l'avevo solo approcciato per curiosità, allora guarderò sui libri.
In ogni caso ho capito che non mi serve a nulla la decomposizione, ma prima mi ero confuso, mi spiego: io avevo pensato che essendo $f∘g$ iniettiva allora sapevo che per ogni a esisteva un b t.c f(a)=b (e quindi immaginavo ogni elemento di A uno colpito da una freccia che finiva in uno di B), tuttavia mi ero detto essendo il codominio della stessa dimensione di A ciò vuol dire che ogni oggetto di B "deriva" da uno di A.
A questo punto non avevo pensato che questo voleva già dire che era suriettiva, e quindi mi ero prodigato a cercare un modo per avere l'idendità componendo con $f∘g$ una serie di trasposizioni.
A questo punto dicevo furbescamente ho id => f è biiettiva.
Si beh bravo furbone, non ti eri accorto che già dall'inizio avevi asserito che $f∘g$ era biiettiva, perché dicendo che ogni elemento di B è "toccato da una freccia proveniente da un elemento di A" è automaticamente suriettiva, che assimeme al fatto che era iniettiva mi dava già subito la biiettività.
E' lo stesso errore di prima dove non ho chiamato pane il pane.
"garson":Per esempio prendi $A=B=NN$, che hanno la stessa cardinalità essendo uguali. La funzione $f:A -> B$, $f(x)=2x$ è iniettiva ma non biiettiva. Nel caso finito questo non succede, se $X$ è finito ogni funzione iniettiva $X -> X$ è per forza biiettiva.
(non capisco bene il perché perda questa possibilità, però penso sia qualcosa legato al fatto che non fuzniona più il principio della piccionaia?). Dovrò capire meglio
Sul resto, il punto è che tutto si appoggia sul fatto che ho scritto sopra, cioè che se $X$, $Y$ sono finiti della stessa cardinalità allora ogni funzione iniettiva $f:X to Y$ è biiettiva. Lo puoi dimostrare per induzione su $n=|X|=|Y|$. Prendi $x in X$, $y=f(x) in Y$. Poi prendi $A=X-{x}$, $B=Y-{y}$ e $g:A to B$, $g(t)=f(t)$. Questa $g$ è ben definita (cioè $g(t) in B$ per ogni $t in A$) perché $f$ è iniettiva, inoltre $g$ è iniettiva (perché lo è $f$) e $|A|=|B|=n-1$ quindi per induzione $g$ è biiettiva e quindi lo è anche $f$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo