Consider the category of Relations, whose objects are sets and morphisms are relations $R:A \rightarrow B$ if $R\subset A \times B$ is relation. Compostion is defined by $S \circ R:=\{(a,c)| \exists b \in B \, \text{ with } (a,b)\in R \, \, (b,c)\in S\}$ where $R \subset A \times B$ and $S \subset B\times C$.
I want to show that this is a category. Clearly the identity morphism is given by relation $1_A=A \times A$. I am trying to show associativity but I'm slightly confused. I can see the argument that you would write down but I am not sure why it is justified.
If we have $T \circ (S \circ R)=\{(a,d)| \exists c \in C \, \text{ with } (a,c)\in S \circ R \, \, (c,d)\in T\}$, I am confused about how the quantifiers work when we trying to replace $(a,c) \in S\circ R$ with the conditions for being in $S\circ R$.
I don't know how justify going from here to what would be the correct answer $T \circ (S \circ R)=\{(a,d)| \exists c \in C \, \text{ with } (\exists b \in B \, \text{ with } (a,b)\in R \, \, (b,c)\in S) \, \, (c,d)\in T\}$.
If I could show that this was the same as $T \circ (S \circ R)=\{(a,d)| \exists c \in C \, \exists b \in B \, \text{with} (a,b)\in R \, (b,c)\in S, (c,d)\in T\}$ then we would be done
Show that $X = Y$ iff $w \, X\, z \;=\; e \, Y \, z$ for any elements $w, z$.
$\def\BEGINstep{ \langle } \def\ENDstep{ \rangle } \newcommand{\step}[2][=]{ \\ #1 \;\; & \qquad \color{maroon}{\BEGINstep \text{ #2 } \ENDstep} \\ & } \newenvironment{calc}{\begin{align*} & }{\end{align*}}$
\begin{calc} w \,(T ∘ (S ∘ R))\, z \step{ definition of composition } ∃ x. \quad w \,T\, x \, (S ∘ R) \, z \step{ definition of composition, and “and” distributes over ∃ } ∃ x, y. \quad w \,T\, x \, S\, y \,R \, z \step{ definition of composition, and “and” distributes over ∃ } ∃ y. \quad w \,(T ∘ S)\, y \,R \, z \step{ definition of composition } w \,((T ∘ S) ∘ R)\, z \end{calc}