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$
    – Darth Alpha
    Jul 22, 2015 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$
    – Mr. Meeseeks
    Jul 22, 2015 at 5:30

2 Answers 2

Reset to default
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$
    – Mr. Meeseeks
    Jul 22, 2015 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$
    – Mr. Meeseeks
    Jul 22, 2015 at 5:37
  • $\begingroup$ people get stuck on 'x=xjk and y=yjk. This implies that x=y' $\endgroup$
    – JMP
    Jul 22, 2015 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$
    – Mr. Meeseeks
    Jul 22, 2015 at 5:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .