Many-to-One Relation Composite with Inverse is Transitive

From ProofWiki
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$