Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

3 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.