Associativity of compositions of relations

Question

Prove that given relations

$R_1 \subseteq A \times B$, $R_2 \subseteq B \times C$, $R_3 \subseteq C \times D$

then

$(R_1 \circ R_2) \circ R_3 = R_1 \circ (R_2 \circ R_3)$

I don't know where exactly to start? What does it mean for something to be in $(R_1 \circ R_2) \circ R_3$?

Here is what I know.

I know that I have to show that $(R_1 \circ R_2) \circ R_3 \subseteq R_1 \circ (R_2 \circ R_3)$ and $R_1 \circ (R_2 \circ R_3) \subseteq (R_1 \circ R_2) \circ R_3$.

Answer 1

Yes, You need to show that $(R_1\circ R_2)\circ R_3\subseteq R_1\circ(R_2 \circ R_3)$ and $R_1\circ(R_2 \circ R_3) \subseteq (R_1\circ R_2)\circ R_3$.

(I think you are not following this definition of composition of relations.)

By the way, to prove first one, just choose an element $(a,d)\in (R_1\circ R_2)\circ R_3$ $\subseteq A\times D$ and apply your definition of composition of relations.

Answer 2

Preparations: $\newcommand{\op}[2]{ \left\langle #1 ,\, #2 \right\rangle }$ $\newcommand{\rel}[1]{ \mathcal{#1} }$ $\newcommand{\dom}[1]{ \mathrm{dom} \ {#1} }$ $\newcommand{\ran}[1]{ \mathrm{ran} \ {#1} }$

Define ordered pair:

$$\op{x}{y} = \left\{\left\{x\right\},\,\left\{x,\,y\right\}\right\}$$

What to prove:

If $\rel{R}$, $\rel{S}$, $\rel{T}$ are relations, such that $\left(\rel{R}\circ\rel{S}\right)\circ\rel{T}$ is well defined, then $\rel{R}\circ\left(\rel{S}\circ\rel{T}\right)$ is also well defined and equals $\left(\rel{R}\circ\rel{S}\right)\circ\rel{T}$.

Proof:

Suppose $\rel{R} \subseteq A \times B,\; \rel{S} \subseteq B \times C,\; \rel{T} \subseteq C \times D$, while $A,\ B,\ C,\ D$ are arbitrary sets.

\begin{align} \op{a}{d} \in \left(\rel{R}\circ\rel{S}\right)\circ\rel{T} &\iff \exists c \in C :\: \left\{ \begin{array}{l} \op{a}{c}\in\rel{R}\circ\rel{S}\\\op{c}{d}\in\rel{T} \end{array} \right. \\ &\iff \exists b \in B,\; \exists c \in C :\: \left\{ \begin{array}{l} \op{a}{b} \in \rel{R} \\ \op{b}{c} \in \rel{S} \\ \op{c}{d} \in \rel{T} \end{array} \right. \\ &\iff \exists b \in B :\: \left\{ \begin{array}{l} \op{a}{b} \in \rel{R} \\ \op{b}{d} \in \rel{S}\circ\rel{T} \end{array} \right. \\ &\iff \op{a}{d} \in \rel{R}\circ\left(\rel{S}\circ\rel{T}\right) \end{align}

Q.E.D.