Prove or disprove: $\forall\rho,\sigma,\phi\subseteq A^2: \ \rho \subseteq \sigma \rightarrow \rho \circ \phi \subseteq \sigma \circ \phi$

Question

Where $\rho,\sigma,\phi$ are relations on a finite set $A$ and $\circ$ denotes the relation composition.

I was neither able to prove it, nor to come up with a counterexample.

Answer 1

I'm not sure if "$\rho \circ \phi$" means we do $\rho$ first or not, but it won't matter.

Let $(x,y) \in \rho \circ \phi$.

Case 1: We do $\rho$ first.

Then there exists $z \in A$ such that $(x,z) \in \rho$ and $(z,y) \in \phi$. But then $(x,z) \in \sigma$, and so $(x,y) \in \sigma \circ \phi$.

Case 2: We do $\phi$ first.

Then there exists $z \in A$ such that $(x,z) \in \phi$ and $(z,y) \in \rho$. But then $(z,y) \in \sigma$, and so $(x,y) \in \sigma \circ \phi$.