How to prove if the relation R is an equivalence relation?

Question

Hello so I stumbled upon an exercise where I need to prove that R is an equivalence relation, normally I have no problem doing this, but with this exercise I have absolutely no clue where to begin. I think my biggest problem is understanding what's given. The exercise goes as follows:

$X$ and $Y$ are two sets. We notate $Fun(X,Y)$ is the set of all functions $f:X\rightarrow Y$. Let $R$ be the relation on $Fun(X,Y)$ given by: $(f,g) \in R$ if and only if there exist a bijective function $\sigma:Y \rightarrow Y$ with $\sigma \circ f =g $.

Prove that $R$ is an equivalence relation.

What I know

• $R$ is an equivalence relation when $R$ is reflexive, symmetric and transitive (so this is what I need to prove).

• $R$ is reflexive if for all $x\in X : xRx$

• $R$ is symmetric if for all $x,y\in X : xRy \rightarrow yRx$

• $R$ is transitive if for all $x,y,z \in X: xRy \text{ and } yRx \rightarrow xRy$

If someone could help me, it would be very kind of you :)

Thank you in advance

Answer 1

Reflexivity

For all $f\in Fun(X,Y)$ we have that $(f,f)\in R$ since $Id \circ f=f$ with $Id:Y\to Y:y\mapsto y$ the identity operator.

Symmetric

Let $(f,g)\in R$. Then there exists a bijection $\sigma:Y\to Y$ with $\sigma\circ f=g$. Then $\sigma^{-1} \circ g=f$ and since $\sigma^{-1}$ is a bijection we have $(g,f)\in R$.

Transitivity

Let $(f,g)\in R$ and $(g,h)\in R$. Then there are bijections $\sigma ,\lambda:Y\to Y$ with $\sigma \circ f=g$ and $\lambda \circ g=h$. Then $\lambda \circ \sigma \circ f=h$ and since a composition of bijection is bijective it holds that $(f,h)\in R$.

Answer 2

Although you already have a fine answer, I'm posting this because I think a picture makes it easier to understand.

The top left diagram shows the definition. If we follow the arrows across and down, first applying $f$ and then $\sigma$, we get the same thing as we would if we just took the shortcut via $g$.

The top right diagram shows the situation for reflexivity, when we have $f=g$. Clearly, $\sigma=\operatorname{id}$ is required.

The middle diagram is for symmetry. We are given $\sigma$ and we must find a $\tau$ so that if we first go diagonally by $g$ and then up by $\tau$, we get the same thing as if we went straight across by $f$. It's easy to guess $\tau=\sigma^{-1}$ from the diagram, isn't it?

The third picture is for transitivity. We are given $\sigma$ and $\tau$ such that $g=\sigma\circ f$ and $h=\tau\circ g$ and we must find $\rho$ such that $h=\rho\circ f.$ It's clear from the picture that $\rho=\tau\circ\sigma$ is what we need.