2

Why is the relation $∣x-y∣ \geq 1$ on a set of positive integers not transitive?

According to my professor it is not a transitive relation but I'm having a hard time finding cases to satisfy this.

Sammy Black
  • 25,273
Ryan Garcia
  • 33
  • 2
    Consider $(x,y,z)=(1,0,1)$. – lulu Nov 09 '23 at 23:38
  • To show that a particular "for all" property of a relation does not hold, you ought to come up with an explicit counterexample. – Sammy Black Nov 09 '23 at 23:42
  • 6
    Perhaps translate this into plain English: "$x$ is a distance of at least one unit from $y$." Does $x$ and $y$ being 1 mile apart, and $y$ and $z$ being 1 mile apart, ensure $x$ and $z$ are at least 1 mile apart? (Hint: What if you go back along your path, i.e. let $x=z$. This is the motivation behind lulu's post.) – PrincessEev Nov 09 '23 at 23:46
  • 2
    @lulu: That example does not quite work, since the relation that Ryan is working with is defined on the positive integers. It can be modified to, say, $(x,y,z)=(2,1,2)$. – Joe Nov 09 '23 at 23:50
  • 1
    I believe my confusion is coming from my assumption that x,y,z are unique but it appears they do not have to be – Ryan Garcia Nov 09 '23 at 23:51
  • @Joe good catch. – lulu Nov 09 '23 at 23:52
  • @RyanGarcia: A rule of thumb in mathematics is the following: unless an author explicitly states that a collection of variables is distinct, they may well be equal. – Joe Nov 10 '23 at 00:08

1 Answers1

2

If a relation $R$ on a set $S$ is not transitive, then there exist $a,b,c\in S$ such that

  • $a\mathrel R b$
  • $b\mathrel R c$
  • $a\not\mathrel R c$

Here, $R$ is the relation on $\mathbb Z^+$ (the set of positive integers) such that $a\mathrel R b$ if and only if $|x-y|\ge 1$. So, to show that $R$ is not transitive, we need to find $a,b,c\in\mathbb Z^+$ such that $|a-b|\ge 1$, $|b-c|\ge 1$, but $|a-c|<1$.

Now, if there is an example of $a$, $b$, and $c$ that satisfy the above, then due to the condition $|a-c|<1$, it must be the case that $a=c$ (if two integers differ by an amount less than one, they must be equal). Thus, the question boils down to finding positive integers $a$ and $b$ such that $|a-b|\ge 1$: indeed, if this condition holds then $|b-c|=|b-a|=|a-b|\ge 1$, and $|a-c|=0<1$. This is easy: for instance, we could take $a=1$ and $b=3$, and we're done.

Joe
  • 19,636