Determine whether this relation is reflexive, symmetric...

Question

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.

Answer 1

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

Answer 2

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.