Problem with composite relations

Question

The composition $\mathcal{R_2}\circ \mathcal{R_1}$ of the relations $\mathcal{R_1}$ and $\mathcal{R_2}$ is defined as follows:

$\mathcal{R_2}\circ \mathcal{R_1}:=\{(x,z)\ |\exists\ y(x\mathcal{R_1}y\land y\mathcal{R_2}z)\}$.

In particular if $\mathcal{R_1}\subset X\times Y $ and $\mathcal{R_2}\subset Y\times Z$, then $\mathcal{R}=\mathcal{R_2}\circ \mathcal{R_1}\subset X\times Z$, and

$x\mathcal{Rz}:=\exists\ y\ ((y\in Y)\land(x\mathcal{R_1y)\land(y\mathcal{R_2z}))}$.

Let $\Delta_X$ be the diagonal of $X^2$ and $\Delta_Y$ be the diagonal of $Y^2$. Show that if the relations $\mathcal{R_1}\subset X\times Y$ and $\mathcal{R_2}\subset Y\times X$ are such that $(\mathcal{R_2}\circ \mathcal{R_1}=\Delta_X)\land(\mathcal{R_1}\circ \mathcal{R_2}=\Delta_Y)$, then both relations are functional and define mutually inverse mappings of $X$ and $Y$.

My working thus far:

$(x,x)\in \Delta_X\Rightarrow (x,x)\in \mathcal{R_2}\circ \mathcal{R_1}\Rightarrow \mathcal{R_2}\circ \mathcal{R_1}\subset X^2$.

Similarly,

$(y,y)\in \Delta_Y\Rightarrow (y,y)\in \mathcal{R_1}\circ \mathcal{R_2}\Rightarrow \mathcal{R_1}\circ \mathcal{R_2}\subset Y^2$.

This is the furthest I got. I am not sure if I have any errors in my working and how to show that the relations are functional.

Answer 1

Two things need to be established.

1) $\mathcal{R_1}$ and $\mathcal{R_2}$ are functional relationships. This can be done by showing that for every first element in the set of ordered pairs, there is a unique second element.

2) $\mathcal{R_1}$ and $\mathcal{R_2}$ define mutually inverse mappings of $X$ and $Y$. This can be done by showing that both composite relations are identity mappings. This will lead to proving that they are bijective, and hence, mutually inverse.

1) $x_1 \in X \Rightarrow x_1 \Delta_X x_1 \Rightarrow x_1 {\mathcal{R_1} \circ {}\mathcal{R_2} x_1}$.

A/Q, $\mathcal{R_1} \circ \mathcal{R_2}:= \{(x_1,y_1)|\exists y_1(x_1\mathcal{R_1}y_1 \land y_1\mathcal{R_2}x_1)\}$.

This means that there exists at least one unique $y_1$ such that $x_1\mathcal{R_1}y_1 \land y_1\mathcal{R_2}x_1$.

Need to show that $y$s are unique for every $x$. Try to prove by contradiction.

Suppose $\exists x_1\mathcal{R_1}y_2$.

This means

$x_1\mathcal{R_1}y_1 \land x_1\mathcal{R_1}y_2$ [There are two $y$s for some $x$] $\Rightarrow y_1\mathcal{R_2}x_1 \land x_1\mathcal{R_1}y_2 \Rightarrow y_1\mathcal{R_1}\circ \mathcal{R_2}y_2 \Rightarrow y_1\Delta_Y y_2\Rightarrow y_1=y_2$.

This means that for each ordered pair the second elemt for each first element in $\mathcal{R_1}$ is unique. This proves that $\mathcal{R_1}$ is a functional relation.

An analogous argument can be used to prove that $\mathcal{R_2}$ is a functional relation.

2) $x\mathcal{R_1}y$ and $y\mathcal{R_2}x$ are functions.

$x\mathcal{R_1}y:=f_1:X\to Y$.

$y\mathcal{R_2}x:=f_2:Y\to X$.

A/Q, $f_2\circ f_1=e_X$ and $f_1\circ f_2=e_Y$ where $e_X$ and $e_Y$ are identity mappings. i.e., they map the domain to itself.

$X=e_X(X)=(f_2\circ f_1)(X)=f_2(f_1(X))\subset f_2(Y)$.

Therefore, $f_2$ is surjective.

Further, if $x_1\in X$ and $x_2\in X$ then

$x_1\neq x_2\Rightarrow e_X(x_1)\neq e_X(x_2)\Rightarrow (f_2\circ f_1)(x_1)\neq (f_2\circ f_1)(x_2)\Rightarrow f_2(f_1(x_1))\neq f_2(f_1(x_2))\Rightarrow f_1(x_1)\neq f_1(x_2)$

Therefore, $f_1$ is injective.

An analogous argument can be used to show that in the case of $f_1\circ f_1=e_Y$, $f_1$ is surjective and $f_2$ is injective.

This implies that $f_1$ and $f_2$ are mutually inverse mappings.

Answer 2

Let's show that $xR_1y \iff yR_2x$ or in other words, $R_1$ as a subset of $X \times Y$ is just the interchange of the two components of $R_2$ as a subset of $Y \times X$. (You could call $R_1$ and $R_2$ inverse and say $R_1 = R_2^{-1}$ and vice versa).

Note that since $R_1 \circ R_2 = \Delta_Y$, we have that the domain of $R_2$, $\operatorname{dom}(R_2) = Y$ and similary, $R_2 \circ R_1 = \Delta_X$ implies that $\operatorname{dom}(R_1)=X$.

Let $(x,y)\in R_1$. Then $y \in \operatorname{dom}(R_2)$ and hence, for some $z\in X$, $yR_2z$. Thus, $(x,z)\in R_1 \circ R_2$ and $(x,z) \in \Delta_X$, which implies $z=x$, i.e. $(y,x)\in R_2$ and furthermore, $x$ is the only element of $x$ which fulfils this, which implies that $R_2$ is a function and has a trivial multivalued part.

Similarly, we get from $(y,x)\in R_2$ that $(x,y)\in R_1$ and $R_1$ is a function.

Now, since $\operatorname{dom}(R_1)=\operatorname{ran}(R_2)=X$ and $\operatorname{dom}(R_2)=\operatorname{ran}(R_1)=Y$ we have that both relations are surjective.

Furthermore, the argument above shows that $xR_1y$ and $zR_1y$ implies $x=z$, i.e. $R_1$ is injective. Analogously for $R_2$.

Thus, $R_1$ and $R_2$ are biijective functions and their respective inverse.

Answer 3

Interesting to see that this can be also answered in a different way, in which we avoid mentioning elements as far as possible and argue more algebraically.

We are given $\mathcal{R}_1 \subseteq X \times Y$ and that $\mathcal{R}_2 \subseteq Y \times X$. We are also given that $\mathcal{R}_2 \circ \mathcal{R}_1 = \Delta_X$ and $\mathcal{R}_1 \circ \mathcal{R}_2 = \Delta_Y$. From these we have to show that $\mathcal{R}_1$ and $\mathcal{R}_2$ are functional and inverse to each other.

Note that $\mathcal{R}_1$ being functional is equivalent to $$\mathcal{R}_1 \circ \mathcal{R}_1^{-1} \subseteq \Delta_Y.$$ Informally: imagine tracing backwards along $\mathcal{R}_1$ from an element $y \in Y$ to some $x \in X$ and then forwards from $x$ to any $y' \in Y$. Being functional means that whenever we do this we have to have $y = y'$, that is, $(y,y') \in \Delta_Y$.

Similarly, $\mathcal{R}_2$ being functional is equivalent to $$\mathcal{R}_2 \circ \mathcal{R}_2^{-1} \subseteq \Delta_X.$$ We also need to know that the diagonal is the identity relation for composition, so that $$\Delta_Y \circ \mathcal{R}_1 \circ \Delta_X = \mathcal{R}_1, \text{ and } \Delta_X \circ \mathcal{R}_2 \circ \Delta_Y = \mathcal{R}_2.$$ We do need this property which holds for an arbitrary relation $\mathcal{R}$: $$\mathcal{R} \subseteq \mathcal{R} \circ \mathcal{R}^{-1} \circ \mathcal{R}.$$ Now, everything falls out very neatly: $$\begin{array}{rcl} \mathcal{R}_1 \subseteq \mathcal{R}_1 \circ \mathcal{R}_1^{-1} \circ \mathcal{R}_1 & \Rightarrow & \mathcal{R}_1 \circ \mathcal{R}_2 \subseteq \mathcal{R}_1 \circ \mathcal{R}_1^{-1} \circ \mathcal{R}_1 \circ \mathcal{R}_2\\ & \Rightarrow & \Delta_Y \subseteq \mathcal{R}_1 \circ \mathcal{R}_1^{-1} \circ \Delta_Y \\ & \Rightarrow & \mathcal{R}_2 \circ \Delta_Y \subseteq \mathcal{R}_2 \circ \mathcal{R}_1 \circ \mathcal{R}_1^{-1} \\ & \Rightarrow & \mathcal{R}_2 \subseteq \Delta_X \circ \mathcal{R}_1^{-1} \\ & \Rightarrow & \mathcal{R}_2 \subseteq \mathcal{R}_1^{-1} \end{array}$$ For exactly the same reason $\mathcal{R}_1 \subseteq \mathcal{R}_2^{-1}$, so taking inverses of the relations, $\mathcal{R}_1^{-1} \subseteq \mathcal{R}_2$ and hence (using the fact that $\mathcal{R}_2 \subseteq \mathcal{R}_1^{-1}$) we get $\mathcal{R}_2 = \mathcal{R}_1^{-1}$ and $\mathcal{R}_1 = \mathcal{R}_2^{-1}$.

The property of being functional can be justified explicitly by noting: $$\mathcal{R}_1 \circ \mathcal{R}_1^{-1} = \mathcal{R}_1 \circ \mathcal{R}_2 = \Delta_Y, \text{ and } \mathcal{R}_2 \circ \mathcal{R}_2^{-1} = \mathcal{R}_2 \circ \mathcal{R}_1 = \Delta_X.$$