how to prove that function is injective or surjective?

Question

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.

Answer 1

Recall the definitions first.

1. $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)$.
2. 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)$.
3. 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?

Answer 2

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.