composition relations in Set Theory

66 Views Asked by At

I have provided my solution and I see there are subtle differences to those provide in picture. Is my solution equivalent? Which is more rigorously correct?

enter image description here

\begin{align} (S \circ R)^{-1} & = \left\{ \left< z, x \right> : \left< z, x \right> \in S \circ R \right\} \\ & = \left\{ \left< z, x \right> : \exists y \in Y s.t. \left< y, z \right> \in S, \left< x, y \right> \in R \right\} \\ &= \left\{ \left< z, x \right> : \exists y \in Y s.t. \left< z, y \right> \in S^{-1}, \left< y, x \right> \in R^{-1} \right\} \\ &= S^{-1} \circ R^{-1} \end{align}

1

There are 1 best solutions below

1
On BEST ANSWER

The typical way to show that two sets are equivalent is to show that each is a subset of the other.

Let $z \times x \in (S \circ R)^{-1} \subseteq Z \times X$ be arbitrary. By definition of the inverse on a relation, this means that $x \times z \in S \circ R \subseteq X \times Z$. This means there is some $y \in Y$ such that $x \times y \in R$ and $y \times z \in S$. If $x \times y \in R$, then $y \times x \in R^{-1} \subseteq Y \times X$; similarly, if $y \times z \in S$, then $z \times y \in S^{-1} \subseteq Z \times Y$. Then $z \times x \in R^{-1} \circ S^{-1}$. This shows $(S \circ R)^{-1} \subseteq R^{-1} \circ S^{-1}$.

Now let $z \times x \in R^{-1} \circ S^{-1}$. This means there is some $y \in Y$ such that $z \times y \in S^{-1} \subseteq Z \times Y$ and $y \times x \subseteq R^{-1} \subseteq Y \times X$. These imply $y \times z \in S$ and $x \times y \in R$. Then $x \times z \in S \circ R$ and so $z \times x \in (S \circ R)^{-1}$. This shows $R^{-1} \circ S^{-1} \subseteq (S \circ R)^{-1}$.