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

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.

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

• "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). – Eevee Trainer Jun 1 at 9:41
• @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. – 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).