Composition of Relation with Inverse is Symmetric

Theorem

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

Then the composition of $\RR$ with its inverse $\RR^{-1}$ is symmetric:

$(1): \quad \RR^{-1} \circ \RR$ is a symmetric relation on $S$

$(2): \quad \RR \circ \RR^{-1}$ is a symmetric relation on $T$.

Note that this result holds for any $\RR \subseteq S \times T$, and does not require that $\struct {S, \RR}$ necessarily be a relational structure.

$\ds \tuple {a, b}$

$\in$

$\ds \RR^{-1} \circ \RR$

$\ds \leadsto \ \ $

$\ds \exists c \in T: \, $

$\ds \tuple {a, c}$

$\in$

$\ds \RR$

$\, \ds \land \, $

$\ds \tuple {c, b}$

$\in$

$\ds \RR^{-1}$

$\ds \leadsto \ \ $

$\ds \exists c \in T: \, $

$\ds \tuple {b, c}$

$\in$

$\ds \RR$

$\, \ds \land \, $

$\ds \tuple {c, a}$

$\in$

$\ds \RR^{-1}$

$\ds \leadsto \ \ $

$\ds \tuple {b, a}$

$\in$

$\ds \RR^{-1} \circ \RR$

Thus $\tuple {a, b} \in \RR^{-1} \circ \RR \implies \tuple {b, a} \in \RR^{-1} \circ \RR$ and thus $\RR^{-1} \circ \RR$ is symmetric.

As $\RR = \paren {\RR^{-1} }^{-1}$ from Inverse of Inverse Relation, it follows that $\RR \circ \RR^{-1} = \paren {\RR^{-1} }^{-1} \circ \RR^{-1}$ is likewise a symmetric relation.

Similarly, the codomain of $\RR \circ \RR^{-1}$ is $T$, as is its domain.

This completes the proof.

$\blacksquare$