[Esercizio] insieme quoziente
Costruire tutti gli insiemi quoziente dell'insieme $3={1,2,3}$.
Intanto so che un insieme quoziente è dato dal l'insieme di tutte le classi di equivalenza definite in rapporto ad una specifica relazione di equivalenza, quindi sono partito da una relazione di equivalenza... si ma quale? Intanto una relazione è definita come un qualsiasi sottoinsieme del prodotto cartesiano
$3 times 3={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}$
ma quante relazioni di equivalenza posso definire? Mi rispondo dicendo "tutte quelle che sono Riflessive, Simmetriche e Transitive".
Bene, no anzi, male, perchè ne ho trovata solo una che è quella di appartenenza:
$in$, dove $aRb <=> (a,b) in R$, $AAa,b in 3$.
Infatti $R$ è simmetrica $(1,1) in R$, $(2,2) in R$ e $(3,3) in R$, è riflessiva $(1,2) in R$ e $(2,1) in R$, ed è transitiva (ometto la scrittura). Quindi posso allora definire le classi di equivalenza come $[a]={b|(a,b) in R}$, e quindi uno degli insieme quoziente $3/R={ [1];[2];[3] }$ (ho usato il punto e virgola come separatore degli elementi perchè non riesco a scrivere l'insieme in modo corretto...).
Sempre che questo sia tutto corretto, quanti altri insieme quozienti posso creare?
Intanto so che un insieme quoziente è dato dal l'insieme di tutte le classi di equivalenza definite in rapporto ad una specifica relazione di equivalenza, quindi sono partito da una relazione di equivalenza... si ma quale? Intanto una relazione è definita come un qualsiasi sottoinsieme del prodotto cartesiano
$3 times 3={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}$
ma quante relazioni di equivalenza posso definire? Mi rispondo dicendo "tutte quelle che sono Riflessive, Simmetriche e Transitive".
Bene, no anzi, male, perchè ne ho trovata solo una che è quella di appartenenza:
$in$, dove $aRb <=> (a,b) in R$, $AAa,b in 3$.
Infatti $R$ è simmetrica $(1,1) in R$, $(2,2) in R$ e $(3,3) in R$, è riflessiva $(1,2) in R$ e $(2,1) in R$, ed è transitiva (ometto la scrittura). Quindi posso allora definire le classi di equivalenza come $[a]={b|(a,b) in R}$, e quindi uno degli insieme quoziente $3/R={ [1];[2];[3] }$ (ho usato il punto e virgola come separatore degli elementi perchè non riesco a scrivere l'insieme in modo corretto...).
Sempre che questo sia tutto corretto, quanti altri insieme quozienti posso creare?
Risposte
Secondo me la fai troppo complicata. Ricordati che ogni relazione di equivalenza $R$ nell'insieme $A$ determina una partizione $A/R$. Trova le partizioni!! 
Vero!!! Ci penso poi scrivo qualcosa 
Il numero di relazioni di equivalenza sull'insieme $3={1,2,3}$ è dato dal numero di Bell che permette, appunto, di esprimere il numero di partizioni per un insieme finito. Il numero di Bell si calcola per ricorsione tramite $B(n)=sum_(i=1)^n ((n-1),(i-1)) B(n-i)$ e per l'insieme $3$ abbiamo che $B(3)=5$; infatti le possibile partizioni dell'insieme $3$ sono (come spoilerato da perplesso 
):
$P_1 {{1},{2},{3}]$
$P_2 {{1,2},{3}}$
$P_3 {{1,3},{2}}$
$P_4 {{2,3},{1}}$
$P_5 {1,2,3}$
Dato che sappiamo che ad ogni partizione possiamo associare una relazione di equivalenza, allora posso definire 5 insiemi quoziente:
$3/R_P_1 = {{1},{2},{3}}$
$3/R_P_2 = {{(a,b)|(a,b) in {1,2} times {1,2}}, {3}}$
$3/R_P_3 = {{(a,b)|(a,b) in {1,3} times {1,3}}, {2}}$
$3/R_P_4 = {{(a,b)|(a,b) in {2,3} times {2,3}}, {1}}$
$3/R_P_5 = {(a,b)|(a,b) in {1,2,3} times {1,2,3}}$
):$P_1 {{1},{2},{3}]$
$P_2 {{1,2},{3}}$
$P_3 {{1,3},{2}}$
$P_4 {{2,3},{1}}$
$P_5 {1,2,3}$
Dato che sappiamo che ad ogni partizione possiamo associare una relazione di equivalenza, allora posso definire 5 insiemi quoziente:
$3/R_P_1 = {{1},{2},{3}}$
$3/R_P_2 = {{(a,b)|(a,b) in {1,2} times {1,2}}, {3}}$
$3/R_P_3 = {{(a,b)|(a,b) in {1,3} times {1,3}}, {2}}$
$3/R_P_4 = {{(a,b)|(a,b) in {2,3} times {2,3}}, {1}}$
$3/R_P_5 = {(a,b)|(a,b) in {1,2,3} times {1,2,3}}$
In attesa di una conferma di quanto ho scritto prima chiederei un aiuto per questo altro esercizio:
data una relazione di equivalenza $R$ sull'insieme $X$, dimostrare che un sottoinsieme $Y sub X$ è una classe di equivalenza per la $R$ se e solo se per un certo $y in Y$ si ha $z in Y <=> yRz$.
Se $R$ è una relazione di equivalenza allora questa mi determina una partizione. Supposto che $Y$ sia un blocco della partizione, allora se è una classe di equivalenza dovrei "far vedere" che è definita da tutti e soli gli elementi che sono in relazione con un dato elemento di $Y$?
data una relazione di equivalenza $R$ sull'insieme $X$, dimostrare che un sottoinsieme $Y sub X$ è una classe di equivalenza per la $R$ se e solo se per un certo $y in Y$ si ha $z in Y <=> yRz$.
Se $R$ è una relazione di equivalenza allora questa mi determina una partizione. Supposto che $Y$ sia un blocco della partizione, allora se è una classe di equivalenza dovrei "far vedere" che è definita da tutti e soli gli elementi che sono in relazione con un dato elemento di $Y$?
Nessun aiuto?
"GundamRX91":
per un certo $y in Y$ si ha $z in Y <=> yRz$.
Beh ma questa è esattamente la definizione della classe di equivalenza $[y]$. Quindi $Y=[y]$. Viceversa se sappiamo che $Y$ è una classe di equivalenza allora ogni elemento di $Y$ è in relazioni con ogni altro elemento di $Y$. Pertanto $Y=[y]$ per ogni $y \in Y$.
Si in effetti forse è più semplice del previsto.
Nel frattempo ho provato a fare la dimostrazione in questo modo e mi piacerebbe avere il tuo parere (comprese di bacchettate):
sia $X$ un insieme e sia $R$ una relazione di equivalenza definita su $X$. Un sottoinsieme $Y sub X$ è una classe di equivalenza, rispetto $R$:
$Y=[y] <=> z in Y <=> yRz$ per un $y in Y$
$=>$
$Y=[y]={x in X| xRy}$ per definizione di classe di equivalenza; sia allora $z in X$ in relazione con un elemento $y in Y$, quindi $zRy <=> z in [y] <=> z in Y$
$Leftarrow$
$z in Y <=> yRz$ implica che $z in Y ^^ y in Y$, quindi $Y$ è l'insieme degli elementi tra loro in relazione $R$ di equivalenza, e sia allora $[Y]$ la corrispondente classe di equivalenza. Dato che una relazione di equivalenza induce una partizione allora $Y$ è un blocco di essa e, per definizione di partizione, $Y sub X$.
Nel frattempo ho provato a fare la dimostrazione in questo modo e mi piacerebbe avere il tuo parere (comprese di bacchettate
):sia $X$ un insieme e sia $R$ una relazione di equivalenza definita su $X$. Un sottoinsieme $Y sub X$ è una classe di equivalenza, rispetto $R$:
$Y=[y] <=> z in Y <=> yRz$ per un $y in Y$
$=>$
$Y=[y]={x in X| xRy}$ per definizione di classe di equivalenza; sia allora $z in X$ in relazione con un elemento $y in Y$, quindi $zRy <=> z in [y] <=> z in Y$
$Leftarrow$
$z in Y <=> yRz$ implica che $z in Y ^^ y in Y$, quindi $Y$ è l'insieme degli elementi tra loro in relazione $R$ di equivalenza, e sia allora $[Y]$ la corrispondente classe di equivalenza. Dato che una relazione di equivalenza induce una partizione allora $Y$ è un blocco di essa e, per definizione di partizione, $Y sub X$.
"GundamRX91":
$=>$
$Y=[y]={x in X| xRy}$ per definizione di classe di equivalenza; sia allora $z in X$ in relazione con un elemento $y in Y$, quindi $zRy <=> z in [y] <=> z in Y$
Vabbè.
$Leftarrow$
$z in Y <=> yRz$ implica che $z in Y ^^ y in Y$, quindi $Y$ è l'insieme degli elementi tra loro in relazione $R$ di equivalenza, e sia allora $[Y]$ la corrispondente classe di equivalenza. Dato che una relazione di equivalenza induce una partizione allora $Y$ è un blocco di essa e, per definizione di partizione, $Y sub X$.
Mah io avrei detto semplicemente... supposta vera quasta equivalenza $z in Y <=> yRz$ va da sè che $z in Y <=> yRz <=> z \in [y]$ (per definizione di $[y]$) e quindi $Y=[y]$
Ma questi esercizi che fai mi sembrano semplici applicazioni delle definizioni. Prova con questo:
Siano $A,B,C$ insiemi non vuoti e siano $f:A \rightarrow C$ e $g:B \rightarrow C$ apllicazioni surriettive. Definiamo una relazione di equivalenza $R_f$ in $A$ così $xR_{f} y <=> f(x)=f(y)$ e poi definiamo una relazione $R_g$ in $B$ allo stesso modo $xR_{g} y <=> g(x)=g(y)$. Esiste un'applicazione biettiva fra i quozienti $A/{R_f}$ e $B/{R_g}$ ??
Se è troppo facile chiedo perdono non sono bravo ad inventare...
Grazie per la risposta 
Per gli esercizi sto provando tutto quello che mi capita sotto tiro, anche quelli banali, che alla fine banali (per me) tanto non sono. Ora vedo anche il tuo esercizio e poi ti faccio sapere.
Per gli esercizi sto provando tutto quello che mi capita sotto tiro, anche quelli banali, che alla fine banali (per me) tanto non sono. Ora vedo anche il tuo esercizio e poi ti faccio sapere.
Perplesso provo a postare la soluzione, ma senza formalizzare nulla perchè non so se sia corretto.
Dunque dal fatto che $R_f$ sia una relazione di equivalenza e nello specifico $ker_f$ allora, dal primo teorema di isomorfismo, esiste una bigezione $f^{\prime}: (A/R_f) -> Imf$ tale che $f = (i_f) circ f^{\prime} circ p_f$, dove $i_f$ e $p_f$ sono rispettivamente l'immersione canonica e la proiezione canonica. Applicando lo stesso ragionamento con $R_g$ allora esiste $g^{\prime}: (A/R_g) -> Img$ tale che $g = (i_g) circ g^{\prime} circ p_g$, dove $i_g$ e $p_g$ sono rispettivamente l'immersione canonica e la proiezione canonica. Dato che $f^{\prime}$ e $g^{\prime}$ sono bigezioni allora esistono le rispettive funzioni inverse, dove $g^{\prime}'$,la inversa di $g^{\prime}$ mi permette di comporre la funzione $h: (A/R_f) -> (B/R_g)$ come $g^{\prime}' circ f^{\prime}$.
Dunque dal fatto che $R_f$ sia una relazione di equivalenza e nello specifico $ker_f$ allora, dal primo teorema di isomorfismo, esiste una bigezione $f^{\prime}: (A/R_f) -> Imf$ tale che $f = (i_f) circ f^{\prime} circ p_f$, dove $i_f$ e $p_f$ sono rispettivamente l'immersione canonica e la proiezione canonica. Applicando lo stesso ragionamento con $R_g$ allora esiste $g^{\prime}: (A/R_g) -> Img$ tale che $g = (i_g) circ g^{\prime} circ p_g$, dove $i_g$ e $p_g$ sono rispettivamente l'immersione canonica e la proiezione canonica. Dato che $f^{\prime}$ e $g^{\prime}$ sono bigezioni allora esistono le rispettive funzioni inverse, dove $g^{\prime}'$,la inversa di $g^{\prime}$ mi permette di comporre la funzione $h: (A/R_f) -> (B/R_g)$ come $g^{\prime}' circ f^{\prime}$.
Beh si dai l'idea è quella, anche se io l'avevo pensata più facile. Se $a \in A$ chi è la classe di equivalenza di $a$ rispetto a $R_f$ ?? Tutti gli elmenti di $A$ tali che la loro immagine mediante $f$ sia $f(a)$ ovvero $f^{-1}(f(a))$. Dalla surriettività di $f$ sappiamo che la controimmagine di un qualsiasi elemento di $C$ non è mai vuota, è facile allora dedurre che le classi di equivalenza determinate da $R_f$ altro non sono che le controimmagini degli elementi di $C$. Possiamo allora costruire una biezione $f^{-1}(c) \in A/{R_f} \rightarrow c \in C$. Analogamente possiamo costruire una biezione $g^{-1}(c) \in B/{R_g} \rightarrow c \in C$. Invertendo quest'ultima applicazione e componendo con la prima $f^{-1}(c) \in A/{R_f} \rightarrow c \in C \rightarrow g^{-1}(c) \in B/{R_g}$ che è la biezione cercata. Detto in altri termini $A/{R_f}$ è equipotente a $C$ che è equipotente a $B/{R_g}$.
Non so se si possa parlare di "teorema di isomorfismo" perchè non vedo dove sia il "morfismo", in reltà non vedo neanche le strutture algebriche, ma vabbè ho capito lo stesso...
Non so se si possa parlare di "teorema di isomorfismo" perchè non vedo dove sia il "morfismo", in reltà non vedo neanche le strutture algebriche, ma vabbè ho capito lo stesso...
Il fatto è che è l'unica cosa che mi è venuta in mente
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo