Partizioni e relazioni di equivalenza
Salve,
ho il seguente esercizio, ma, ho difficoltà nello svolgimento.
(a) Trovare tutte le partizioni di {x,y,z}
(b) Quante differenti relazioni di equivalenza ci sono su un insieme di 3 elementi?
(due relazioni di equivalenza sono differenti se essi inducono differenti partizioni).
Tentativo di risoluzione:
(a)
$P_1 = { {x}, {y}, {z} }$
$P_2 = {{x,y}, {z}}$
$P_3 = {{x},{y,z}}$
$P_4 = {{x,z},{y}}$
$P_5 = {x,y,z}$
(b)
direi che due elementi sono in relazione se appartengono allo stesso sottoinsieme della partizione:
perciò se consideriamo come insieme di 3 elementi proprio {x,y,z}, dobbiamo anche considerare una particolare partizione.
> Se consideriamo la $P_1$, gli elementi dell'insieme non sono in relazione di equivalenza in quanto si verifica solamente la prop. riflessiva.
> Se consideriamo $P_2$ abbiamo
$x ~ y$, $y ~ x$, $x ~ x$, $y ~ y$
non è soddisfatta la prop. transitiva.
> Se consideriamo $P_3$ abbiamo
$y ~ z, z ~ y, y ~ y, z ~ z$
non è soddisfatta la prop. transitiva.
>Se consideriamo $P_5$ abbiamo
$x~y, y~z \Rightarrow x~z$
$y~x, x~z \Rightarrow y~z$
etc...
è una relazione di equivalenza in quanto si verifica la prop. riflessiva, simmetrica e transitiva.
Ma non ho capito come procedere per la corretta risoluzione del punto (b), ma penso che il punto (a) sia corretto.
La soluzione, secondo i testo, per i punti (a),(b) è cinque.
Potreste per favore darmi una mano? Grazie mille!
ho il seguente esercizio, ma, ho difficoltà nello svolgimento.
(a) Trovare tutte le partizioni di {x,y,z}
(b) Quante differenti relazioni di equivalenza ci sono su un insieme di 3 elementi?
(due relazioni di equivalenza sono differenti se essi inducono differenti partizioni).
Tentativo di risoluzione:
(a)
$P_1 = { {x}, {y}, {z} }$
$P_2 = {{x,y}, {z}}$
$P_3 = {{x},{y,z}}$
$P_4 = {{x,z},{y}}$
$P_5 = {x,y,z}$
(b)
direi che due elementi sono in relazione se appartengono allo stesso sottoinsieme della partizione:
perciò se consideriamo come insieme di 3 elementi proprio {x,y,z}, dobbiamo anche considerare una particolare partizione.
> Se consideriamo la $P_1$, gli elementi dell'insieme non sono in relazione di equivalenza in quanto si verifica solamente la prop. riflessiva.
> Se consideriamo $P_2$ abbiamo
$x ~ y$, $y ~ x$, $x ~ x$, $y ~ y$
non è soddisfatta la prop. transitiva.
> Se consideriamo $P_3$ abbiamo
$y ~ z, z ~ y, y ~ y, z ~ z$
non è soddisfatta la prop. transitiva.
>Se consideriamo $P_5$ abbiamo
$x~y, y~z \Rightarrow x~z$
$y~x, x~z \Rightarrow y~z$
etc...
è una relazione di equivalenza in quanto si verifica la prop. riflessiva, simmetrica e transitiva.
Ma non ho capito come procedere per la corretta risoluzione del punto (b), ma penso che il punto (a) sia corretto.
La soluzione, secondo i testo, per i punti (a),(b) è cinque.
Potreste per favore darmi una mano? Grazie mille!
Risposte
Per a credo sia tutto giusto tranne l'ultimo punto in cui credo intendessi [tex]P_5 = \{ \{x,y,z\}\}[/tex].
Per b invece, si può dire che sono 5 le equivalenze poichè equivalenze e partizioni di un insieme sono in corrispondenza biunivoca.
Il tuo ragionamento non l'ho molto capito, la simmetria è soddisfatta se a ~ b implica b ~ a, e la transività se a ~ b e b ~ c implicano a ~ c, dove a,b,c sono elementi qualsiasi dell'insieme, se l'antecedente è falso allora la proposizione non è falsa ma vera.
[tex][/tex]
Per b invece, si può dire che sono 5 le equivalenze poichè equivalenze e partizioni di un insieme sono in corrispondenza biunivoca.
Il tuo ragionamento non l'ho molto capito, la simmetria è soddisfatta se a ~ b implica b ~ a, e la transività se a ~ b e b ~ c implicano a ~ c, dove a,b,c sono elementi qualsiasi dell'insieme, se l'antecedente è falso allora la proposizione non è falsa ma vera.
[tex][/tex]
"marco.ve":
Il tuo ragionamento non l'ho molto capito, la simmetria è soddisfatta se a ~ b implica b ~ a, e la transività se a ~ b e b ~ c implicano a ~ c, dove a,b,c sono elementi qualsiasi dell'insieme, se l'antecedente è falso allora la proposizione non è falsa ma vera.
Quello che voglio dire è, ad esempio considerando la partizione
$P_1 = {{x},{y},{z}}$
abbiamo
$x ~ x$
$y ~ y$
$z ~ z$
come fa ad essere una relazione di equivalenza se non vengono soddisfatte le prop. simmetriche e transitive?
cioè non vengono soddisfatte $x ~ y, y ~x$ e anche $x ~ y, y ~ z, x ~ z$.
O dobbiamo considerare x=y=z, cioè per la prop. riflessiva, un elemento x; per quella simmetrica due elementi x, x; e per quella transitiva x,x,x, dato che solo in questo modo sono soddisfatte?
Tu dici che
Proviamo a verificare se $P_1$ è una relazione di equivalenza ...
1) riflessiva: è vera perché ogni elemento dell'insieme è in relazione con se stesso dato un elemento non può appartener a due sottoinsiemi diversi
2) simmetrica: è vera perché dato che i sottoinsiemi sono tutti dei singoletti ogni elemento è in relazione solo con stesso quindi dato che $aRb$ è automaticamente sempre e solo $aRa$ anche $bRa$ (ovvero in pratica $aRa$) apparterrà alla stessa relazione.
3) transitiva: è vera per lo stesso ragionamento del punto 2)
Quindi $P_1$ è una relazione di equivalenza ...
"cloe009":
... due elementi sono in relazione se appartengono allo stesso sottoinsieme della partizione ...
Proviamo a verificare se $P_1$ è una relazione di equivalenza ...
1) riflessiva: è vera perché ogni elemento dell'insieme è in relazione con se stesso dato un elemento non può appartener a due sottoinsiemi diversi
2) simmetrica: è vera perché dato che i sottoinsiemi sono tutti dei singoletti ogni elemento è in relazione solo con stesso quindi dato che $aRb$ è automaticamente sempre e solo $aRa$ anche $bRa$ (ovvero in pratica $aRa$) apparterrà alla stessa relazione.
3) transitiva: è vera per lo stesso ragionamento del punto 2)
Quindi $P_1$ è una relazione di equivalenza ...
ok, grazie mille! Come pensavo, anche se l'ho scritto in un modo disordinato!
Quindi se prendiamo $P_2 = {{x,y},{z}}$ e
verifichiamo la prop. riflessiva:
$xRx,$
$yRy,$
$zRz$
verifichiamo la prop. simmetrica
$xRy \Rightarrow yRx$
$zRz \Rightarrow zRz$
verifichiamo la prop. transitiva:
$xRy, yRx \Rightarrow xRx$,
$yRx, xRy \Rightarrow yRy$,
$zRz, zRz \Rightarrow zRz$,
è corretto?
Quindi se prendiamo $P_2 = {{x,y},{z}}$ e
verifichiamo la prop. riflessiva:
$xRx,$
$yRy,$
$zRz$
verifichiamo la prop. simmetrica
$xRy \Rightarrow yRx$
$zRz \Rightarrow zRz$
verifichiamo la prop. transitiva:
$xRy, yRx \Rightarrow xRx$,
$yRx, xRy \Rightarrow yRy$,
$zRz, zRz \Rightarrow zRz$,
è corretto?
A rigore mancherebbero alcuni casi (quali? 
) ma direi che va bene ...
) ma direi che va bene ...
forse per la prop. simmetrica:
$xRx \Rightarrow xRx$
$yRy \Rightarrow yRy$
e forse per la prop. transitiva:
$xRx, xRx \Rightarrow xRx$
$yRy, yRy \Rightarrow yRy$
o no?
$xRx \Rightarrow xRx$
$yRy \Rightarrow yRy$
e forse per la prop. transitiva:
$xRx, xRx \Rightarrow xRx$
$yRy, yRy \Rightarrow yRy$
o no?
Yes, non mi pare ce ne siano altri ...
grazie mille davvero, mi sei stato di grande aiuto! 
Vorrei solo aggiungere che la verifica "a mano" è molto utile per "assimilare" questi concetti ma dal punto di vista pratico è utilizzabile solo quandi i casi sono molto pochi; normalmente ci si arriva col ragionamento ...
Per esempio, in questo caso, se volessi dimostrare che la nostra relazione possiede la proprietà simmetrica potrei dire che se $a$ è in relazione con $b$, questo significa che appartengono allo stesso sottoinsieme e di conseguenza anche $b$ è in relazione con $a$; proprietà dimostrata.
Cordialmente, Alex
Per esempio, in questo caso, se volessi dimostrare che la nostra relazione possiede la proprietà simmetrica potrei dire che se $a$ è in relazione con $b$, questo significa che appartengono allo stesso sottoinsieme e di conseguenza anche $b$ è in relazione con $a$; proprietà dimostrata.
Cordialmente, Alex
"cloe009":
(b) Quante differenti relazioni di equivalenza ci sono su un insieme di 3 elementi?
Rispondendo alla domanda: sono 5
$R_1 = {(x,x), (y,y), (z,z)}$
$R_2 = {(x,x), (y,y), (z,z), (x,y), (y,x)}$
$R_3 = {(x,x), (y,y), (z,z), (y,z), (z,y)}$
$R_4 = {(x,x), (y,y), (z,z), (x,z), (z,x)}$
$R_5 = {(x,x), (y,y), (z,z), (x,y), (x,z), (y,x), (y,z), (z,x), (z,y)}$
"cloe009":
(due relazioni di equivalenza sono differenti se essi inducono differenti partizioni).
se non sbaglio per indurre differenti partizioni, dobbiamo considerare la definizione di classe di equivalenza.
Dalla definizione di classe di equivalenza:
Sia $R$ una relazione di equivalenza su un insieme $S$, sia $a \in S$, e sia $[a] = {x \in S : a R x}$.
Questo sottoinsieme $[a]$ di $S$ viene chiamato classe di equivalenza di $a$ (relativa a $R$)
consideriamo perciò ogni singolo elemento del notro insieme ${x,y,z}$
e per la $R_1$
$[x] = {x}$
$[y] = {y}$
$[z] = {z}$
per la $R_2$
$[x] = {x,y}$
$[y] = {x,y}$
$[z] = {z}$
per la $R_3$
$[x] = {x}$
$[y] = {y,z}$
$[z] = {y,z}$
per la $R_4$
$[x] = {x,z}$
$[y] = {y}$
$[z] = {x,z}$
per la $R_5$
$[x] = {x,y,z}$
$[y] = {x,y,z}$
$[z] = {x,y,z}$
perciò, ad esempio, considerando e relazioni $R_1, R_2$,
esse sono differenti relazioni di equivalenza in quanto l'insieme delle classi di equivalenza di ognuno di essi forma una differente partizione.
Inoltre è da tener conto che, per definizione, due classi di equivalenza sono distinte se sono disgiunte.
Infatti se consideriamo l'insieme quoziente del nostro insieme, (che chiamiamo S), $S = {x,y,z}$ secondo la relazione di equivalenza $R_1$ essa è:
[tex]S/R_1 = \left \{[x],[y],[z] \right \}[/tex]
sono tre distinte classi di equivalenza, e sono disgiunte e formano una partizione.
se invece, consideriamo l'insieme quoziente del nostro insieme, (che chiamiamo S), $S = {x,y,z}$ secondo la relazione di equivalenza $R_2$ essa è:
[tex]S/R_2 = \left \{[x],[z] \right \}[/tex]
sono due distinte classi di equivalenza, e sono disgiunte e formano una partizione.
e così via...
quindi dovrebbe essermi chiaro il perchè:
"marco.ve":
equivalenze e partizioni di un insieme sono in corrispondenza biunivoca
cioè iniettiva e suriettiva, cioè ogni elemento del codominio è immagine di un unico elemento nel dominio
se prendiamo in considerazione [tex]S/R_1, P_1[/tex],
$[x] \rightarrow {x}$
$[y] \rightarrow {y}$
$[z] \rightarrow {z}$
se prendiamo in considerazione [tex]S/R_2, P_2[/tex], con $[x] = [y]$
$[x] \rightarrow {x,y}$
$[z] \rightarrow {z}$
cioè potremmo considerare una funzione che associa alla particolare classe nel dominio, la corrpispondente partizione nel codominio, per esempio
$f([x]) = {x,y}$
$f([y]) = {x,y}$
$xRy$ perchè $f([x]) = f([y]) = {x,y}$
o è sbagliato? Cosa ne pensate? Grazie mille!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo