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.

Determine whether this relation $R$ on the set of all integers is reflexive, symmetric, anti-symmetric and/or transitive where $x\,R\,y$ iff $x = y + 1$ or $x = y-1$

  • It is not reflexive: Let $x = 2$: $2\neq 2 + 1$ and $2 \neq 2 - 1$.

  • It is symmetric: If $x = y + 1$ then $y = x - 1$ and if $x = y - 1$ then $y = x + 1$.

  • It is not anti-symmetric: Let $x = 3$ and $y = 2$; then $3 = 2 + 1$ ($x\,R\,y$) and $2 = 3 - 1$ ($y\,R\,x$) And let $x = 2$ and $y = 3$; then $2 = 3 - 1$ ($x\,R\,y$) and $3 = 2 + 1$ ($y\,R\,x$) but $3\neq 2$.

Can anyone prove whether this relation is transitive or not? thanks.

share|improve this question
1  
Try it for the numbers $1,2,3$. –  Samuel May 27 '13 at 20:34
1  
$xRy$ iff $x,y$ differ by one. So, if $xRy$ and $yRz$, what can you say about the relationship between $x$ and $z$? –  copper.hat May 27 '13 at 20:34
    
Thanks guys.... –  ammarx May 28 '13 at 8:10
add comment

2 Answers

up vote 4 down vote accepted

You did fine with reflexivity, and with symmetry and antisymmetry.

Now, let's look at transitivity:

We can summarize the relation as follows: $xRy$ if and only if $x$ and $y$ differ by $1$.

So, suppose $xRy$ ($x$ and $y$ differ by one) and $yRz$ ($y$ and $z$ differ by one),

What may be the case about the difference between $x$ and $z$?

  • (Suspect a counterexample exists: just find $x, y, z$ such that $x = y - 1, y = z - 1 \implies x = z - 2$.
    Or, vice versa, $x = y+1, y = z+1 \implies x = z+2)$

Let $x = 0$, $y = 1$, and $z = 2$, so we certainly have $x, y, z \in \mathbb Z$

  • Clearly, $x = y - 1$ since $0 = 1-1$, so $x R y$,
  • And $y = z - 1$, since $1 = 2 - 1$, so $y R z$.
  • But it is not true that $x = z + 1 $, since $0 \neq 2+1 = 3$ nor does $x = z - 1$, since $0 \neq 2 - 1 = 1$.

Hence, $x$ is not related to $z$, and transitivity fails.

All we need is one counterexample to prove that a relation is non-transitive, and we've just found one such couterexample

share|improve this answer
    
Thanks @amWhy for your answer :) –  ammarx May 28 '13 at 8:06
    
done....... :) . –  ammarx May 28 '13 at 14:48
    
You're welcome, ammarx! –  amWhy May 28 '13 at 14:50
add comment

To disprove, you only need to find a counter example.

Clearly $R 0 1$ and $R 1 0$ hold, but then it would also have to be the case that $R 0 0$ holds, which is not true.

In general, transitive and symmetric would imply reflexive (on its domain) [which would be a contradiction to $R$ not reflexive for 2, which is in the domain]: $Rxy$ implies $Rxy$ by symmetry, from which $Rxy \wedge Ryx \implies Rxx$ by transitivity.

share|improve this answer
    
Perhaps you mean transitive and symmetric. However a relation can be transitive and symmetric whilst not being reflexive: the empty relation is of course transitive and symmetric, but fails to be reflexive on any non empty set. –  egreg May 27 '13 at 21:09
    
@egreg A transitive and symmetric relation is reflexive on its domain. –  Mario Carneiro May 27 '13 at 21:45
    
@MarioCarneiro That's of course true. But it's a very common mistake to derive reflexivity from transitivity and symmetry without checking the domain. –  egreg May 27 '13 at 21:47
    
@egreg The proof starts from the assumption $xRy$ for some $y$, so that implies the domain limitation. (Stated another way, if $R$ is transitive and symmetric, then $xRy$ implies $xRx$.) –  Mario Carneiro May 27 '13 at 21:49
    
@MarioCarneiro Is the relation $R=\{(1,1)\}$ reflexive on the set $X=\{0,1\}$? Of course not. This is the kind of error I'm referring to. –  egreg May 27 '13 at 21:53
show 2 more comments

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.