0
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thank you, so why do you know that $S \subseteq T$? $\endgroup$ Mar 18, 2015 at 16:03
  • $\begingroup$ 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$). $\endgroup$
    – paw88789
    Mar 18, 2015 at 16:06
  • $\begingroup$ This means I deliberately construct $T$ such that $S = T$ from the beginning? $\endgroup$ Mar 18, 2015 at 16:09
  • $\begingroup$ It is not necessarily the case that $S=T$, just that $S\subseteq T$. $\endgroup$
    – paw88789
    Mar 18, 2015 at 16:11
  • $\begingroup$ I'm still chewing on it, but I think I got the main point. Thank's for your clarifications. $\endgroup$ Mar 18, 2015 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.