2
$\begingroup$

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?

  • 0
    @peoplepower: It would mean... a - b > 10? I still don't see the point :(2012-12-06

3 Answers 3

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.

  • 0
    @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.2012-12-06
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.

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.

  • 0
    I do know the definition of total - but I don't know how to prove it (which is precisel$y$ wha$t$ I'm asking here).2012-12-06