1
$\begingroup$

I have set $A=\{1, 2, 3\}$. $M$ is set of all relations on $A$.

$t:M \to M$ is function that returns the transitive closure for each $R \in M$.

I need to decide if the function $t$ is injective and/or surjective and prove it. the question is how should I do it. I don't even know where to begin because all examples I saw before was for functions like $f(x) = 2x + 3$, etc...

Thank you.

  • 1
    $t$ is injective iff for all $m_1,m_2\in M$, $m_1\ne m_2\implies t(m_1)\ne t(m_2)$ or, equivalently, iff $t(m_1)=t(m_2)\implies m_1=m_2$. Can more than one relation have the same transitive closure?2012-05-03
  • 1
    Surjective part of the question: Is every relation on $A$ transitive. Injective part of the question: Can you find two relations on $A$ that have the same transitive closure?2012-05-03

2 Answers 2