1
$\begingroup$

Say we have a relation $R$ on $\mathbb{Z} \times \mathbb{Z}$ such that $(a, b) R (c, d)$ if $a^2 + b^2 \leq c^2 + d^2$

So to prove that $R$ is not an equivalence relation we need to show that $R$

  • Is not one of reflexive, symmetric or transitive

And to prove that $R$ is not a partial order we need to show that $R$

  • Is not one of reflexive, anti-symmetric or transitive

I'm practicing relation type questions, however, my current experience has mainly been with two variables (one on each side of the relation,) so, I'm struggling a bit with this question.

My attempt so far is as follows

$R$ is reflexive as $(a, a) R (a, a)$ because $a^2 + a^2 \leq a^2 + a^2$

$R$ is not symmetric as $a^2 + b^2 \leq c^2 + d^2$ does not imply that $c^2 + d^2 \leq a^2 + b^2$

So as $R$ is not symmetric it cannot be an equivalence relation.

At this point, I'm a bit stuck. I'm not sure how to test if $R$ is transitive or anti-symmetric.

$\endgroup$
1
  • $\begingroup$ Some intuition may help. Note that $a^2+b^2$ is the square of the distance from the origin. And your proof of reflexivity isn’t correct. You need to work with general $(a, b)$, not just points specifically of the form $(a, a)$. $\endgroup$ Commented Jun 1, 2020 at 9:37

2 Answers 2

2
$\begingroup$

To show $R$ is not symmetric you should provide a counterexample. For instance $(1,1)R(2,2)$ but $(2,2)\not R(1,1).$

$R$ is not anti-symmetric as $(1,2)R(2,1)$ and $(2,1)R(1,2)$ but $(1,2)\neq (2,1).$

$\endgroup$
2
  • $\begingroup$ "To show R is not symmetric you need to provide a counterexample." -- OP's argument is true however, if not perfectly elaborated on. A counterexample is not strictly necessary. After all, if $x < y$ (strictly so), then $x \le y$ does not necessarily imply $y \le x$ (in fact, it never does). $\endgroup$ Commented Jun 1, 2020 at 9:41
  • 1
    $\begingroup$ @EeveeTrainer I agree. I just meant OP's argument was incomplete and one way was to provide a counterexample. However, you're right, I'm going to change "need" to "should" for correctness. $\endgroup$ Commented Jun 1, 2020 at 9:42
0
$\begingroup$

To test antisymmetry, notice that $(a,b)R(c,d)$ and $(c,d)R(a,b)$ must both first apply if we suppose it is antisymmetric. Then we have

$$a^2 +b^2 \le c^2 + d^2 \text{ and } c^2 + d^2 \le a^2 + b^2$$

The issue here might be more noticeable if we let $p = a^2 + b^2$ and $q = c^2 + d^2$. Then we have $p \le q$ and $q \le p$. Thus $p=q$ and thus $a^2 + b^2 = c^2 + d^2$. But this isn't enough to get us where we want to go: some numbers can be written as the sum of squares in two different ways, or more. (Some further reading here.) For instance, $50 = 5^2 + 5^2 = 7^2 + 1^2$.

So, then, this gives us an idea... $(5,5)R(7,1)$ and $(7,1)R(5,5)$, correct? After all, they satisfy the inequalities. Yet $(5,5) \ne (7,1)$, showing that antisymmetry doesn't hold. If antisymmetry held we'd have $(a,b)=(c,d)$.

Also, a minor note: you don't need to prove reflexivity of $R$. Since you know it's not symmetric, $R$ is not an equivalence relation, and since you know it's not antisymmetric, you know it's not a partial order. (You also don't have to do arguments in generality as you did for the symmetry case. It's good if you can, but all you need is a single counterexample to blow the whole thing apart.) It might also be good to explain why $a^2 + b^2 \le c^2 + d^2$ doesn't necessarily imply the reverse inequality (hint: it doesn't imply that when the inequality held is strict).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .