Suppose f is a bijection between two sets A and B. Then x, y ∈ A gives us
f(x), f(y) ∈ B. Prove that bijections preserve equivalence relations. That is, if
R is an equivalence relation on A, then R' is an equivalence relation on B, where R' is defined as the relation such that f(x)R'f(y) if and only if xRy, where x, y ∈ A,(therefore f(x), f(y) ∈ B).
I know to prove equivalence relation of R' we just need to prove that the relation is still reflexive, transitive, and symmetric.
By the definition of injectivity, we know that if x is not equal to y, then f(x) is not equal to f(y). From this we know that if xRy and yRx exist, f(x)R'f(y) exists and f(y)R'f(x) exists. This proves symmetry.
How do you prove reflexivity and transitivity? Thanks!
Best Answer
Let $y \in B$. Then $y = f(x)$ for some $x \in A$ since $f$ is surjective. Since $R$ is reflexive, we have $xRx$. Therefore we have have $f(x)R'f(x)$ by definition. So $R'$ is reflexive.
Let $x,y,z \in B$ such that $xR'yR'z$. Since $f$ is surjective, we have $x = f(a), y = f(b), z = f(c)$ for some $a,b,c \in R$. Since $f$ is injective, by defintion of $R'$, we must have $aRbRc$. Then since $R$ is transitive, we have $aRc$, so then $f(a)R'f(c)$. So $R'$ is transitive.