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

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 :)

• Given $fRg$, that is $\sigma\circ f = g$ for some $\sigma$ a bijection, does $\sigma^{-1}$ exist? Can you explain that? Can you explain why this would mean $f = \sigma^{-1}\circ g$ and why this implies $gRf$? Jan 8, 2021 at 14:03

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.

• I cannot thank you enough for how well you explained it Jan 8, 2021 at 15:18
• @TheCreator My pleasure. Jan 8, 2021 at 18:48

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$$.

• Thank you so much for answering!! Jan 8, 2021 at 14:11