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!


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.