# Many-to-One Relation Composite with Inverse is Transitive

Jump to: navigation, search

## Theorem

Let $\mathcal R \subseteq S \times T$ be a relation which is many-to-one.

Then the composites (both ways) of $\mathcal R$ and its inverse $\mathcal R^{-1}$, that is, both $\mathcal R^{-1} \circ \mathcal R$ and $\mathcal R \circ \mathcal R^{-1}$, are transitive.

## Proof

Let $\mathcal R \subseteq S \times T$ be many-to-one.

Then, from the definition of many-to-one:

$\mathcal R \subseteq S \times T: \forall x \in S: \left({x, y_1}\right) \in \mathcal R \land \left({x, y_2}\right) \in \mathcal R \implies y_1 = y_2$

Also, note that from Inverse of Many-to-One Relation is One-to-Many, $\mathcal R^{-1}$ is one-to-many.

Let $\left({a, b}\right), \left({b, c}\right) \in \mathcal R^{-1} \circ \mathcal R$.

 $\displaystyle$  $\displaystyle \left({a, b}\right), \left({b, c}\right) \in \mathcal R^{-1} \circ \mathcal R$ $\displaystyle \implies \ \$ $\displaystyle$  $\displaystyle \exists p \in T: \left({a, p}\right) \in \mathcal R \land \left({p, b}\right) \in \mathcal R^{-1}$ $\displaystyle$ $\land$ $\displaystyle \exists q \in T: \left({b, q}\right) \in \mathcal R \land \left({q, c}\right) \in \mathcal R^{-1}$ Definition of Composite Relation $\displaystyle \implies \ \$ $\displaystyle$  $\displaystyle \left({b, p}\right) \in \mathcal R \land \left({p, a}\right) \in \mathcal R^{-1}$ $\displaystyle$ $\land$ $\displaystyle \left({c, q}\right) \in \mathcal R \land \left({q, b}\right) \in \mathcal R^{-1}$ Definition of Inverse Relation $\displaystyle \implies \ \$ $\displaystyle$  $\displaystyle \left({c, p}\right) \in \mathcal R \land \left({p, b}\right) \in \mathcal R^{-1}$ as $\mathcal R$ is many-to-one $\displaystyle \implies \ \$ $\displaystyle$  $\displaystyle \left({a, p}\right) \in \mathcal R \land \left({p, c}\right) \in \mathcal R^{-1}$ $\displaystyle \implies \ \$ $\displaystyle$  $\displaystyle \left({a, c}\right) \in \mathcal R$ Definition of Composite Relation

Thus $\mathcal R^{-1} \circ \mathcal R$ is transitive.

Now let $\left({p, q}\right), \left({q, r}\right) \in \mathcal R \circ \mathcal R^{-1}$.

 $\displaystyle$  $\displaystyle \left({p, q}\right), \left({q, r}\right) \in \mathcal R \circ \mathcal R^{-1}$ $\displaystyle \implies \ \$ $\displaystyle$  $\displaystyle \exists a \in S: \left({p, a}\right) \in \mathcal R^{-1} \land \left({a, q}\right) \in \mathcal R$ $\displaystyle$ $\land$ $\displaystyle \exists b \in S: \left({q, b}\right) \in \mathcal R^{-1} \land \left({b, r}\right) \in \mathcal R$ Definition of Composite Relation $\displaystyle \implies \ \$ $\displaystyle$  $\displaystyle \left({a, p}\right) \in \mathcal R \land \left({q, a}\right) \in \mathcal R^{-1}$ $\displaystyle$ $\land$ $\displaystyle \left({b, q}\right) \in \mathcal R \land \left({r, b}\right) \in \mathcal R^{-1}$ Definition of Inverse Relation

But $\mathcal R$ is many-to-one.

This means that

$\forall x \in S: \left({x, y_1}\right) \in \mathcal R \land \left({x, y_2}\right) \in \mathcal R \implies y_1 = y_2$

So:

 $\displaystyle \left({a, p}\right) \in \mathcal R \land \left({a, q}\right) \in \mathcal R$ $\implies$ $\displaystyle p = q$ as $\mathcal R$ is many-to-one $\displaystyle \left({b, q}\right) \in \mathcal R \land \left({b, r}\right) \in \mathcal R$ $\implies$ $\displaystyle q = r$ as $\mathcal R$ is many-to-one $\displaystyle$ $\implies$ $\displaystyle p = q = r$ $\displaystyle$ $\implies$ $\displaystyle \left({p, r}\right) \in \mathcal R \circ \mathcal R^{-1}$

Thus (trivially) $\mathcal R \circ \mathcal R^{-1}$ is transitive.

$\blacksquare$