Find transitive closure of $D_r = \{(x,y) \in \mathbb{R} \times \mathbb{R} \mid |x - y| = r\}$

84 Views Asked by At

This is one of the problems I have been solving in Velleman's How to prove book:

Find the reflexive, symmetric and transitive closures of the following relations:

$D_r = \{(x,y) \in \mathbb{R} \times \mathbb{R} \mid |x - y| = r\}$, for any positive real number $r$.

Now I have solved the reflexive and symmetric part. But I'm stuck with the transitive closure part. How to approach the problem? (Note that the book hasn't covered induction yet, so I would like to know a simpler way of solving it.)

1

There are 1 best solutions below

0
On

A way to approach it is to consider constructing the transitive closure in stages - what relation is formed if we take the set of $(x,y)$ such that either $(x,y) \in D_r$ or there is some $z$ such that $(x,z),(z,y) \in D_r$? Then what happens if you include longer chains like this?

Slightly more detailed hint (but still only hinting):

Certainly, if there is some chain $x=x_0,x_1,...,x_n=y$ such that each $(x_i,x_{i+1})$ is in $D_r$ then $(x,y)$ must be in the transitive closure of the $D_r$. You can, for the relation $D_r$, write this as a single condition on $\lvert x - y \rvert$. This gives a relation that contains $D_r$. Is this relation transitive? If not, what happens if you keep repeating this process? If so, what does this mean for the transitive closure of $D_r$?