Relation is surjective iff $I_V=R^T \circ R$

Question

There is a relation $R$ from $U$ to $V$ for which it is given that it is a function.

How can I prove that $R$ is surjective iff $I_V=R^T \circ R$

Can anyone provide me a hint to solve this problem.

Answer 1

Hint:

Let $|U|=n$ and $|V|=m$. Then $R: U \longrightarrow V$ can be represented by a binary $n \times m$ matrix $R=[r_{ij}]$. We are assuming that rows correspond to elements of $U$ and columns correspond to elements of $V$ and $r_{ij}=1$ if element $i \in U$ is related to element $j \in V$ via $R$, otherwise $r_{ij}=0$.

Since $R$ is given to be a function, therefore every row of matrix $R$ will have exactly one $1$.

Suppose $R^TR = I_U$ (note: I think you made a typo with $I_V$). Then this means $r$ cannot have a zero column (same as saying $R^T$ cannot have a zero row). In other words, each row of $R$ has exactly one $1$ (from our previous assertion that $R$ is a function) and now each column also has to have at least one $1$. This shows that $R$ must be surjective. Now try the other implication.

Answer 2

In this answer it is preassumed that the composition of relations is defined as follows:$$\langle x,y\rangle\in S\circ R\iff\exists z\left[\langle x,z\rangle\in R\wedge\langle z,y\rangle\in S\right]$$

First check whether this agrees with your definition.

I suspect that it must be shown that $R\circ R^{T}=I_{V}$ iff $R$ is a surjective function.

We have:

$$\langle x,y\rangle\in R\circ R^{T}\iff\exists z\left[\langle x,z\rangle\in R^{T}\wedge\langle z,y\rangle\in R\right]\iff\exists z\left[\langle z,x\rangle\in R\wedge\langle z,y\rangle\in R\right]$$

So applying that $R$ is a function we find $x=R\left(z\right)=y$. Proved is now that $R\circ R^{T}\subseteq I_{V}$.

If $v\in V$ then the surjectivity of $R$ assures us that $\exists z\left[\langle z,v\rangle\in R\right]$ wich leads conversely (from right to left) to $\langle v,v\rangle\in R\circ R^{T}$. This shows that $I_V\subseteq R\circ R^{T}$.