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

Contains = is a superset of.

The symmetric (resp. transitive) closure of $R$ is the least symmetric (transitive) relation containing $R$.

The symmetric (transitive) closure of $R_2$ contains $R_2$ and thus contains $R_1$; since the symmetric (transitive) closure of $R_1$ is the least symmetric (transitive) relation containing $R_1$, it must be contained by the closure of $R_2$ by definition of "least".

Edit: going in more detail. The case for "transitive" is analogous.

Consider a relation $R \subseteq A^2$. We define the symmetric closure of R to be $S = \{(x, y) \in A^2 : $ for every symmetric relation $S' \subseteq A^2$ such that $R \subseteq S'$, $(x, y) \in S'\}$.

Note that the symmetric closure of $R$ is symmetric and contains $R$.

Note also that whenever we have $S' \subseteq A^2$ satisfying the same properties (that is, whenever we have symmetric $S'$ such that $R \subseteq S'$), we will always have $S \subseteq S'$. Therefore, $S$ may be described as "the least symmetric relation containing $R$".

Back to the problem at hand. Note therefore that we have $R_2 \subseteq S_2$ and $S_2$ symmetric since it is given that $S_2$ is the symmetric closure of $R_2$. Therefore, since it is given that $R_1 \subseteq R_2$, we have $R_1 \subseteq S_2$. That is, $S_2$ is a symmetric relation containing $R_1$. But it is given that $S_1$ is the symmetric closure of $R_1$; therefore, we have $S_1 \subseteq S_2$.

Interestingly, it turns out that the symmetric closure can be given a simpler description. The symmetric closure of $R$ can be written as $R \cup \{(x, y) \in A^2: (y,x) \in R\}$. It can easily be shown that this definition is equivalent to the above.

Sadly, the transitive closure doesn't have a simpler description. It does, however, have a more "concrete" (or, to be precise, more predicative) definition. The transitive closure can also be defined as $\{(x, y) \in A^2 : $ there is some $i > 1$ and a sequence $x_1, ..., x_i$ such that $x = x_1$, $y = x_i$, and for all $j$ s.t. $1 \leq j < i$, $(x_j, x_{j + 1}) \in R\}$. This definition too is equivalent to the above (of transitive closure).

However, it's easiest to approach the problem using the "least relation" definition.

Answer 2

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