Theorem: Many-to-One Relation Composite with Inverse is Transitive

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$.
{{begin-eqn}}
{{eqn | o = 
      | r = \tuple {a, b}, \tuple {b, c} \in \RR^{-1} \circ \RR
      | c = 
}}
{{eqn | ll= \leadsto
      | o = 
      | r = \exists p \in T: \tuple {a, p} \in \RR \land \tuple {p, b} \in \RR^{-1}
      | c = 
}}
{{eqn | lo= \land
      | o = 
      | r = \exists q \in T: \tuple {b, q} \in \RR \land \tuple {q, c} \in \RR^{-1}
      | c = {{Defof|Composition of Relations}}
}}
{{eqn | ll= \leadsto
      | o = 
      | r = \tuple {b, p} \in \RR \land \tuple {p, a} \in \RR^{-1}
      | c = 
}}
{{eqn | lo= \land
      | o = 
      | r = \tuple {c, q} \in \RR \land \tuple {q, b} \in \RR^{-1}
      | c = {{Defof|Inverse Relation}}
}}
{{eqn | ll= \leadsto
      | o = 
      | r = \tuple {c, p} \in \RR \land \tuple {p, b} \in \RR^{-1}
      | c = as $\RR$ is many-to-one
}}
{{eqn | ll= \leadsto
      | o = 
      | r = \tuple {a, p} \in \RR \land \tuple {p, c} \in \RR^{-1}
      | c = 
}}
{{eqn | ll= \leadsto
      | o = 
      | r = \tuple {a, c} \in \RR
      | c = {{Defof|Composition of Relations}}
}}
{{end-eqn}}
Thus $\RR^{-1} \circ \RR$ is transitive.
Now let $\tuple {p, q}, \tuple {q, r} \in \RR \circ \RR^{-1}$.
{{begin-eqn}}
{{eqn | o = 
      | r = \tuple {p, q}, \tuple {q, r} \in \RR \circ \RR^{-1}
      | c = 
}}
{{eqn | ll= \leadsto
      | o = 
      | r = \exists a \in S: \tuple {p, a} \in \RR^{-1} \land \tuple {a, q} \in \RR
      | c = 
}}
{{eqn | lo= \land
      | o = 
      | r = \exists b \in S: \tuple {q, b} \in \RR^{-1} \land \tuple {b, r} \in \RR
      | c = {{Defof|Composition of Relations}}
}}
{{eqn | ll= \leadsto
      | o = 
      | r = \tuple {a, p} \in \RR \land \tuple {q, a} \in \RR^{-1}
      | c = 
}}
{{eqn | lo= \land
      | o = 
      | r = \tuple {b, q} \in \RR \land \tuple {r, b} \in \RR^{-1}
      | c = {{Defof|Inverse Relation}}
}}
{{end-eqn}}
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:
{{begin-eqn}}
{{eqn | l = \tuple {a, p} \in \RR \land \tuple {a, q} \in \RR
      | o = \leadsto
      | r = p = q
      | c = as $\RR$ is many-to-one
}}
{{eqn | l = \tuple {b, q} \in \RR \land \tuple {b, r} \in \RR
      | o = \leadsto
      | r = q = r
      | c = as $\RR$ is many-to-one
}}
{{eqn | o = \leadsto
      | r = p = q = r
      | c = 
}}
{{eqn | o = \leadsto
      | r = \tuple {p, r} \in \RR \circ \RR^{-1}
      | c = 
}}
{{end-eqn}}
Thus (trivially) $\RR \circ \RR^{-1}$ is transitive.
{{qed}}
Category:Composite Relations
Category:Transitive Relations
gg0tee6jx7tzu45wwivrldszc583aaf