Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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?

share|improve this answer
    
thanks. answer is given as R={(x,y)| y<=x}. thats may be because they dont want to loose the actual relation i.e. y=x+1 . but i am not getting how they got that answer –  user1771809 Jan 28 '13 at 17:01
    
R = {x, y) | y<=x} will give you reflexive closure and transitive closure, but not symmetric closure. It will however, give you an antisymmetric relation. –  amWhy Jan 28 '13 at 17:06
    
Do you need to find "separate" conditions for closure? That is, what will the relation need to be for it to be reflexive. Separately, what will it need to be for it to be symmetric. Separately, what will it need to be for the relation to by transitive. Or...do you need closure of all three properties? –  amWhy Jan 28 '13 at 17:11
    
If you want closure with respect to all three properties, then you need $R = \{ (x,y) | x-y \in \mathbb{Z} \}$. –  polkjh Jan 28 '13 at 17:30
    
$x<y$ is not the transitvive closure of $R$, unless you are more specific about the set this is a relation on (is $R\subseteq\mathbb Z\times Z$ or viewed as $R\subseteq \mathbb R\times\mathbb R$?) –  Hagen von Eitzen Jan 28 '13 at 18:46

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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