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$.

Proof

This has to be rewritten. In particular: In light of the more relaxed definition of composite of relation You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by doing so. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Rewrite}} from the code.

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\)

Definition of Composition of Relations

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

\(\ds \tuple {c, b}\)

\(\in\)

\(\ds \RR^{-1}\)

\(\ds \leadsto \ \ \)

\(\ds \exists c \in T: \, \)

\(\ds \tuple {b, c}\)

\(\in\)

\(\ds \RR\)

Definition of Inverse Relation

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

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

\(\in\)

\(\ds \RR^{-1}\)

\(\ds \leadsto \ \ \)

\(\ds \tuple {b, a}\)

\(\in\)

\(\ds \RR^{-1} \circ \RR\)

Definition of Composition of Relations

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.

The domain of $\RR^{-1} \circ \RR$ is $S$ from Domain of Composite Relation, as is its codomain from Codomain of Composite Relation and the definition of Inverse Relation.

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

This completes the proof.

$\blacksquare$