2

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?

Saturn
  • 7,191

3 Answers3

2

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.

Thomas
  • 43,555
  • 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. – Saturn Dec 06 '12 at 04: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 06 '12 at 14:15
1

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.

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
0

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.

Jebruho
  • 1,700
  • Totality is stronger than this. We need for each pair $x,y\in\mathbb{Z}$ that either $xRy$ or $yRx$. – yearning4pi Dec 06 '12 at 02: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). – Saturn Dec 06 '12 at 02:54