2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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$? $\endgroup$
    – JMoravitz
    Jan 8, 2021 at 14:03

2 Answers 2

5
$\begingroup$

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

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.

$\endgroup$
2
  • 1
    $\begingroup$ I cannot thank you enough for how well you explained it $\endgroup$
    – TheCreator
    Jan 8, 2021 at 15:18
  • $\begingroup$ @TheCreator My pleasure. $\endgroup$
    – saulspatz
    Jan 8, 2021 at 18:48
3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Thank you so much for answering!! $\endgroup$
    – TheCreator
    Jan 8, 2021 at 14:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .