Prove that the product of two relations is the identity relation if both relations are bijective maps So the question is:
Suppose $R_1$ and $R_2$ are relations on a set $S$ with $R_1\circ R_2 = \operatorname{I}$ and $R_2\circ R_1 = \operatorname{I}$. Prove that both $R_1$ and $R_2$ are bijective maps.
I know that I is the identity relation which means $\operatorname{I} = \{(\alpha,\alpha)|\alpha\in S\}$ and so for $R_1\circ R_2 = \operatorname{I}$ we have to have $\forall x: \exists z: (x,z)\in R_1 \land (z,x)\in R_2$. I also know that maps are functions which means that every object most have only one image, that surjective maps are function where all objects have one image but different objects can have same images, I also know that injective means that all objects have only one image and that different objects have different images, but not all images need to have an object and that a bijective map is when all objects have a different image and all images have a different object (so subjective and injective).
But I have no idea how to use all this information to solve my problem. Can anybody help?
 A: From what you wrote we already know that $\forall x\exists z:(x,z)\in R_1$.
To prove that $R_1$ is a function, assume also $(x,y)\in R_1$ and aim to show $y=z$.
But then $(z,x)\in R_2$ and $(x,y)\in R_1$ implies $(z,y)\in R_2;R_1=I$, that is, $z=y$, as wished.
Now, by symmetry, $R_2$ is also a function, and by the conditions, it is just the inverse of $R_1$, so both must be bijective.
Alternatively, the conditions imply the same for the inverse relations, so we get that the inverse of $R_1$ is also a function, which means that $R_1$ is a bijection.
A: Disclaimer. There is a contradiction between the title of the OP and the body of the OP. The body of the OP asks to prove that if the two ways to compose two relations are both the identity, then the two relations are bijections. The title of the OP asks to prove the converse. I answer the question in the body of the OP.
Also, the title of the OP talks about the product of two relations, but the body of the OP refers to the composition of two relations (the product of two relations is another thing).
I assume that $R_1$ is a binary relations from a set $S$ to a set $T$ (possibly $S = T$), and that $R_2$ is a binary relation from $T$ to $S$.
Notation. $R(x,y)$ is a shorthand for $(x, y) \in R$. The identity relation on a set $S$ is denoted by $I_S$.
I write $R_1;R_2$ for the composition of $R_1$ and $R_2$ (others prefer the notation $R_2 \circ R_1$), that is, for every $x, x' \in S$,
$$R_1 ; R_2 (x,x') \iff \exists y \in T : R_1(x,y) \text{ and } R_2(y,x')
$$

The Proof. As you said, you have to prove the three properties below.

*

*$R_1$ (resp. $R_2$) is a function from $S$ to $T$ (resp. from $T$ to $S$);


*$R_1$ and $R_2$ are injective;


*$R_1$ and $R_2$ are surjective.
Let us show each point. We prove them only for $R_1$, because the proofs for $R_2$ are exactly the same, given the symmetry of the hypothesis.

*

*To prove that $R_1$ is a function from $S$ to $T$, we have to show that, for every $x \in S$, there exists a unique $y \in T$ such that $R_1(x,y)$. Let $x \in S$.

*

*Existence: Since we know that $R_1 ; R_2 = I_S$ and clearly $I_S(x,x)$, we have that there exists $y \in T$  such that $R_1(x,y)$ (and $R_2(y,x)$).


*Uniqueness: Suppose that $R_1(x,y)$ and $R_1(x,y')$ for some $y, y' \in T$.
Since $R_1 ; R_2 = I_S$ and clearly $I_S(x,x)$, there exists $y'' \in T$ such that $R_2(y'',x)$ (and $R_2(x,y'')$).
By composition, from $R_2(y'',x)$ and $R_1(x,y)$ and $R_1(x,y')$, it follows that $R_2;R_1(y'',y)$ and $R_2;R_1(y'',y')$.
Therefore, $y = y'' = y'$ because $R_2 ; R_1 = I_T$ by hypothesis.
Summing up, if $R_1(x,y)$ and $R_1(x,y')$ then $ y = y'$.




*To prove that $R_1$ is injective we have to show that, for every $x , x' \in S$, if $R_1(x,y)$ and $R_1(x',y)$ then $x =x'$. Let $x, x' \in S$ such that $R_1(x,y)$ and $R_1(x',y)$.
Since $R_2;R_1 = I_T$ and clearly $I_T(y,y)$, there exists $x'' \in S$ such that $R_1(x'',y)$ (and $R_2(y,x'')$). By composition, from $R_1(x'',y)$ and $R_2(y,x)$ and $R_2(y,x')$, it follows that $R_1;R_2(x'',x)$ and $R_1;R_2(x'',x')$. Therefore, $x = x'' = x' $ because $R_1;R_2 = I_S$ by hypothesis.
Summing up, if $R_1(x,y)$ and $R_1(x',y)$ then $x = x'$.


*To prove that $R_1$ is surjective, we have to show that, for every $y \in T$, there exists some $x \in S$ such that $R_1(x,y)$.
Let $y \in T$. Since we know that $R_2;R_1 = I_T$ and clearly $I_T(y,y)$, there exists $x \in S$ such that $R_1(x,y)$ (and $R_2(y,x)$).

Comment. In the proof above, there are some redundancies:

*

*the proof of injectivity of $R_1$ is very similar to that one of the uniqueness property when showing that $R_1$ is a function;

*the proof of the surjectivity of $R_1$ is very similar to that one of the existence property when showing that $R_1$ is a function.

In fact, the proof above can be simplified if we first prove that $R_1$ and $R_2$ are both injective and surjective relations, and from that, we can infer that $R_1$ and $R_2$ are injective and surjective functions. This would shorten the proof because it avoids repeating some similar reasoning several times, but it is conceptually slightly more sophisticated. To familiarize yourself with this kind of proof, it is better to start with the demonstration I showed above.
A: The  proof is very basic without no difficulties.
Proof. Since $R_1$ is symmetric to $R_2$, it suffices to show that $R_1$ is a bijective map.

*

*$R_1$ is a function on $S$. Suppose $(x,y),(x,z)\in R_1$. Since $R_2\circ R_1 = \operatorname{I}$, then $(y,x)\in R_2$. And since $(x,z)\in R_1$ then $(y,z)\in R_1\circ R_2 = \operatorname{I}$ which follows that $y=z$. Now we show the domain of $R_1$ is $S$. Suppose $x\in S$, since $R_2\circ R_1 = \operatorname{I}$, then there is some $y\in S$ such that $(x,y)\in R_1$ and $(y,x)\in R_2$ which is as desired.

*$R_1$ is injective. Suppose $(x_0,y_0),(x_1,y_1)\in R_1$ and $y_0=y_1$. Since $R_2\circ R_1 = \operatorname{I}$, then $(y_1,x_1)\in R_2$, and so $(y_0,x_1)\in R_2$. And since $(x_0,y_0)\in R_1$ then $(x_0,x_1)\in R_1\circ R_2 = \operatorname{I}$ which follows that $x_0=x_1$.

*$R_1$ is surjective. Suppose $y\in S$. Since $R_1\circ R_2 = \operatorname{I}$, then there is some $x\in S$ such that $(y,x)\in R_2$ and $(x,y)\in R_1$ which is as desired.

