Proving $S_1 \subseteq S_2$ for transitive closure

Question

This is one of the problem I have been working from Velleman's How to prove book:

Suppose $R_1$ and $R_2$ are relations on $A$ and $R_1 \subset R_2$l

(a) Let $S_1$ and $S_2$ be the reflexive closure of $R_1$ and $R_2$ respectively. Prove that $S_1 \subseteq S_2$.

(b) Do similar theorem hold for the symmetric and transitive closures ? Justify your answer with proofs or counterexamples.

Now I have done the first part of the problem and trying to see if it holds for transitive closure. This has been my attempt:

Let $S_1$ and $S_2$ be transitive closure of $R_1$ and $R_2$ respectively. Suppose $a \in A$ and $b \in A$ such that $(a,b) \in S_1$. Now there can be two cases:

Case 1. $(a,b) \in R_1$ Then since $R_1 \subseteq R_2$ it follows that $(a,b) \in R_2$ Now from the definition of $S_2$, it follows that $R_2 \subseteq S_2$. So, we can conclude that $(a,b) \in S_2$.

Case 2. $(a,b) \notin R_2$. Then there is some $c \in A$ such that $(a,c) \in S_1$ and $(c,b) \in S_1$

Now I'm stuck in that part. It just leads me back to square one. How shall I proceed from here or is there some other approach I need to take ?

---

Note: The book hasn't yet covered Induction, so ideally I'm looking for a proof without using it.

Answer 1

Hint 1

One way to think of the transitive closure of a relation $\sim$ is as the set of all $(x,y)\in A^2$ such that there is some chain $x= a_0 \sim a_1 \sim a_2 \sim a_3 \sim \cdots \sim a_n = y$ for some finite chain of $a_i$ such that $a_i\sim a_{i+1}$ for all $i=0,\ldots,n-1$. That this is a transitive relation containing $\sim$ is easy to check, and it must be the smallest since if any transitive relation contains $\sim$, and such a chain exists, then by induction and the transitivity of the larger relation, $(x,y)$ would have to be in the larger relation. Try using this equivalent definition to prove the result.

Hint 2

Now suppose $R_1\subset R_2$, then consider $S_1$. If $(x,y)\in S_1$ then there is a chain in $R_1$ between $x$ and $y$.

Solution

Since $R_1\subset R_2$, this is also a chain in $R_2$ so $(x,y)\in S_2$, and $S_1\subset S_2$.

Non-inductive Solution

It is also possible to do this without the explicit construction of the transitive closure.

These kinds of proofs are often unintuitive, which is why I didn't present it earlier. But they are very common throughout mathematics, so here goes.

Since the transitive closure of a relation is the smallest transitive relation containing the original relation, and the intersection of transitive relations is again transitive, any transitive relation that contains another relation contains that relation's transitive closure. $R_1\subset R_2\subset S_2$, so $S_1\subset S_2$.