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
chiarissimo thx 
Scusate l'ennesima intrusione ma in questi giorni sto vivendo sul forum
Mi è tornata in mente questa discussione che ho letto l'altro giorno e ci vedo un qualcosa di simile nel mio dubbio.
In particolare stavo studiando topologia in analisi I e leggevo che i chiusi sono i complementari degli aperti. A questo punto mi sono accorto che volevo dimostrarmi una cosa: che ogni chiuso proviene da qualche aperto come complementare e che ogni aperto proviene da un complementare di qualche chiuso. In sostanza mi pare ci sia una corrispondenza 1:1, quindi il concetto di equipotenza tra i due insiemi costituiti da tutti gli aperti e tutti i chiusi.
Qui viene la domanda. Io ho insiemi A tutti gli aperti e C tutti i chiusi e so che: preso un qualunque elemento di C ve ne sarà un A tale che C è complementare di quell'elemento di A.
D'altra parte so che ogni elemento di A ha la proprietà che c'è un elemento di B che ha cme complementare quello di A. Mi sembra di avere noto: Per ogni b di B esiste un a di A tale che (a,b) sta in qualche relazione che è "uno complementare dell'alro": e questa è suriettività. Stessa cosa a parti invertite ho una funzione suriettiva che collega B ad A. Sbaglio?
Mettiamo A e C siano ora finiti come insiemi, se io so che una funzione è suriettiva da A->C ed è suriettiva da C->A posso concludere che è biiettiva? Così da dimostrare che vi è equipotenza? Ho fatto i disegni con Venn come i bambini dell'asilo e mi sembra funzionare ma non ho idea su come procedere nel dimostrarlo.
Grazie.
Mi è tornata in mente questa discussione che ho letto l'altro giorno e ci vedo un qualcosa di simile nel mio dubbio.
In particolare stavo studiando topologia in analisi I e leggevo che i chiusi sono i complementari degli aperti. A questo punto mi sono accorto che volevo dimostrarmi una cosa: che ogni chiuso proviene da qualche aperto come complementare e che ogni aperto proviene da un complementare di qualche chiuso. In sostanza mi pare ci sia una corrispondenza 1:1, quindi il concetto di equipotenza tra i due insiemi costituiti da tutti gli aperti e tutti i chiusi.
Qui viene la domanda. Io ho insiemi A tutti gli aperti e C tutti i chiusi e so che: preso un qualunque elemento di C ve ne sarà un A tale che C è complementare di quell'elemento di A.
D'altra parte so che ogni elemento di A ha la proprietà che c'è un elemento di B che ha cme complementare quello di A. Mi sembra di avere noto: Per ogni b di B esiste un a di A tale che (a,b) sta in qualche relazione che è "uno complementare dell'alro": e questa è suriettività. Stessa cosa a parti invertite ho una funzione suriettiva che collega B ad A. Sbaglio?
Mettiamo A e C siano ora finiti come insiemi, se io so che una funzione è suriettiva da A->C ed è suriettiva da C->A posso concludere che è biiettiva? Così da dimostrare che vi è equipotenza? Ho fatto i disegni con Venn come i bambini dell'asilo e mi sembra funzionare ma non ho idea su come procedere nel dimostrarlo.
Grazie.
Sia $X$ uno spazio topologico (per esempio $RR^n$ standard), sia $O$ l'insieme degli aperti di $X$ e sia $C$ l'insieme dei chiusi di $X$. Sia $f:O to C$, $f(A)=X-A$ (dove $X-A$ è il complementare di $A$ in $X$) e sia $g:C to O$, $g(B)=X-B$ (il complementare di $B$ in $X$). Allora $f$ e $g$ sono ben definite (perché il complementare di un aperto è un chiuso e viceversa) e sono entrambe biiettive perché sono una l'inversa dell'altra, cioè $g(f(A))=A$ e $f(g(B))=B$ per ogni $A in O$, $B in C$. Infatti $X-(X-A)=A$ per ogni sottoinsieme $A$ di $X$. Se hai dubbi su questo per favore apri un nuovo argomento nella sezione di geometria, perché siamo parecchio fuori tema. Grazie.
No, non ho dubbi su questo, perché ho capito la tua spiegazione e non ho domande al riguardo. Il problema è che pensavo di sfruttare la suriettività più che il discorso che hai fatto e quindi non pensavo di essere fuori tema, mi sembrava un dubio simile.
Ma per tornare OT dato che ormai mi aveva incurisito quello a cui pensavo:
Mettiamo A e C siano finiti come insiemi, se io so che una funzione è suriettiva da A->C ed è suriettiva da C->A posso concludere che è biiettiva? Così da dimostrare che vi è equipotenza? Non ho idea su come procedere nel dimostrarlo. Però mi accorgo che se metto tre oggetti in A e 2 in B, e verifico che per ogni oggetto in B c'è né uno in A in relazione (chiamiamola complementare) e che se per ogi elemento di A verifico che c'è un elemento in B in relazione, allora proprio perché è una funzione da due elementi di B non posso andare a connetterne 3 di A perché andrebbe in disaccordo con il concetto di funzione B->A che dice: per ogni elemento di B esiste un unico elemento di A tale che (a,b) siano in relazione. Il tutto funziona solo quando sono con stessa cardinalità.
E nel caso infinito? Si può concludere qualcosa?
Ma per tornare OT dato che ormai mi aveva incurisito quello a cui pensavo:
Mettiamo A e C siano finiti come insiemi, se io so che una funzione è suriettiva da A->C ed è suriettiva da C->A posso concludere che è biiettiva? Così da dimostrare che vi è equipotenza? Non ho idea su come procedere nel dimostrarlo. Però mi accorgo che se metto tre oggetti in A e 2 in B, e verifico che per ogni oggetto in B c'è né uno in A in relazione (chiamiamola complementare) e che se per ogi elemento di A verifico che c'è un elemento in B in relazione, allora proprio perché è una funzione da due elementi di B non posso andare a connetterne 3 di A perché andrebbe in disaccordo con il concetto di funzione B->A che dice: per ogni elemento di B esiste un unico elemento di A tale che (a,b) siano in relazione. Il tutto funziona solo quando sono con stessa cardinalità.
E nel caso infinito? Si può concludere qualcosa?
"indenzenblao":Non ha senso questa frase. Se una funzione è del tipo $A to C$ allora $A$ è il suo dominio e $C$ è il suo codominio, non li puoi scambiare di posto.
una funzione è suriettiva da A->C ed è suriettiva da C->A
No, non intendevo quello, intendevo che per ipotesi so che esistono due funzioni suriettive nei due versi (vedi spoiler). Hai ragione che mi ero spiegato male e il quote è sbagliato.
forse con una immagine è più facile:
era queso che mi chiedevo
forse con una immagine è più facile:
era queso che mi chiedevo
Ah adesso ho capito. Sì è vero nel caso finito quando dominio e codominio hanno la stessa cardinalità, addirittura se hai due insiemi finiti $A$ e $B$ della stessa cardinalità allora ogni funzione suriettiva $A to B$ è in realtà biiettiva.
Nel caso infinito non è vero, per esempio scrivendo $NN={0,1,2,...}$ (numeri naturali) posso definire
$f:NN to NN$,
$f(x)=[x/2]$
dove $[r]$ indica la parte intera di $r$, cioè il più grande intero minore o uguale a $r$ (per esempio $[7/2]=3$). Questa è suriettiva ma non iniettiva (lo riesci a vedere?).
Nel caso infinito non è vero, per esempio scrivendo $NN={0,1,2,...}$ (numeri naturali) posso definire
$f:NN to NN$,
$f(x)=[x/2]$
dove $[r]$ indica la parte intera di $r$, cioè il più grande intero minore o uguale a $r$ (per esempio $[7/2]=3$). Questa è suriettiva ma non iniettiva (lo riesci a vedere?).
per l'infinito è vero, che scemo mica ci avrei mai pensato a questo bell'esempio!
Per quanto riguarda invece il caso finito, mi sembra che la questione si divida in due parti:
- se |A|=|B| allora posso trovare funzioni g:B->A e f:A->B suriettive.
- e poi se esistono tra due insiemi finiti A e B due funzioni g:B->A e f:A->B suriettive allora sono equipotenti.
Però non capisco bene dove mettere le mani per dimostrarlE formalmente e chiedo a te .
Per quanto riguarda invece il caso finito, mi sembra che la questione si divida in due parti:
- se |A|=|B| allora posso trovare funzioni g:B->A e f:A->B suriettive.
- e poi se esistono tra due insiemi finiti A e B due funzioni g:B->A e f:A->B suriettive allora sono equipotenti.
Però non capisco bene dove mettere le mani per dimostrarlE formalmente e chiedo a te
.Questa è suriettiva ma non iniettiva (lo riesci a vedere?).
"indenzenblao":Sì perché se scrivi $A={a_1,...,a_n}$, $B={b_1,...,b_n}$ con $|A|=|B|=n$ allora puoi definire la funzione $f:A to B$, $f(a_i)=b_i$ per $i=1,...,n$. Questa $f$ è biiettiva, cioè è iniettiva e suriettiva.
se |A|=|B| allora posso trovare funzioni g:B->A e f:A->B suriettive.
se esistono tra due insiemi finiti A e B due funzioni g:B->A e f:A->B suriettive allora sono equipotenti.Sì perché la suriettività di $g$ implica che $|B| ge |A|$ e la suriettività di $f$ implica che $|A| ge |B|$, quindi $|A|=|B|$.
Il tutto si basa sul fatto seguente: se $f:A to B$ è suriettiva allora $|A| ge |B|$. Nel caso finito, questo si può dimostrare così: scriviamo $A={a_1,...,a_n}$, $B={b_1,...,b_m}$ con $|A|=n$, $|B|=m$. Per ogni $b in B$ prendiamo $P(b)={a in A\ :\ f(a)=b}$ (la preimmagine di $b$ tramite $f$). Cioè $P(b)$ consiste degli elementi $a in A$ la cui immagine $f(a)$ è uguale a $b$. Siccome $f$ è suriettiva, $P(b)$ è non vuoto, cioè $|P(b)| ge 1$, per ogni $b in B$. D'altra parte $A$ è l'unione disgiunta dei $P(b_i)$ (perché ogni fissato $a in A$ appartiene a $P(f(a))$ e a nessun'altra preimmagine), e quindi
$n=|A|=|P(b_1)|+...+|P(b_m)| ge 1+...+1 = m$.
Abbiamo cioè che $n ge m$, quello che volevamo dimostrare.
mi sembra che se assumo $f(x_1)=f(x_2)$ (*) tali che $x_1=(2k)/2$ e $x_2=(2k+1)/2$, si ha l'uguaglianza (*) ma $x_1!=x_2$ quindi $f(x_1)=f(x_2)!=>x_1=x_2$ => niente iniettivitàGiusto ma la scelta è $x_1=2k$, $x_2=2k+1$.
Sì perché se scrivi $A={a_1,...,a_n}$, $B={b_1,...,b_n}$ con $|A|=|B|=n$ allora puoi definire la funzione $f:A to B$, $f(a_i)=b_i$ per $i=1,...,n$. Questa $f$ è biiettiva, cioè è iniettiva e suriettiva.Non ci avevo pensato che indicizzandoli con $i$ sarebbe stato facilissimo definire la funzione $f(a_i)=b_i$, che è biiettiva usando lo stesso i su ai e bi.
Il tutto si basa sul fatto seguente:non lo sapevo, grazie mille è chiarissimo!
Giusto ma la scelta è $x_1=2k$, $x_2=2k+1$.Eh si è un refuso, correggo subito.
grazie per le spiegazioni utilissime e molto complete
Non so se l'avete già detto perchè non ho letto tutti i messaggi con attenzione ma anche nel caso infinito se esistono funzioni suriettive in entrambi i versi tra due insiemi allora hanno la stessa cardinalità.
"garson":
1) per ogni a in A esiste unico [aggiungo: "corrispondente"] B [recte: $b$] in B e 2) per ogni b in B esiste unico a in A [aggiungo: "di cui $b$ è il corrispondente"]
Mi sembra che 1) sia la definizione di funzione da $A$ in $B$ (non necessariamente iniettiva, stando al solo punto 1)...) e 2) la definizione della sua biiettività.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo