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


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 '17 at 7:29
  • $\begingroup$ for some $m$ is enough by definition of $R$ $\endgroup$ Apr 2 '17 at 7:30
  • $\begingroup$ so would it be 4! ? $\endgroup$ Apr 2 '17 at 7:31
  • $\begingroup$ not quite. Hint: how many functions do not take any $m$ to $1$? $\endgroup$ Apr 2 '17 at 7:35
  • $\begingroup$ yes you are right $\endgroup$ Apr 2 '17 at 7:41

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.