# Determine whether this relation is reflexive, symmetric…

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.

-
Try it for the numbers $1,2,3$. – Samuel May 27 '13 at 20:34
$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

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

-
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

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.

-
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