Relazione di equivalenza <-> Partizioni
Questa e' la parte di testo antecedente l'esercizio richiesto:
"Quanto precede prova che ad ogni relazione di equivalenza $R$ sull'insieme
$A$ resta associata una partizione di $A$; viceversa, ad ogni assegnata partizione $P$
dell'insieme $A$ (che e', ripetiamolo, una famiglia $P = {A_i | i in I)$ di sottoinsiemi $A_i$ di $A$ - che vengono detti blocchi della partizione -
che siano non vuoti, a due a due disgiunti e la cui unione $U_i in IA_i$ coincida con $A$) possiamo associare la relazione di equivalenza $R_p$
su $A$ definita da: $aR_Pb <=> EEi in I(a in A_i ^^ b in A_i)$. In altri termini, due elementi $a,b in A$
sono equivalenti se e solo se appartengono allo stesso blocco della partizione.
Per esercizio si provi che si tratta proprio di una relazione d'equivalenza e
inoltre che se, partendo da una relazione d'equivalenza $R$ associamo a questa
una partizione $P$, e poi a questa partizione associamo la relazione $R_P$, allora
quest'ultima coincide con la relazione $R$ da cui siamo partiti."
Quest'ultima parte e' l'esercizio vero e proprio.
Da quanto capito la relazione definisce la classe di equivalenza (e di conseguenza la partizione) e viceversa, ma non capisco come impostare l'esercizio....
"Quanto precede prova che ad ogni relazione di equivalenza $R$ sull'insieme
$A$ resta associata una partizione di $A$; viceversa, ad ogni assegnata partizione $P$
dell'insieme $A$ (che e', ripetiamolo, una famiglia $P = {A_i | i in I)$ di sottoinsiemi $A_i$ di $A$ - che vengono detti blocchi della partizione -
che siano non vuoti, a due a due disgiunti e la cui unione $U_i in IA_i$ coincida con $A$) possiamo associare la relazione di equivalenza $R_p$
su $A$ definita da: $aR_Pb <=> EEi in I(a in A_i ^^ b in A_i)$. In altri termini, due elementi $a,b in A$
sono equivalenti se e solo se appartengono allo stesso blocco della partizione.
Per esercizio si provi che si tratta proprio di una relazione d'equivalenza e
inoltre che se, partendo da una relazione d'equivalenza $R$ associamo a questa
una partizione $P$, e poi a questa partizione associamo la relazione $R_P$, allora
quest'ultima coincide con la relazione $R$ da cui siamo partiti."
Quest'ultima parte e' l'esercizio vero e proprio.
Da quanto capito la relazione definisce la classe di equivalenza (e di conseguenza la partizione) e viceversa, ma non capisco come impostare l'esercizio....
Risposte
R_p la dimostri normalmente
Detta molto alla buona
per ogni $x in A$ se $xR_px$ inizia a ragiona sul fatto che se $x$ appartiene a $A$, allora $x$ appartiene anche a un blocco di una partizione di $A$ e che allora esiste un blocco di $A$ in $a$ cui $x$ appartiene e siccome $x$ è in relazione con tutti gli elementi di uno stesso blocco allora $R_p$ è riflessiva.
Poi si tratta di dimostrare le atre proprietà affinchè si possa dire che "R_p" è una relazione di equivalenza.
Se poi non ho capito male la seconda parte ...
Nel caso opposto parti dai blocchi di $A$ e considera che gli elementi di ogni blocco sono in relazione di equivalenza fra loro cioè $aRb$ con $a$ e $b$ appartenenti allo stesso blocco e verificandone le proprietà dovresti riottenere la stessa definizione di $R_p$. Cioè $R$ e $R_p$ coincidono.
Detta molto alla buona
per ogni $x in A$ se $xR_px$ inizia a ragiona sul fatto che se $x$ appartiene a $A$, allora $x$ appartiene anche a un blocco di una partizione di $A$ e che allora esiste un blocco di $A$ in $a$ cui $x$ appartiene e siccome $x$ è in relazione con tutti gli elementi di uno stesso blocco allora $R_p$ è riflessiva.
Poi si tratta di dimostrare le atre proprietà affinchè si possa dire che "R_p" è una relazione di equivalenza.
Se poi non ho capito male la seconda parte ...
Nel caso opposto parti dai blocchi di $A$ e considera che gli elementi di ogni blocco sono in relazione di equivalenza fra loro cioè $aRb$ con $a$ e $b$ appartenenti allo stesso blocco e verificandone le proprietà dovresti riottenere la stessa definizione di $R_p$. Cioè $R$ e $R_p$ coincidono.
Intanto grazie per la traccia, ora vedo di ragionarci su.
A presto, spero.......
A presto, spero.......
Ragazzi sto diventando pazzo!!! A proposito di questo esercizio stavo cercando di avere chiari i concetti per poterlo risolvere, quindi volevo avere una conferma.
Le partizioni di un insieme sono definite in pratica dalle relative classi di equivalenza, o blocchi; e' corretto?
Inoltre tutte le partizioni di un insieme possono essere viste come l'insieme delle parti di quell'insieme??
Le partizioni di un insieme sono definite in pratica dalle relative classi di equivalenza, o blocchi; e' corretto?
Inoltre tutte le partizioni di un insieme possono essere viste come l'insieme delle parti di quell'insieme??
L'insieme delle parti di $A$ è un insieme che contiene tutti i sottoinsiemi di $A$
$A={z,w,q}$
$P(A)={\emptyset,{z},{w},{q},{z,w},{z,q},{w,q},{z,w,q}}$
vedi anche: http://it.wikipedia.org/wiki/Insieme_delle_parti
------------------------------------------------------------------------------
Una partizione di $A$ è la divisione di un insieme in sottoinsiemi disgiunti di $A$
$A={1,2,3,4,5,6,7}$
$A_1={1}$
$A_2={2,3,4}$
$A_3={5}$
$A_3={6,7}$
vedi anche: http://it.wikipedia.org/wiki/Partizione ... insiemi%29
------------------------------------------------------------------------------
Se hai una relazione di equivalenza su $A$
Le classi di equivalenza che ne derivano sono tutti insiemi disgiunti a due a due e la loro unione da $A$, quindi le classi di equivalenza sono una particolare partizione di $A$.
$A={z,w,q}$
$P(A)={\emptyset,{z},{w},{q},{z,w},{z,q},{w,q},{z,w,q}}$
vedi anche: http://it.wikipedia.org/wiki/Insieme_delle_parti
------------------------------------------------------------------------------
Una partizione di $A$ è la divisione di un insieme in sottoinsiemi disgiunti di $A$
$A={1,2,3,4,5,6,7}$
$A_1={1}$
$A_2={2,3,4}$
$A_3={5}$
$A_3={6,7}$
vedi anche: http://it.wikipedia.org/wiki/Partizione ... insiemi%29
------------------------------------------------------------------------------
Se hai una relazione di equivalenza su $A$
Le classi di equivalenza che ne derivano sono tutti insiemi disgiunti a due a due e la loro unione da $A$, quindi le classi di equivalenza sono una particolare partizione di $A$.
E' vero, avevo dimenticato che le partizioni sono disgiunte tra loro. Bene questo pone fine alla questione partizioni, mentre per le classi di equivalenza, in parte, avevo capito bene 
provo a dimostrare che la $R_P$ e' una relazione di equivalenza.
Per essere tale la relazione di equivalenza deve soddisfare le proprieta' Riflessiva, Simmetrica e Transitiva.
Proprieta' Riflessiva:
se un elemento $a in A$ allora $a in A_i$ che un blocco della partizione $P$ di $A$, da cui la proprieta' riflessiva e' sicuramente verificata in quanto $a-=a$ e $aR_Pa$
Proprieta' Simmetrica
$aR_Pb => bR_Pa$ se $a-=b$ allora $a=b$ e se faccio $a*(-1)=b*(-1)$ ottengo $-a=-b$ e $b=a$ da cui $bR_Pa$
Proprieta' Transitiva
$aR_Pb ^^ bR_Pc => aR_Pc$ dalla proprieta' simmetrica sappiamo che $a-=b$ quindi appartengono allo stesso blocco $A_i$ della partizione, quindi se $aR_Pb$, $b$ per essere in relazione con un altro elemento $c$ quest'ultimo deve appartenere allo stesso blocco $c in A_i$; quindi se $bR_Pc$ ne consegue che anche $aR_Pc$
Bene, bastonatemi pure (spero che attaccato al bastone ci sia anche una spiegazione )
Per essere tale la relazione di equivalenza deve soddisfare le proprieta' Riflessiva, Simmetrica e Transitiva.
Proprieta' Riflessiva:
se un elemento $a in A$ allora $a in A_i$ che un blocco della partizione $P$ di $A$, da cui la proprieta' riflessiva e' sicuramente verificata in quanto $a-=a$ e $aR_Pa$
Proprieta' Simmetrica
$aR_Pb => bR_Pa$ se $a-=b$ allora $a=b$ e se faccio $a*(-1)=b*(-1)$ ottengo $-a=-b$ e $b=a$ da cui $bR_Pa$
Proprieta' Transitiva
$aR_Pb ^^ bR_Pc => aR_Pc$ dalla proprieta' simmetrica sappiamo che $a-=b$ quindi appartengono allo stesso blocco $A_i$ della partizione, quindi se $aR_Pb$, $b$ per essere in relazione con un altro elemento $c$ quest'ultimo deve appartenere allo stesso blocco $c in A_i$; quindi se $bR_Pc$ ne consegue che anche $aR_Pc$
Bene, bastonatemi pure (spero che attaccato al bastone ci sia anche una spiegazione
)
La proprietà simmetrica non la puoi dimostrare cosi' perchè moltipilcare per $-1$ non è lecito.
Ti faccio un esempio
$A={"cane,gatto,topo,pollo,tacchino,piccione,vipera,cobra,pitone"}$
$A_1={"cane,gatto,topo"}$
$A_2={"pollo,tacchiono,piccione"}$
$A_3={"vipera,cobra,pitone"}$
$I={1,2,3}$
$A_1capA_2=emptyset$
$A_2capA_3=emptyset$
$A_1capA_3=emptyset$
e
$A_1cupA_2cupA_3=A$
Quindi $(A_1,A_2,A_3)$ è una partizione di $A$
Definisco la relazione $R_p$ su $A$: $a,b in A$ , $aR_Pb <=> EEi in I(a in A_i ^^ b in A_i)$
$"pollo"R_p"tacchino"$ e anche $"tacchino"R_p"pollo"$.
Però no puoi dire che siccome $"-1*pollo"="-1*tacchino"$ e quindi $"tacchino"="pollo"$ è un'operazione che non puoi fare sui polli e tacchini.
Con le operazioni di moltiplicazione che hai fatto hai già deciso che $"-tacchino"R_p"-pollo"$ ma $"-tacchino"$ e $"-pollo"$ non appartengono ad $A$ e tanto meno a qualsiasi partizione di $A$. In pratica lo vedrai più avanti stai dicendo che $-pollo$ è l'opposto del $pollo$. (Stai usando delle proprietà che valgono per altre strutture algebriche).
La transitiva riguardala un pò.. ci se quasi $aequivb$ non credo sia proprio corretto qui stai dicendo già che due elementi di $A$ sono in relazione di equivalenza quando ancora l'equivalenza non è dimostrata.(Qui dovresti avere il parere di uno algebrista, perchè forse va bene), il fatto di "appoggiarsi" alla simmetria, rifletti sul fatto che ci sono relazioni transitive ma che non sono simmetriche.
Ciao
Ti faccio un esempio
$A={"cane,gatto,topo,pollo,tacchino,piccione,vipera,cobra,pitone"}$
$A_1={"cane,gatto,topo"}$
$A_2={"pollo,tacchiono,piccione"}$
$A_3={"vipera,cobra,pitone"}$
$I={1,2,3}$
$A_1capA_2=emptyset$
$A_2capA_3=emptyset$
$A_1capA_3=emptyset$
e
$A_1cupA_2cupA_3=A$
Quindi $(A_1,A_2,A_3)$ è una partizione di $A$
Definisco la relazione $R_p$ su $A$: $a,b in A$ , $aR_Pb <=> EEi in I(a in A_i ^^ b in A_i)$
$"pollo"R_p"tacchino"$ e anche $"tacchino"R_p"pollo"$.
Però no puoi dire che siccome $"-1*pollo"="-1*tacchino"$ e quindi $"tacchino"="pollo"$ è un'operazione che non puoi fare sui polli e tacchini.
Con le operazioni di moltiplicazione che hai fatto hai già deciso che $"-tacchino"R_p"-pollo"$ ma $"-tacchino"$ e $"-pollo"$ non appartengono ad $A$ e tanto meno a qualsiasi partizione di $A$. In pratica lo vedrai più avanti stai dicendo che $-pollo$ è l'opposto del $pollo$. (Stai usando delle proprietà che valgono per altre strutture algebriche).
La transitiva riguardala un pò.. ci se quasi $aequivb$ non credo sia proprio corretto qui stai dicendo già che due elementi di $A$ sono in relazione di equivalenza quando ancora l'equivalenza non è dimostrata.(Qui dovresti avere il parere di uno algebrista, perchè forse va bene), il fatto di "appoggiarsi" alla simmetria, rifletti sul fatto che ci sono relazioni transitive ma che non sono simmetriche.
Ciao
E se mi facilito la vita usando le tavole di verita??? In pratica la proprieta' riflessiva la potrei dimostrare dicendo che
affinche' $aR_pb => bR_Pa$ sia vera deve essere vero almeno il secondo enunciato $bR_Pa$, e a maggior ragione se lo sono entrambi, e questo dimostra quindi che $a,b in A_i$
affinche' $aR_pb => bR_Pa$ sia vera deve essere vero almeno il secondo enunciato $bR_Pa$, e a maggior ragione se lo sono entrambi, e questo dimostra quindi che $a,b in A_i$
Stesso discorso per la proprieta' transitiva, dove bisogna verificare che $aR_Pb ^^ bR_Pc => aR_Pc$
ma affinche' questo enunciato sia nel suo complesso vero bisogna che la prima parte $aR_Pb ^^ bR_Pc$ sia vera, e cioe'
che $aR_Pb$ e $bR_Pc$ siano veri, e questo implica che se $a,b in A_i$ allora anche $b,c in A_i$, ma allora anche $a,c in A_i$ e quindi $aR_Pc$ e' vera.
Come ragionamento puo' andare ora?
ma affinche' questo enunciato sia nel suo complesso vero bisogna che la prima parte $aR_Pb ^^ bR_Pc$ sia vera, e cioe'
che $aR_Pb$ e $bR_Pc$ siano veri, e questo implica che se $a,b in A_i$ allora anche $b,c in A_i$, ma allora anche $a,c in A_i$ e quindi $aR_Pc$ e' vera.
Come ragionamento puo' andare ora?
La riflessiva andava bene è solo la scritta con $\equiv$ che non so se è corretta o no.
Ma la riflessiva va bene.
Sara $a in A_i$ per un $i in I$.
il resto lo leggo dopo ciao.
Ma la riflessiva va bene.
Sara $a in A_i$ per un $i in I$.
il resto lo leggo dopo ciao.
in effetti mi sono confuso... intendevo la proprieta' simmetrica prima, non la riflessiva.
Grazie comunque
Grazie comunque
L'altro esercizio chiedeva di provare che partendo da una relazione di equivalenza $R$ associata ad una partizione $P$, e se a quest'ultima associamo la relazione $R_P$, allora questa coincide con la relazione di partenza.
Io sono partito dalla relazione di equivalenza che e' un sottoinsieme del prodotto cartesiano di un insieme per se stesso:
$R sube A xx A = {(a,b)| a,b in A ^^ a-=b} => [(a,b)]_-= => (a,b in A_i) sub P => EEi in I(a in A_i ^^ b in A_i) = aR_Pb$
Io sono partito dalla relazione di equivalenza che e' un sottoinsieme del prodotto cartesiano di un insieme per se stesso:
$R sube A xx A = {(a,b)| a,b in A ^^ a-=b} => [(a,b)]_-= => (a,b in A_i) sub P => EEi in I(a in A_i ^^ b in A_i) = aR_Pb$
perchè usi così tanti simboli?
le dimostrazioni di cerlienco sono belle perchè, in fin dei conti, semplici ma esplicative.
Posto $P={A_i t.c. i in I}$
con $I$ un insieme infinito di indici (vedi il teorema di Scelta o di Zermelo al primo capitolo della dispensa)
$aRb iff a in A_i ^^^ b in A_i iff aR_pb$
per quanto riguarda il dimostrare che $aR_pb iff EE i in I (a in A_i ^^^ b in A_i)$ è una relazione di equivalenza, puoi partire semplicemente dalla definizione:
Proprietà riflessiva:
$aR_px iff a in A_i ^^^ x in A_i$ posto $x=a$ avrai che l'enunciato precedente vale $iff a in A_i ^^^ a in A_i iff aR_pa$
Proprietà simmetrica:
$aR_pb iff a in A_i ^^^ b in A_i iff b in A_i ^^^ a in A_ì iff bR_pa$
Proprietà transitiva:
$(aR_pb iff a in A_i ^^^ b in A_i) ^^^(bR_pc iff b in A_i ^^^ c in A_i) => a in A_i ^^^ b in A_i ^^^ c in A_i => a in A_ì ^^^ c in A_i iff aR_pc$
le dimostrazioni di cerlienco sono belle perchè, in fin dei conti, semplici ma esplicative.
Posto $P={A_i t.c. i in I}$
con $I$ un insieme infinito di indici (vedi il teorema di Scelta o di Zermelo al primo capitolo della dispensa)
$aRb iff a in A_i ^^^ b in A_i iff aR_pb$
per quanto riguarda il dimostrare che $aR_pb iff EE i in I (a in A_i ^^^ b in A_i)$ è una relazione di equivalenza, puoi partire semplicemente dalla definizione:
Proprietà riflessiva:
$aR_px iff a in A_i ^^^ x in A_i$ posto $x=a$ avrai che l'enunciato precedente vale $iff a in A_i ^^^ a in A_i iff aR_pa$
Proprietà simmetrica:
$aR_pb iff a in A_i ^^^ b in A_i iff b in A_i ^^^ a in A_ì iff bR_pa$
Proprietà transitiva:
$(aR_pb iff a in A_i ^^^ b in A_i) ^^^(bR_pc iff b in A_i ^^^ c in A_i) => a in A_i ^^^ b in A_i ^^^ c in A_i => a in A_ì ^^^ c in A_i iff aR_pc$
ho capito, quindi bastava usare la doppia implicazione per giustificare le varie proprieta'/relazioni.... Non ho capito invece quando usi i punti interrogativi come indice dell'insieme $A$.
Grazie
Grazie
"GundamRX91":
ho capito, quindi bastava usare la doppia implicazione per giustificare le varie proprieta'/relazioni.... Non ho capito invece quando usi i punti interrogativi come indice dell'insieme $A$.
Grazie
non ho usato punti interrogativi O_o
ho usato l'indice in basso a destra i
ok, ok ora ho capito. Grazie ancora!!!
Invece per l'altra dimostrazione che mi dici, e' corretta? Intendo quella dell'associazione tra partizione e relazione di equivalenza?
Invece per l'altra dimostrazione che mi dici, e' corretta? Intendo quella dell'associazione tra partizione e relazione di equivalenza?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo