Condition for Composite Relation with Inverse to be Identity

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\mathcal R \subseteq S \times T$ be a relation on $S \times T$.

Let $\mathcal R \circ \mathcal R^{-1}$ be the composite of $\mathcal R$ with its inverse.

Let $I_T$ be the identity mapping on $T$.


Then:

$\mathcal R \circ \mathcal R^{-1} = I_T$

if and only if:

$\mathcal R$ is many-to-one

and:

$\mathcal R$ is right-total.


Example

CompositeWithInverseIdentity.png

Note in the above that:

$\mathcal R$ is many-to-one
$\mathcal R$ is right-total
$\mathcal R \circ \mathcal R^{-1} = I_T$.

Note, however, that $\mathcal R^{-1}$ is neither many-to-one nor right-total, and does not need to be for $\mathcal R \circ \mathcal R^{-1} = I_T$.


Proof

Sufficient Condition

Let $\mathcal R \circ \mathcal R^{-1} = I_T$.


Aiming for a contradiction, suppose:

$\exists t \in T: t \notin \Img {\mathcal R}$

Then:

$t \notin \Img {\mathcal R \circ \mathcal R^{-1} }$

But:

$t \in \Img {I_T}$

by definition of the identity mapping on $T$.

Hence:

$\mathcal R \circ \mathcal R^{-1} \ne I_T$

From this contradiction we deduce that:

$\mathcal R \circ \mathcal R^{-1} = I_T \implies T \setminus \Img {\mathcal R} = \O$

where $T \setminus \Img {\mathcal R}$ denotes set difference.

So from Set Difference with Superset is Empty Set‎:

$T \subseteq \Img {\mathcal R}$

But from Image is Subset of Codomain we have:

$T \supseteq \Img {\mathcal R}$

and so:

$\Img {\mathcal R} = T$

which means $\mathcal R$ is right-total.

$\Box$


Suppose $\mathcal R$ is not many-to-one.

Then:

$\exists s \in S: \exists t_1, t_2 \in T, t_1 \ne t_2: \tuple {s, t_1} \in \mathcal R \land \tuple {s, t_2} \in \mathcal R$

By definition of inverse relation:

$\exists s \in S: \exists t_1, t_2 \in T: \tuple {t_1, s} \in \mathcal R^{-1} \land \tuple {t_2, s} \in \mathcal R^{-1}$

The composite of $\mathcal R^{-1}$ and $\mathcal R$ is defined as:

$\mathcal R \circ \mathcal R^{-1} = \set {\tuple {x, z} \in T \times T: \exists y \in S: \tuple {x, y} \in \mathcal R^{-1} \land \tuple {y, z} \in \mathcal R}$


Thus:

\(\displaystyle \tuple {t_1, s}\) \(\in\) \(\displaystyle \mathcal R^{-1}\)
\(\displaystyle \tuple {s, t_2}\) \(\in\) \(\displaystyle \mathcal R\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \tuple {t_1, t_2}\) \(\in\) \(\displaystyle \mathcal R \circ \mathcal R^{-1}\) where $t_1 \ne t_2$ (from above)

So, by definition of identity mapping:

$\mathcal R \circ \mathcal R^{-1} \ne I_T$

From this contradiction we deduce that $\mathcal R$ must be many-to-one.

$\Box$


So it has been demonstrated that if:

$\mathcal R \circ \mathcal R^{-1} = I_T$

then:

$\mathcal R$ is many-to-one

and

$\mathcal R$ is right-total.

$\Box$


Necessary Condition

Let:

$\mathcal R$ be many-to-one

and

$\mathcal R$ be right-total.


Let $\tuple {t_1, t_2} \in \mathcal R \circ \mathcal R^{-1}$.

The composite of $\mathcal R^{-1}$ and $\mathcal R$ is defined as:

$\mathcal R \circ \mathcal R^{-1} = \set {\tuple {t_1, t_2} \in T \times T: \exists s \in S: \tuple {t_1, s} \in \mathcal R^{-1} \land \tuple {s, t_2} \in \mathcal R}$

By definition of inverse:

$\mathcal R \circ \mathcal R^{-1} = \set {\tuple {t_1, t_2} \in T \times T: \exists s \in S: \tuple {s, t_1} \in \mathcal R \land \tuple {s, t_2} \in \mathcal R}$

But $\mathcal R$ is many-to-one, and so:

$t_1 = t_2$

So:

$\forall \tuple {t_1, t_2} \in \mathcal R \circ \mathcal R^{-1}: t_1 = t_2$

and so:

$\mathcal R \circ \mathcal R^{-1} \subseteq I_T$


Now let $t \in T$.

By definition of identity mapping on $T$:

$\tuple {t, t} \in I_T$

As $\mathcal R$ is right-total:

$\Img {\mathcal R} = T$

and so:

$\exists s \in S: \tuple {s, t} \in \mathcal R$

and so:

$\exists s \in S: \tuple {t, s} \in \mathcal R^{-1}$

Hence by definition of the composite of $\mathcal R^{-1}$ and $\mathcal R$:

$\tuple {t, t} \in \mathcal R \circ \mathcal R^{-1}$

So:

$\mathcal R \circ \mathcal R^{-1} \supseteq I_T$

and so:

$\mathcal R \circ \mathcal R^{-1} = I_T$

$\Box$


Hence the result.

$\blacksquare$


Sources