Many-to-One Relation Composite with Inverse is Transitive

Theorem

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

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

Proof

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

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

$\RR \subseteq S \times T: \forall x \in S: \tuple {x, y_1} \in \RR \land \tuple {x, y_2} \in \RR \implies y_1 = y_2$

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

Let $\tuple {a, b}, \tuple {b, c} \in \RR^{-1} \circ \RR$.

\(\ds \)

\(\)

\(\ds \tuple {a, b}, \tuple {b, c} \in \RR^{-1} \circ \RR\)

\(\ds \leadsto \ \ \)

\(\ds \)

\(\)

\(\ds \exists p \in T: \tuple {a, p} \in \RR \land \tuple {p, b} \in \RR^{-1}\)

\(\, \ds \land \, \)

\(\ds \)

\(\)

\(\ds \exists q \in T: \tuple {b, q} \in \RR \land \tuple {q, c} \in \RR^{-1}\)

Definition of Composition of Relations

\(\ds \leadsto \ \ \)

\(\ds \)

\(\)

\(\ds \tuple {b, p} \in \RR \land \tuple {p, a} \in \RR^{-1}\)

\(\, \ds \land \, \)

\(\ds \)

\(\)

\(\ds \tuple {c, q} \in \RR \land \tuple {q, b} \in \RR^{-1}\)

Definition of Inverse Relation

\(\ds \leadsto \ \ \)

\(\ds \)

\(\)

\(\ds \tuple {c, p} \in \RR \land \tuple {p, b} \in \RR^{-1}\)

as $\RR$ is many-to-one

\(\ds \leadsto \ \ \)

\(\ds \)

\(\)

\(\ds \tuple {a, p} \in \RR \land \tuple {p, c} \in \RR^{-1}\)

\(\ds \leadsto \ \ \)

\(\ds \)

\(\)

\(\ds \tuple {a, c} \in \RR\)

Definition of Composition of Relations

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

Now let $\tuple {p, q}, \tuple {q, r} \in \RR \circ \RR^{-1}$.

\(\ds \)

\(\)

\(\ds \tuple {p, q}, \tuple {q, r} \in \RR \circ \RR^{-1}\)

\(\ds \leadsto \ \ \)

\(\ds \)

\(\)

\(\ds \exists a \in S: \tuple {p, a} \in \RR^{-1} \land \tuple {a, q} \in \RR\)

\(\, \ds \land \, \)

\(\ds \)

\(\)

\(\ds \exists b \in S: \tuple {q, b} \in \RR^{-1} \land \tuple {b, r} \in \RR\)

Definition of Composition of Relations

\(\ds \leadsto \ \ \)

\(\ds \)

\(\)

\(\ds \tuple {a, p} \in \RR \land \tuple {q, a} \in \RR^{-1}\)

\(\, \ds \land \, \)

\(\ds \)

\(\)

\(\ds \tuple {b, q} \in \RR \land \tuple {r, b} \in \RR^{-1}\)

Definition of Inverse Relation

But $\RR$ is many-to-one.

This means that:

$\forall x \in S: \tuple {x, y_1} \in \RR \land \tuple {x, y_2} \in \RR \implies y_1 = y_2$

So:

\(\ds \tuple {a, p} \in \RR \land \tuple {a, q} \in \RR\)

\(\leadsto\)

\(\ds p = q\)

as $\RR$ is many-to-one

\(\ds \tuple {b, q} \in \RR \land \tuple {b, r} \in \RR\)

\(\leadsto\)

\(\ds q = r\)

as $\RR$ is many-to-one

\(\ds \)

\(\leadsto\)

\(\ds p = q = r\)

\(\ds \)

\(\leadsto\)

\(\ds \tuple {p, r} \in \RR \circ \RR^{-1}\)

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

$\blacksquare$