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.

Define a relation $R$ on $\mathbb{Z}$ by $R = \{(a,b)|a≤b+2\}$.

(a) Prove or disprove: $R$ is reflexive.

(b) Prove or disprove: $R$ is symmetric.

(c) Prove or disprove: $R$ is transitive.

For (a), I know that $R$ is reflexive because if you substitute $\alpha$ into the $a$ and $b$ of the problem, it is very clear that $\alpha \leq \alpha + 2$ for all integers.

For (b), I used a specific counterexample; for $\alpha,\beta$ in the integers, if you select $\alpha = 1$, and $\beta = 50$, it is clear that although $\alpha ≤ \beta + 2$, $\beta$ is certainly not less than $ \alpha + 2$.

However, for (c), I am not sure whether the following proof is fallacious or not:

Proof: Assume $a R b$ and $b R g$;

Hence $a ≤ b + 2$ and $b ≤ g + 2$

Therefore $a - 2 ≤ b$ and $b ≤ g + 2$

So $a-2 ≤ b ≤ g + 2$

and clearly $a-2 ≤ g+2$

So then $a ≤ g+4$

We can see that although $a$ might be less than $ g+2$, it is not always true.

Therefore we know that the relation $R$ is not transitive.

QED.

It feels wrong

share|improve this question
    
I apologize for the syntax by the way, I'm not very well-versed in LaTeX yet. –  Arthur Collé Aug 2 '12 at 4:26

2 Answers 2

up vote 5 down vote accepted

You are right, the attempt to prove transitivity doesn't work. But your calculation should point towards a counterexample.

Make $a \le b+2$ in an extreme way, by letting $b=a-2$. Also, make $b\le g+2$ in the same extreme way. Then $a \le g+2$ will fail. Perhaps work with an explicit $a$, like $47$.

share|improve this answer
    
Merci beaucoup André :). Should I take away from this that it is better to cite a specific counter-example rather than citing the conditions by which a counter-example could exist? What is the meaning of "the attempt to prove transitivity doesn't work." That the 'proof' as I had it was incomplete without a proper crtex? –  Arthur Collé Aug 2 '12 at 4:34
1  
@Augustus: The attempt doesn't work because what you were trying to prove is false. But you only showed that $a \le g+4$. When you think about when this does not imply that $a \le g+2$, it points to how to construct a counterexample. And yes, if it is feasible to do so, produce a specific counterexample, like $a=47$, $b=45$, $g=43$. –  André Nicolas Aug 2 '12 at 4:40

Here's a counterexample: $a = 5, b = 3, c = 1$

share|improve this answer

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.