2
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ Your title asks for $A\to B$ but the question asks for $B\to A$. I think you must have a typo in your quantifiers, surely both are not tied to $x$? I also think your explanation of what $R_1;R_2=I$ means is wrong. I think you need to sort all this out first. $\endgroup$ Sep 18 '21 at 9:53
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

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

  2. $R_1$ and $R_2$ are injective;

  3. $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.

  1. 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'$.

  2. 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'$.

  3. 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:

  1. 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;
  2. 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.

$\endgroup$
4
  • $\begingroup$ Note that $R_1,R_2$ are relations on $S$, and so no such a different $T$. Therefore the answer is too redundant. $\endgroup$
    – M. Logic
    Sep 18 '21 at 14:21
  • $\begingroup$ Can I ask the reason for the downvote? The fact that I prove the property in a slightly more general context it is not a mistake. $\endgroup$ Sep 18 '21 at 14:25
  • $\begingroup$ But it's not neat. Beginners should write the proof as neat as possible. $\endgroup$
    – M. Logic
    Sep 18 '21 at 14:30
  • 1
    $\begingroup$ @M.Logic - In my opinion, a proof that shows that an hypothesis is superfluous is neater than a proof that uses that hypothesis with no need, and without explaining its use. Anyway, I never downvote an answer only because I don't like its style. Everyone has his or her own style and I respect it. $\endgroup$ Sep 18 '21 at 14:47
-2
$\begingroup$

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.
$\endgroup$
10
  • $\begingroup$ Pay attention! In the proof that $R_1$ is a function, from the fact that $(x,y) \in R_1$ and $R_2 \circ R_1= I$ does not follow immediately that $(y,x) \in R_2$. $\endgroup$ Sep 18 '21 at 13:57
  • $\begingroup$ @Taroccoesbrocco It must be since $\operatorname{I}$ is the identy relation on $S$. $\endgroup$
    – M. Logic
    Sep 18 '21 at 14:00
  • $\begingroup$ Since $R_1$ and $R_2$ are relations (a priori they are not functions), from the fact that $(x,y) \in R_1$ and $R_2 \circ R_1 = I $ you can only deduce that $(x,y') \in R_1$ and $(y',x) \in R_2$ for some $y'$, but a priori it might be $y \neq y'$. For instance, $R_2$ might be not defined in $y$. $\endgroup$ Sep 18 '21 at 14:06
  • 1
    $\begingroup$ I agree that the OP assumes $S = T$, but still from the fact that $(x,y) \in R_1$ and $R_2∘R_1=I$ does not follow immediately that $(y,x)\in R_2$. This is an inference that should be explained in a proof. Unless the proof amounts to say that a property holds because it holds. Actually, it is by explaining this inference that it is evident that the hypothesis $S = T$ is superfluous. $\endgroup$ Sep 18 '21 at 14:42
  • 1
    $\begingroup$ The current proof that $R_1$ is a function only shows that $R_1$ is functorial (if $(x,y) \in R_1$ and $(x,z) \in R_1$ then $y =z$), but it should also show that $R_1$ is total, i.e., for any $x \in S$ there is an $y \in S$ such that $(x,y) \in R_1$. $\endgroup$ Sep 18 '21 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.