# relations and functions discrete mathematics

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$.
• for some $m$ is enough by definition of $R$ Apr 2 '17 at 7:30
• not quite. Hint: how many functions do not take any $m$ to $1$? Apr 2 '17 at 7:35