0
$\begingroup$

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

$\endgroup$

5 Answers 5

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ But what about (1,2) (1,3) ... 2 doesn't divide 1 and 3 doesn't divide 1. What do I do with those? $\endgroup$
    – Ray Rutzer
    Dec 30, 2016 at 21:44
  • $\begingroup$ @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). $\endgroup$
    – J.G.
    Dec 30, 2016 at 23:39
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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!

$\endgroup$
8
  • $\begingroup$ But what about (1,1), (2,2) ... wouldn't that violate that clause? $\endgroup$
    – Ray Rutzer
    Dec 30, 2016 at 21:48
  • $\begingroup$ 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$. $\endgroup$
    – pjs36
    Dec 30, 2016 at 21:50
  • $\begingroup$ But if the left hand side is false doesn't that means that the entire statement is true in this case? $\endgroup$
    – Ray Rutzer
    Dec 30, 2016 at 21:57
  • $\begingroup$ 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. $\endgroup$
    – pjs36
    Dec 30, 2016 at 22:00
  • $\begingroup$ 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. $\endgroup$
    – pjs36
    Dec 30, 2016 at 22:08

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.