[Math] Determine whether this relation is reflexive, symmetric…

discrete mathematicsequivalence-relationsrelations

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.

Best Answer

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

Related Question