Reflexive , symmetric and transitive closure of a given relation

Question

Given a relation $R = \{(x,y)\mid y=x+1\}$ and I have to find the reflexive, transitive and symmetric closure.

For reflexive, I added $y=x$ with given condition so now the relation becomes $R = \{(x, y)~| ~y=x+1 , \text{ or}\; y=x\}$

To make it symmetric, I added $y=x-1$ as one more condition but I am confused about transitive closure, what will be that?

Will the final result be a reflexive relation ?

Answer 1

So far, it seems you have $R=\{(x, y)\mid y=x+1, \text{ or}\; y=x \text{ or}\; y = x-1\}$.

For transitive closure, you need to have the relation satisfy, for all $x, y, z$, if $(x, y) \in R$ and $(y, z) \in R$, then your need to ensure $(x, z) \in R$.

Test your current conditions for the relation and check for transitivity.

For example, if $y = x + 1$ and $z = y + 1$, then $z = (x + 1) + 1 \implies z = x+2$. So currently, you don't have transitive closure. Both $(x, y), (y, z)\in R$, but $(x,z) \notin R$.

Note that $R = \{(x, y) \mid y = x\}$, by itself, is an equivalence relation (hence reflexive, symmetric, and transitive for all elements on which it is defined), as equality is perhaps the most fundamental of all equivalence relations.

Assuming we are talking about real numbers, we can get transitive closure (with reflexive closure), on the reals using the relation $R = \{(x, y)\mid y\leq x\}$. But this relation fails to by symmetric. "$\leq$" is a paradigmatic partial order relation on the set of reals: reflexive, antisymmetric, and, and transitive. Can you see why it is transitive, reflexive, but not symmetric?

Answer 2

Let $R_1=\big\{\langle x,y\rangle:y\in\{x-1,x,x+1\}\big\}$; this is the relation that you’ve constructed so far, and it is, as you say, reflexive and symmetric. It is not transitive, however: $0R_11$ and $1R_12$, but $0\not R_1 2$. If you think about this example a bit, you should see that you need to throw in all pairs $\langle x,x+2\rangle$, and of course then you’ll also need all pairs $\langle x-2,x\rangle$ in order to keep symmetry. Call this new relation $R_2$. Is it transitive?

Unfortunately, no: $0R_22$ and $2R_23$ (remember, $R_2$ still has all of the pairs that were in $R_1$), but $0\not R_23$. Again, a little thought shows that this is a general problem: to have any hope of transitivity, we need to throw in all pairs $\langle x,x+3\rangle$ and, to keep symmetry, all pairs $\langle x-3,x\rangle$. Throw these pairs in as well, and call the resulting relation $R_3$. You should check that

$$R_3=\big\{\langle x,x+n\rangle:n\in\{-3,-2,-1,0,1,2,3\}\big\}\;.$$

You can also check that $R_3$ still isn’t transitive: $0R_33$ and $3R_34$, but $0\not R_34$.

In general let

$$R_n=\big\{\langle x,x+k\rangle:k\in\Bbb Z\text{ and }|k|\le n\big\}\;;$$

$R_n$ is clearly reflexive and symmetric, but $0R_nn$ and $nR_n(n+1)$, but $0\not R_n(n+1)$. On the other hand, $0R_{n+1}(n+1)$, so $R_{n+1}$ does a little better than $R_n$ in terms of transitivity. Now let’s do this extension in general:

• Show by induction on $n$ that if $E$ is a reflexive, symmetric, transitive relation containing $R$, then $R_n\subseteq E$.

Thus, the closure that you want must include everything in $\bigcup_nR_n$.

• Check that $\bigcup_nR_n=\big\{\langle x,x+n\rangle:n\in\Bbb Z\big\}$. This can also be described as $\big\{\langle x,y\rangle:y-x\in\Bbb Z\big\}$.

• Show that $\bigcup_nR_n$ is reflexive, symmetric, and transitive, and conclude that it’s the desired closure of $R$.