# Finding equivalence classes in a set of functions with a condition

I can't seem to work around this problem...

Let $n$ and $m$ be two positive integers. $F$ is the set of functions from {1,..,n} to {1,...,m}. We define the relation $R$ as: $f R g$ if and only if there exists a bijective function $h$ from {1,...,n} to {1,...,n} such that $f \circ h = g$.

Prove that $R$ is a relation of equivalence. How many equivalence relations are there? What if $F$ is the set of only injective functions? What if they are surjectives?

For instance... proving that $R$ is reflexive, $f R f$, this would imply $h(x) = x$ because $f \circ h = f$. And this would be possible because $h$ is bijective. If this is right, how should I continue? Trying to prove symmetry the same way? i.e.

$f R g ----> g R f$

$f(h(x)) = g(x)$

$g(h(x)) = f(x)$

There's something I'm missing here... I get stuck in the same with the transitive property.

Thanks!

Consider: if $h$ is bijective, then it has an inverse, namely $h^{-1}$. How can you apply that to $f\circ h=g$?
For transitivity, just remember what your proof should like: assume that you have some bijections $j$ and $k$ such that $f\circ j=g$, and $g\circ k=h$. You want some function $l$ such that $f\circ l=h$. Can you see how putting the previous two assumptions give you what you want?
• like this? $f \circ h \circ h^{-1} = g \circ h^{-1}$ – jrs Apr 21 '16 at 17:29
• Yep. And of course, if $h$ is a bijection, what can you say about $h^{-1}$? – Kevin Long Apr 21 '16 at 21:05