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.

https://en.wikipedia.org/wiki/Composition_of_relations... are you using this convention ndrizza? — JP McCarthy, Jul 15 '15 at 14:09
Relation composition. I've now added it to the body. Yes I'm using this convention. — ndrizza, Jul 15 '15 at 14:10
Yes, but like at max. 1 min after asking. I noticed the typo instantly. It hasn't changed since then. — ndrizza, Jul 15 '15 at 14:20

score 1 · Accepted Answer · answered Jul 15 '15 at 14:13

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$.

1 Answers1