Let $S_1$ and $S_2$ be the symmetric closures of $R_1$ and $R_2$, respectively. Prove that $S_1 \subseteq S_2$.

Question

This is an exercise from Velleman's "How To Prove It".

Suppose $R_1$ and $R_2$ are relations on $A$ and $R_1 \subseteq R_2$.

• Let $S_1$ and $S_2$ be the symmetric closures of $R_1$ and $R_2$, respectively. Prove that $S_1 \subseteq S_2$.
• Let $T_1$ and $T_2$ be the transitive closures of $R_1$ and $R_2$, respectively. Prove that $T_1 \subseteq T_2$.

The symmetric closure $S$ of $R$ is the smallest set (under the subset partial order) such that $R \subseteq S$ and $S$ is symmetric. The definition for transitive closure is similar.

I am stuck on solving both of these problems.
For the first one, if I could somehow show that an arbitrary element of $S_1$ is contained in $R_1$, it would be easy to show that $S_1 \subseteq S_2$, since $R_1 \subseteq R_2$ and $R_2 \subseteq S_2$.

Any hints would help. Thanks in advance!

Answer 1

Since $R_1 \subseteq R_2$ and $R_2 \subseteq S_2$ we have $R_1 \subseteq S_2$, but since $S_2$ is reflexive and $S_1$ is the smallest reflexive relation that contains $R_1$, it follows that $S_1 \subseteq S_2$. Similarly we can show that $T_1 \subseteq T_2$.