# Let $R$ be a relation on $A$ and $S$ its transitive closure. Prove $\text{Dom}(S) = \text{Dom}(R)$ and $\text{Ran}(S) = \text{Ran}(R)$

I have the following exercise from the book "How to prove it", chapter 4.5, p.211, problem 9.

Suppose $R$ is a relation on $A$, and let $S$ be the transitive closure of $R$. Prove that $\operatorname{Dom}(S) = \operatorname{Dom}(R)$ and $\operatorname{Ran}(S) = \operatorname{Ran}(R)$

Since I had no idea how to approach it, I looked at the hint in the appendix where it says:

Hint: Let $T = \lbrace(x,y) \in S \mid x \in \operatorname{Dom}(R) \text{ and } y \in \operatorname{Ran}(R)\rbrace$. Prove that $R \subseteq T$ and $T$ is transitive.

I really don't understand why this should then be the proof. Can somebody explain the rational behind this to me?

The idea is that the transitive closure of $R$ is the smallest transitive relation containing $R$. The hint gives a transitive relation that contains $R$ and has the same domain and range as $R$. So we have $R\subseteq S\subseteq T$.
Consequently, we have $\text{dom}(R)\subseteq\text{dom}(S)\subseteq\text{dom}(T)$, and similarly for the ranges. But the domains of $R$ and $T$ are equal, and so the domain of $S$ is the same also. Similarly for ranges.
• Thank you, so why do you know that $S \subseteq T$? Mar 18, 2015 at 16:03
• Because $S$ is the smallest transitive relation containing $R$, which means it will be a subset of any transitive relation containing $R$ (such as $T$). Mar 18, 2015 at 16:06
• This means I deliberately construct $T$ such that $S = T$ from the beginning? Mar 18, 2015 at 16:09
• It is not necessarily the case that $S=T$, just that $S\subseteq T$. Mar 18, 2015 at 16:11