Condition for Composite Relation with Inverse to be Identity

From ProofWiki
Jump to navigation Jump to search

Theorem

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

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

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


Then:

$\RR \circ \RR^{-1} = I_T$

if and only if:

$\RR$ is many-to-one

and:

$\RR$ is right-total.


Example

CompositeWithInverseIdentity.png

Note in the above that:

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

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


Proof

Sufficient Condition

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


Aiming for a contradiction, suppose:

$\exists t \in T: t \notin \Img \RR$

Then:

$t \notin \Img {\RR \circ \RR^{-1} }$

But:

$t \in \Img {I_T}$

by definition of the identity mapping on $T$.

Hence:

$\RR \circ \RR^{-1} \ne I_T$

From this contradiction we deduce that:

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

where $T \setminus \Img \RR$ denotes set difference.

So from Set Difference with Superset is Empty Set‎:

$T \subseteq \Img \RR$

But from Image is Subset of Codomain we have:

$T \supseteq \Img \RR$

and so:

$\Img \RR = T$

which means $\RR$ is right-total.

$\Box$


Suppose $\RR$ 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 \RR \land \tuple {s, t_2} \in \RR$

By definition of inverse relation:

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

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

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


Thus:

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

So, by definition of identity mapping:

$\RR \circ \RR^{-1} \ne I_T$

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

$\Box$


So it has been demonstrated that if:

$\RR \circ \RR^{-1} = I_T$

then:

$\RR$ is many-to-one

and

$\RR$ is right-total.

$\Box$


Necessary Condition

Let:

$\RR$ be many-to-one

and

$\RR$ be right-total.


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

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

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

By definition of inverse:

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

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

$t_1 = t_2$

So:

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

and so:

$\RR \circ \RR^{-1} \subseteq I_T$


Now let $t \in T$.

By definition of identity mapping on $T$:

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

As $\RR$ is right-total:

$\Img \RR = T$

and so:

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

and so:

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

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

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

So:

$\RR \circ \RR^{-1} \supseteq I_T$

and so:

$\RR \circ \RR^{-1} = I_T$

$\Box$


Hence the result.

$\blacksquare$


Sources