Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
$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$.
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!
