Relazioni di equivalenza
Ciao a tutti, ho problemi nello svolgere esercizi del tipo "Dimostrare che...", nello specifico mi trovo a risolvere alcuni esercizi sulle relazioni di equivalenza. L'esercizio è il seguente :
1. (a) Siano $ U,V \ne ∅ $ e sia $ f:U→V $ una funzione. Dati $ x,y∈ U $, diciamo che $ x ∼ y$ se e solo se$ f(x) = f(y)$. Dimostrare che si tratta di una relazione di equivalenza.
(b) Sia $ U \ne ∅ $ e $ ∼ $ una relazione di equivalenza su U. Siano $ a $ e $ b $ due elementi di $ U $ e $ a ̃ $ e $ ̃b $ le rispettive classi di equivalenza. Dimostrare che $ a ̃ = ̃b $ se e solo se $ a ∼ b. $
Vi posto il mio ragionamento:
Partendo dalla definizione di relazione di equivalenza sò che x$∼ $y deve essere riflessiva, transitiva e simmetrica.
Ma come faccio a dimostrarlo ? Mi basta dire che dato $ f(x) = f(y) $ allora posso affermare :
-che $ f(x) = f(x) $ (RIFLESSIVA Verificata)
- che $ f(x) = f(y)$ allora $ f(y) = f(x) $ (Simmetrica Verificata)
- che $ f(x) = f(y) e f(y) = f(z) $ allora $ f(x) = f(z) $ sempre grazie al fatto che so che $ f(x) = f(y) $
E' corretto questo mio ragionamento?
Mentre per il punto b come potrei fare? Consigli generici per questa tipologia di esercizi?
Grazie e scusate il distrurbo
P.S spero di aver scritto in maniera leggibile (prima volta nel forum
)
1. (a) Siano $ U,V \ne ∅ $ e sia $ f:U→V $ una funzione. Dati $ x,y∈ U $, diciamo che $ x ∼ y$ se e solo se$ f(x) = f(y)$. Dimostrare che si tratta di una relazione di equivalenza.
(b) Sia $ U \ne ∅ $ e $ ∼ $ una relazione di equivalenza su U. Siano $ a $ e $ b $ due elementi di $ U $ e $ a ̃ $ e $ ̃b $ le rispettive classi di equivalenza. Dimostrare che $ a ̃ = ̃b $ se e solo se $ a ∼ b. $
Vi posto il mio ragionamento:
Partendo dalla definizione di relazione di equivalenza sò che x$∼ $y deve essere riflessiva, transitiva e simmetrica.
Ma come faccio a dimostrarlo ? Mi basta dire che dato $ f(x) = f(y) $ allora posso affermare :
-che $ f(x) = f(x) $ (RIFLESSIVA Verificata)
- che $ f(x) = f(y)$ allora $ f(y) = f(x) $ (Simmetrica Verificata)
- che $ f(x) = f(y) e f(y) = f(z) $ allora $ f(x) = f(z) $ sempre grazie al fatto che so che $ f(x) = f(y) $
E' corretto questo mio ragionamento?
Mentre per il punto b come potrei fare? Consigli generici per questa tipologia di esercizi?
Grazie e scusate il distrurbo
P.S spero di aver scritto in maniera leggibile (prima volta nel forum
)
Risposte
Ciao e benvenuto !
Penso sia sufficiente far vedere che due classi di equivalenza o coincidono o sono disgiunte.
Comincerei il ragionamento in questa maniera (chiamo $cl(a)$ la classe di equivalenza di $a$):
Se $cl(a) \ne cl(b) \Rightarrow \exists x \in cl(a) \wedge x \notin cl(b)$
a questo punto se $x \in cl(a) \Rightarrow x∼a$ ma supponendo $a∼b$ per la proprietà transitiva è anche $x∼b$ e allora $x \in cl(b)$ e ciò contraddice l'ipotesi iniziale...
In alternativa supponendo che $a∼b$ allora $b∼a$,
Se $x \in cl(a) \Rightarrow a∼x$ e $x∼a$ e per la transitiva, essendo $a∼b$, si ha anche che $x∼b$ per cui $x \in cl(b)$
pertanto $cl(a) \subseteq cl(b)$
invertendo i ruoli si conclude che $cl(b) \subseteq cl(a)$ e dalla doppia inclusione
$a∼b \Rightarrow cl(a)=cl(b)$
"delghi7":
(b) Sia $ U \ne ∅ $ e $ ∼ $ una relazione di equivalenza su U. Siano $ a $ e $ b $ due elementi di $ U $ e $ a ̃ $ e $ ̃b $ le rispettive classi di equivalenza. Dimostrare che $ a ̃ = ̃b $ se e solo se $ a ∼ b. $
Penso sia sufficiente far vedere che due classi di equivalenza o coincidono o sono disgiunte.
Comincerei il ragionamento in questa maniera (chiamo $cl(a)$ la classe di equivalenza di $a$):
Se $cl(a) \ne cl(b) \Rightarrow \exists x \in cl(a) \wedge x \notin cl(b)$
a questo punto se $x \in cl(a) \Rightarrow x∼a$ ma supponendo $a∼b$ per la proprietà transitiva è anche $x∼b$ e allora $x \in cl(b)$ e ciò contraddice l'ipotesi iniziale...
In alternativa supponendo che $a∼b$ allora $b∼a$,
Se $x \in cl(a) \Rightarrow a∼x$ e $x∼a$ e per la transitiva, essendo $a∼b$, si ha anche che $x∼b$ per cui $x \in cl(b)$
pertanto $cl(a) \subseteq cl(b)$
invertendo i ruoli si conclude che $cl(b) \subseteq cl(a)$ e dalla doppia inclusione
$a∼b \Rightarrow cl(a)=cl(b)$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo