How can I prove if $SR=RS$, then $SR$ is the least equivalence relation?

Question

• from Jean Gallier, Logic For Computer Science and Discrete Mathematics.

assumptions:

1. two relations $S, R$ on $A$ are equivalence relation.
2. composition of relation $SR=RS$.

I have to prove:

1. relation $SR$ is the least equivalence relation containing $S$ and $R$.

I tried:

I've proven $SR$ is...

1. equivalence relation and
2. the relation that contains $S$ and $R$.

I have to:

1. $SR$ is the least.

at once I've assumed that $SR$ is not the least, i.e. there are some relation $Q$ containing $S$ and $R$ which is not $SR$ but $SR$ have some elements that $Q$ does not have.

then I tried to deduce the contradiction from the assumption, but I can't deduce.

Answer 1

This is assuming what you have claimed (that you've proven that $RS$ is an equivalence relation and $R,S \subseteq RS$).

Let $Q$ be another equivalence relation on $A$ and suppose $R,S \subseteq Q$.

Given some $(u,v) \in RS$, there is $w \in A$ such that $uRwSv$.
As $R,S \subseteq Q$, we also have that $uQwQv$;
as $Q$ is transitive, $(u,v) \in Q$.

It follows that $SR=RS \subseteq Q$, that is, $RS$ is the least equivalence relation on $A$ containing $R$ and $S$.