let $B=\{1,2,3,4\}$. let $\mathscr T$ be the set of all functions from $B$ to $B$. let $\mathbb R$ be the following relation: for all $k,h \in \mathscr T$, $k\mathbb Rh $ if and only if $k(m) \le h(m)$ for some $m \in B$.

1) is $\mathbb R $ reflexive? symmetric? transitive? prove it.

I think it is transitive but I don't how to prove it. Also, are my proofs for reflexive and symmetric correct? I'm kind of confused because it says for some m in $B$. does that mean that I don't have to prove it for all $m$? is it is enough to do it for one m like I did for reflexive proof?

Thank you


1 Answer 1


The relation is not transitive. Consider $$k=\{(1, 3), (2, 3), (3, 3), (4, 3)\}$$ $$h=\{(1, 1), (2, 2), (3, 3), (4, 4)\}$$ $$g=\{(1, 1), (2, 1), (3, 1), (4, 1)\}$$ Then $kRh$, $hRg$ but $k$ is not related to $g$.

For (2), notice that $k(m)=1$ for all $m$ and so for every other function $h$ in $T$, there must be some $m$ such that $1=k(m)\leq h(m)$.

For (3), notice that the only functions $h$ for which $hRk$ is possible is if $h(m)=1$ for some $m$.

  • $\begingroup$ for 3, does h(m)= 1 for all m? or is it enough if it was {(1,1),(2,3),(3,2),(4,2)} for example $\endgroup$ Apr 2, 2017 at 7:29
  • $\begingroup$ for some $m$ is enough by definition of $R$ $\endgroup$ Apr 2, 2017 at 7:30
  • $\begingroup$ so would it be 4! ? $\endgroup$ Apr 2, 2017 at 7:31
  • $\begingroup$ not quite. Hint: how many functions do not take any $m$ to $1$? $\endgroup$ Apr 2, 2017 at 7:35
  • $\begingroup$ yes you are right $\endgroup$ Apr 2, 2017 at 7:41

You must log in to answer this question.

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