Composition of relations. Both relations are functional and mutually inverse mappings. Zorich - MAI p22

550 Views Asked by At

$\def\R{\mathcal{R}}$

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 \wedge y \mathcal{R}_2 z\}$$ Let $\Delta_X$ be the diagonal of $X^2$ and $\Delta_Y$ 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)\wedge(\mathcal{R}_1 \circ \mathcal{R}_2 = \Delta_Y)$, then both relations are functional and define mutually inverse mappings of $X$ and $Y$.

I will try to solve this below, but first I must note, this is from Zorich - Mathematical Analysis I, page 22, Exercise 1.3.5, Q1a). Furthermore, I do not condone such long questions.


My attempt:

What does it mean for a relation to be functional?

$$(x \R y_1) \wedge (x \R y_2 ) \implies ( y_1 = y_2)$$

This qualifies the relation as a function.

What does it mean for two relations to define mutually inverse mappings of $X$ and $Y$.

Since the relations are functions(if the above does hold), then to satisfy this we need:

$$f:X\to Y, G: Y\to X \text{ to have: }$$ $$g \circ f = e_X, f \circ g = e_Y$$

Where $e_X$ and $e_Y$ are the identity mappings on $X$ and $Y$ respectively.

1

There are 1 best solutions below

1
On

To show that $ \mathcal{R}_1$ is a functional relation, we could proceed as follows.

\begin{eqnarray*} x_1 \in X &\implies& (x_1, x_1) \in \Delta_X \\ &\implies& (x_1, x_1) \in \mathcal{R}_2 \circ \mathcal{R}_1 \end{eqnarray*}

It follows from the earlier stated definition of $ \mathcal{R}_2 \circ \mathcal{R}_1$ and the above that there exists at least one $y_1$, such that: \begin{equation*} (x_1, y_1) \in \mathcal{R}_1 \wedge (y_1, x_1) \in \mathcal{R}_2 \end{equation*}

Now suppose that: \begin{equation*} \exists (x_1, y_2) \in \mathcal{R}_1 \end{equation*}

From the two statements above, we can begin to reason as follows: \begin{eqnarray*} (x_1, y_1) \in \mathcal{R}_1 \wedge (x_1, y_2) \in \mathcal{R}_1 &\implies& (y_1, x_1) \in \mathcal{R}_2 \wedge (x_1, y_2) \in \mathcal{R}_1 \\ &\implies& (y_1, y_2) \in \mathcal{R}_1 \circ \mathcal{R}_2 \\ &\implies& (y_1, y_2) \in \Delta_Y \\ &\implies& y_1 = y_2 \end{eqnarray*}

This proves that $ \mathcal{R}_1 $ is a functional relation. An exactly analogous argument can be used to prove that $ \mathcal{R}_2 $ is also a functional relation.

To prove that the two relations define mutually inverse mappings of $X$ and $Y$:

From the above proof of $\mathcal{R}_1$ being a functional relationship, we have the following result:

\begin{equation*} \forall x \in X \; \exists! \, y \in Y, \mbox{ such that } (x,y) \in \mathcal{R}_1 \end{equation*}

From the analogous results that prove $\mathcal{R}_2$ is a functional relation, we can similarly deduce that: \begin{equation*} \forall y \in Y \; \exists! \, x \in X, \mbox{ such that } (y,x) \in \mathcal{R}_2 \end{equation*}

It follows from the above two results that $\mathcal{R}_1$ and $\mathcal{R}_2$ define mutually inverse mappings of $X$ and $Y$.