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.

  • $\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$ – Robert Shore Jun 1 at 9:37

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

| cite | improve this answer | |
  • $\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$ – Eevee Trainer Jun 1 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$ – Sahiba Arora Jun 1 at 9:42

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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