Associativity of compositions of relations 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$. 
 A: 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.
A: 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.
