# Could somebody please explain to me how this binary relation is Anti-symmetric?

$$A = \{1, 2, 3, 4\}$$ where $$xRy$$ if $$x \mid y$$

$$R = \{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)\}$$.

I am watching this video about Partial Orders and the guy just said the relation was Anti-symmetric; however, I do not understand why.

I know that for a relation to be anti-symmetric : if $$aRb$$ and $$bRa$$ then $$a = b$$.

However, I do not see that there. Sorry for not giving in more knowledge. I am just really confused on this one.

You may find it useful to take the definition of "anti-symmetric" and use it to say under what conditions a relation $R$ is not anti-symmetric. You'll find that for $R$ not to be anti-symmetric means that there exist $a$ and $b$ such that $aRb$ and $bRa$ but $a\neq b$. Now look at the relation $R$ exhibited in the question and see whether you can find any such $a$ and $b$.

Suppose $xRy$ and $yRx$, with $x,y\ge0$. Then $x$ is a factor of $y$, and $y$ is a factor of $x$. These imply, respectively, that $x\le y$ and $y\le x$. It is clear to deduce from this that $x=y$.

If $a|b$ and $b|a$ then integers $k,\,l$ exist with $b=ka,\,a=lb=lka$. Since $a,\,b\in\left\{ 1,\,2,\,3,\,4\right\}$, we have $k,\,l>0$ and $lk=1$. Hence $k=l=1$ and $a=b$.

• But what about (1,2) (1,3) ... 2 doesn't divide 1 and 3 doesn't divide 1. What do I do with those? Dec 30, 2016 at 21:44
• @RayRutzer In those cases $\left(a,\,b\right)\in R$ but $\left(b,\,a\right)\notin R$ (if I'm remembering $R$'s definition correctly).
– J.G.
Dec 30, 2016 at 23:39

Let $x \mid y$ stand for "$x$ evenly divides $y$." If $x \mid y$ and $y \mid x$ then $x=y$. Hence, the divisibility relation is antisymmetric. (It is indeed a partial order.)

The fact that for non-negative integers $x \mid y$ and $y \mid x$ imply that $x=y$ is not surprising, but if you want a full proof, consider this: $x$ evenly divides $y$ if there exists a non-negative integer $n$ such that $y = nx$. Likewise, if $y$ evenly divides $x$, then there exists a non-negative integer $m$ such that $x = my$.

If both conditions are true, consider two cases. If $x=0$, then $y = n0 = 0$. Otherwise, substitution gives you $x = mnx$, and dividing both sides by $x$ (which we can, because we are now assuming that it is non-zero), we get $1 = mn$. The only solution for $m,n$ nonnegative integers is $m=n=1$, which finally gives $x=y$.

Note that assuming that the integers are non-negative is important. Otherwise, $-3$ divides $3$ and vice versa, but $-3 \neq 3$.

Use the contrapositive way of thinking about antisymmetry: $$aRb \text{ and }bRa \implies a = b$$ is equivalent to $$a \neq b \implies \text{not} (aRb \text{ and } bRa);$$ in other words, you never see both $aRb$ and $bRa$ (or, as ordered pairs, both $(a, b)$ and $(b, a)$) for distinct $a, b$. You don't even need to recognize that it's a divisibility relation; you can just look at it!

• But what about (1,1), (2,2) ... wouldn't that violate that clause? Dec 30, 2016 at 21:48
• No, because $1 \neq 1$ is false (as is $2 \neq 2$). Remember: The contrapositive lets us think about pairs $(a, b)$ and $(b, a)$ where $a \neq b$. Dec 30, 2016 at 21:50
• But if the left hand side is false doesn't that means that the entire statement is true in this case? Dec 30, 2016 at 21:57
• Right! So whenever $a = b$, the statement $$a \neq b \implies \text{not} (aRb \text{ and } bRa)$$ is true, and that statement is equivalent to the "usual" definition of antisymmetry. So the presence of pairs $(a, a)$ doesn't "violate" antisymmetry, even when formulated in this contrapositive way. Dec 30, 2016 at 22:00
• So the "working definition" that I like for antisymmetry is this: If $a \neq b$ and $aRb$, then it is not the case that $bRa$; or, as ordered pairs, when $a \neq b$ and $(a, b) \in R$, then $(b, a) \not\in R$. It just lets you scan relations (given as sets!) quickly to determine if there are any "symmetric" pairs (if there are any, your relation is not antisymmetric; if there aren't any, it is). It's just the most intuitive formulation for antisymmetry in general, for me. Dec 30, 2016 at 22:08