Inverse of Composite Relation

Theorem

Let $\mathcal R_2 \circ \mathcal R_1 \subseteq S_1 \times S_3$ be the composite of the two relations $\mathcal R_1 \subseteq S_1 \times S_2$ and $\mathcal R_2 \subseteq S_2 \times S_3$.

Then:

$\left({\mathcal R_2 \circ \mathcal R_1}\right)^{-1} = \mathcal R_1^{-1} \circ \mathcal R_2^{-1}$

Proof

Let $\mathcal R_1 \subseteq S_1 \times S_2$ and $\mathcal R_2 \subseteq S_2 \times S_3$ be relations.

We assume that:

$\operatorname{Dom} \left({\mathcal R_2}\right) = \operatorname{Cdm} \left({\mathcal R_1}\right)$

where $\operatorname{Dom}$ denotes domain and $\operatorname{Cdm}$ denotes codomain.

This is necessary for $\mathcal R_2 \circ \mathcal R_1$ to exist.

From the definition of an inverse relation, we have:

• $\operatorname{Dom} \left({\mathcal R_2}\right) = \operatorname{Cdm} \left({\mathcal R_2^{-1}}\right)$
• $\operatorname{Cdm} \left({\mathcal R_1}\right) = \operatorname{Dom} \left({\mathcal R_1^{-1}}\right)$

So we confirm that $\mathcal R_1^{-1} \circ \mathcal R_2^{-1}$ is defined.

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \mathcal R_2 \circ \mathcal R_1\)	\(=\)	\(\displaystyle \left\{ {\left({x, z}\right): x \in S_1, z \in S_3: \exists y \in S_2: \left({x, y}\right) \in \mathcal R_1 \land \left({y, z}\right) \in \mathcal R_2}\right\}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Composite
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \left({\mathcal R_2 \circ \mathcal R_1}\right)^{-1}\)	\(=\)	\(\displaystyle \left\{ {\left({z, x}\right): \left({x, z}\right) \in \mathcal R_2 \circ \mathcal R_1}\right\}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Inverse Relation
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left\{ {\left({z, x}\right): x \in S_1, z \in S_3: \exists y \in S_2: \left({x, y}\right) \in \mathcal R_1 \land \left({y, z}\right) \in \mathcal R_2}\right\}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Composite
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left\{ {\left({z, x}\right): z \in S_3, x \in S_1: \exists y \in S_2: \left({z, y}\right) \in \mathcal R_2^{-1} \land \left({y, x}\right) \in \mathcal R_1^{-1} }\right\}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Inverse Relation
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \mathcal R_1^{-1} \circ \mathcal R_2^{-1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Composite

$\blacksquare$

Sources

• Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 10$: Inverses and Composites
• Seth Warner: Modern Algebra (1965)... (previous)... (next): Exercise $5.8 \ \text{(c)}$
• George McCarty: Topology: An Introduction with Application to Topological Groups (1967): $\text{I}$: Problem $\text{AA}$