# How to verify if $aRb \leftrightarrow a - b \le 10$ is total?

Book exercise:

$R$ is a relation over $\mathbb Z$.

$aRb \leftrightarrow a - b \le 10$

Verify if it is reflexive, symmetric, transitive, antisymmtetic or total.

I can tell it is reflexive, since $a-a = 0 \le 10$.

It isn't symmetric, since $(0R11)$ but $\lnot(11R0)$

Not antisymmetric either, because $(10R0)\land(0R10)$ but $\lnot(10 = 0)$

Not transitive either, because $(11R1) \land (1R0)$ but $\lnot(11R0)$

All was well, until I tried to verify if it was total. Haven't been able to find a counter-example, so it is likely total after all. However, I don't know how to prove it. How can I?

-
Say we have $a,b\in\mathbb{Z}$ and $\lnot(aRb)$. What does that translate into? –  peoplepower Dec 6 '12 at 2:54
@peoplepower: It would mean... $a - b > 10$? I still don't see the point :( –  Zol Tun Kul Dec 6 '12 at 3:02

## 3 Answers

You want to prove that given any two integers $a$ and $b$, you have that $aRb$ or $bRa$. That is you would want that for given $a,b$ one of the following hold \begin{align} a - b &\leq 10 \\ b - a &\leq 10. \end{align} This is obviously true. Why? The "formal" proof is you want: Given $a$ and $b$ you have $a-b \in \mathbb{Z}$. Say that $a-b \geq 0$. Then $b-a = - (a-b)\leq 0 \leq 10$ and so by definition $bRa$. Now assume the other case $a-b \leq 0$. Then $a-b \leq 0 \leq 10$ and so by definition $aRb$. Hence you have shown that given any two $a,b\in \mathbb{Z}$ you will have $aRb$ or $bRa$.

So the relation is total.

-
I can see it is true, yes, definitely true - but I need to prove it in a formal manner. I doubt that showing a bunch of examples would work. –  Zol Tun Kul Dec 6 '12 at 4:04
@Omega: I edited my answer to try and help a bit more. There really isn't more to it than this. You can't make it much more formal. –  Thomas Dec 6 '12 at 14:15

For any two integers $\,x,y\,$ , either $\,x-y\leq 10\,$ or $\,x-y>10\Longleftrightarrow y-x<-10<10\,$ , so yes: it's total.

-

Basically, you need to show that for all $x,y\in \mathbb{Z}$, $x-y\leq 10$ or $y-x\leq 10$. I'll leave it to you to see if this is true. Assume that neither is true. Then see if you can get a contradiction. That's a possible proof.

-
Totality is stronger than this. We need for each pair $x,y\in\mathbb{Z}$ that either $xRy$ or $yRx$. –  peoplepower Dec 6 '12 at 2:53
I do know the definition of total - but I don't know how to prove it (which is precisely what I'm asking here). –  Zol Tun Kul Dec 6 '12 at 2:54