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.



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?

  • $\begingroup$ like this? $f \circ h \circ h^{-1} = g \circ h^{-1}$ $\endgroup$ – jrs Apr 21 '16 at 17:29
  • $\begingroup$ Yep. And of course, if $h$ is a bijection, what can you say about $h^{-1}$? $\endgroup$ – Kevin Long Apr 21 '16 at 21:05

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.