Showing that a relation is neither an equivalence relation nor a partial order

Question

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.

Answer 1

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

Answer 2

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