Given is a function $f:X\to Y$ and an equivalence relation $c$ on $Y$. For $a,b \in X$ $a \text{ } c_f \text{ } b$ if and only if $f(a) \text{ } c \text{ } f(b)$. Show that $c_f$ is an equivalence relation on $X$.
I know that it should have three cases, reflexive, symmetric and transitive.
Show reflexive:
- $\forall i \in X:i \text{ } c_f \text{ } i \text{ } $: Suppose $f(i) = y, y \in Y, \text{ then } y \text{ } c \text{ } y \text{. So } c_f \text{ is reflexive.}$
Is this correct? And could you help me with the next steps?
You have shown that $c_f$ is reflexive (not symmetric).
To prove that $c_f$ is symmetric you must show that $\forall a,b : a \ c_f\ b \iff b\ c_f\ a$
Suppose $a,b \in X$ and $a \ c_f \ b$. Therefore $f(a)\ c\ f(b)$. Since $c$ is an equivalence it is symmetric, so $f(b)\ c\ f(a)$. Therefore also $b\ c_f\ a$.
You can prove that if $b \ c_f \ a$ then $a \ c_f \ b$ exactly the same way.
Now, let's show that $f$ is transitive.
Suppose $a\ c_f\ d$ and $d\ c_f\ b$. We want to show that $a\ c_f\ b$.
From what we suppose we see that $f(a)\ c\ f(d)$ and $f(d)\ c\ f(b)$
Since $c$ is transitive, $f(a)\ c\ f(b)$. This implies that $a\ c_f\ b$.