3
$\begingroup$

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

  • 0
    I apologize for the syntax by the way, I'm not very well-versed in LaTeX yet.2012-08-02

2 Answers 2

5

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$.

  • 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$.2012-08-02
1

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