Thread: Proof concerning a transitive closure

Problem Statement:

Suppose R is a relation on A and let S be the transitive closure of R. Prove that Dom(S) = Dom(R) and Ran(S) = Ran(R).

*Dom() signifies the domain of the specified relation. Ran() signifies the range of the specified relation.*


My attempt thus far:

Let M = {T ⊆ A x A | R ⊆ T and T is transitive}. I have already shown (in a different exercise) that ∩M is the transitive closure of R (so S = ∩M).


Let x ∈ Dom(S). Then there is some y ∈ A such that (x,y) ∈ S = ∩M. This means (∀K ∈ M)((x,y) ∈ K). We must show x ∈ Dom(R), which means there is some z ∈ A such that (x,z) ∈ R... (and this is where i can't seem to find how to proceed)


As you can see, I am trying to prove the two conjuncts separately. I am proving the equalities by proving that each side is a subset of the other. I can prove the opposite direction- Dom(R) ⊆ Dom(S)- easily, but this one doesn't seem as easy. I'm sure it is analogous for the range equalities as well.


Any insight is appreciated, thanks!

Let T = {(x,y) ∈ A x A | x ∈ Dom(R) and y ∈ Ran(R)}.

Clearly, if (x,y) ∈ R then (x,y) ∈ T. So R ⊆ T. Also, if (x,y),(y,z) ∈ T, then x ∈ Dom(R) since (x,y) ∈ T and similarly z ∈ Ran(R) since (y,z) ∈ T. Hence, (x,z) ∈ T, so T is transitive. Therefore, T ∈ M and so (x,y) ∈ T, which in turn implies x ∈ Dom(R).

Whew! I've proven the other subset direction and it is much easier. I'm sure the range equality is analogous and can use the same relation T. On the other hand, I'm not sure how to feel. I'm definitely happy the problem has been solved, but I feel I shouldn't have struggled as much with it (I usually post problems for help only after pondering them for a few hours with no avail).

Basically, the problem is to prove that a journey of a thousand miles begins with a single step

This is obvious if a journey is defined as a sequence of steps, that is, if the transitive closure of R is defined as . If the transitive closure S is instead defined as the smallest transitive relation containing R, the problem reduces to proving that . This is proved by showing that contains R and is transitive.

More generally, one can show that for some relation T such that Dom(R) = Dom(T) and Ran(R) = Ran(T). The inclusion follows if in addition T contains R and is transitive. This is what you did, and your choice of T is quite elegant.

Originally Posted by Syrus

Clearly, if (x,y) ∈ R then (x,y) ∈ T. So R ⊆ T. Also, if (x,y),(y,z) ∈ T, then x ∈ Dom(R) since (x,y) ∈ T and similarly z ∈ Ran(R) since (y,z) ∈ T. Hence, (x,z) ∈ T, so T is transitive. Therefore, T ∈ M and so for all (x,y), if (x,y) ∈ S, then (x,y) ∈ T, which in turn implies x ∈ Dom(R).