0
$\begingroup$

Here is the question I am currently working on (screenshot):



I'd appreciate some suggestions/guidance for part (a), proving that $D_n$ is a partial order.

Reflexive: Let $x \in \mathbb{Z}$ such that $xD_nx$.

Let $n$ be a positive integer such that $x \mid x$ can be restated as $x=xn$. Thus, $xD_nx$ and $D_n$ is reflexive.

Antisymmetric: Let $x,y \in \mathbb{Z}$ such that $xD_ny$ and $yD_nx$.

Thus we have that $x\mid y$ and $y \mid x$. Let $k,j \in \mathbb{Z}$ such that $xk=y$ and $yj=x$. By substitution, we have that $x=xjk$ and $y=yjk$. This implies that $x=y$ and that the relation is antisymmetric.

^I definitely feel like there are some holes here, and this is probably not correct.

Transitive: Let $x,y,z \in \mathbb{Z}$ such that $xD_ny$ and $yD_nz$.

Let $m,n \in \mathbb{Z}$ such that $xm=y$ and $yn=z$.

^ This is where I am stuck for transitivity. Generally I would do some type of addition to get to reach the proper conclusion, but I don't think that would work in this case.

Thanks for the guidance! As for part (b), I am comfortable drawing Hasse diagrams, with the exception that I'm not sure how to plug in these numbers for $S$ into the relation.

I'm terrible at these relation questions, and working through a review for my final next week. Up until this point, I have been mostly okay with the intro/proofs class. If anyone has any good suggestions for sites/resources, I'd appreciate it. I haven't found anything too great online.

$\endgroup$
2
  • $\begingroup$ For anti-symmetric, just being a bit nit-picky. You might want to use the fact that they are POSITIVE integers. Because jk = (-1)*(-1) works just fine. $\endgroup$ Jul 22 '15 at 5:29
  • $\begingroup$ @DarthAlpha Good suggestion, thanks. I am very much okay with nit-picky. My prof isn't great, albeit also a nit-picker. $\endgroup$ Jul 22 '15 at 5:30
1
$\begingroup$

You are done though! $$xm=y, yn=z \implies xmn= z \implies x|z \implies x D_n z$$

Substitution, you were doing so well.

$\endgroup$
1
  • $\begingroup$ Ughhh, I am such a derp. Thank you. I am such a needy math student and often worry that when it seems too easy that I'm not doing it correctly. Thanks for the help!!! $\endgroup$ Jul 22 '15 at 5:33
1
$\begingroup$

Reflexive: Does $xD_nx \forall x\in S$? Yes, because $x|x \implies x|x$.

Anti-symmetric: Does $xD_ny \land yD_nx \implies x=y$? Your proof here is correct, you might want to add $jk=1 \implies j=1,k=1$.

Transitive: Does $xD_ny \land yD_nz \implies xD_nz$? We have $jx=y$ and $ky=z$ so $z=ky=kjx \implies jkx=z \implies xD_nz$.

For the Hasse diagrams, I would use horizontal levels $\{1\}, \{2,3\}, \{4,6\}, \{8,12\}, \{24\}$ for $n=24$. $D_{16}$ is ordered.

$\endgroup$
3
  • $\begingroup$ Thanks. Sometimes I'm not sure when to add something like $j=1,k=1$ vs just having the reader see something that I might deem as "obvious". $\endgroup$ Jul 22 '15 at 5:37
  • $\begingroup$ people get stuck on 'x=xjk and y=yjk. This implies that x=y' $\endgroup$
    – JMP
    Jul 22 '15 at 5:39
  • $\begingroup$ I get stuck on it, and I'm not sure I've really convinced myself that $x=xjk$ and $y=yjk$ implies that $x=y$. $\endgroup$ Jul 22 '15 at 5:43

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.