how to prove that function is injective or surjective? 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.
 A: Recall the definitions first.


*

*$t\colon M\to M$ is a function if $t\subseteq M\times M$ such that for every $R\in M$ there is a unique ordered pair $\langle R,R'\rangle\in t$. We often denote $R'$ as $t(R)$.

*A function $t$ is called injective if for every $R,S$ in the domain of $t$ such that $R\neq S$ we have that $t(R)\neq t(S)$.

*A function $t\colon A\to B$ is called surjective if for every $C\in B$ there is at least one $R\in A$ such that $t(A)=B$.


Now when will $t$ be injective? If whenever you are given two different relations their transitive closure is different. Recall that if $R$ is transitive then $t(R)=R$, and so if $S$ is a non-transitive relation we have that $t(S)=t(t(S))$ but $t(S)\neq S$. So in order to find a counterexample for injectivity we need to point out at least one non-transitive relation.
Similarly when will $t$ be surjective? If every relation is a transitive closure of some other relation. Again a non-transitive relation will be a counterexample to this property.
Can you find a non-transitive relation?
A: Hint $\:$ Note $\ t^2 = t,\:$ i.e. $\:t(t(r)) = t(r)\:$ since $\:t(r)\:$ is already transitive. 
Therefore: $\:t\:$ is injective $\iff$ $\: t =  1\iff t\:$ is surjective $\!,\!\:$ viz.


*

*if $\:t\:$ is injective then $\:t(t(r)) = t(r)\:\Rightarrow\: t(r) = r$

*if $\:t\:$ is surjective then $\: r = t(s)\:\Rightarrow\:t(r) = t(t(s)) = t(s) = r$
Remark $\:$ Ditto for any idempotent operator, e.g. any closure operator. 
