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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .