4
$\begingroup$

I am a little bit confused as to how I would draw a lattice for the set $S= \{1,2,3,4,6,9,12,18\} $when it is partially ordered by divisibility.

I was able to prove that it has a greatest lower bound, and a least upper bound for all elements $x,y \in S$. I believe my proof is correct, and by having these two bounds, the set is therefore a lattice.

I am just a bit confused as to how I would draw it.

$\endgroup$
2
$\begingroup$

Just how are you confused about drawing the lattice? Here's how I did it. I started by putting 1 at the bottom, since it's the least element of the lattice, it divides everything.

Since 2 and 3 are divisible by 1, but not by each other, I put 2 one cm northwest of 1, I put 3 one cm northeast of 1, and draw lines from 2 to 1 and from 3 to 1.

Since 6 is divisible by everything so far, I put 6 one cm NE of 2 (and one cm NW of 3) and draw lines from 6 to 2 and from 6 to 3. Of course I don't draw a line from 6 to 1.

I now have a diamond, with 1 at the bottom, 2 and 3 on the sides, 6 at the top.

Next I look at 4: divisible by 1 and 2, not divisible by 3 or 6. So I put 4 one cm NW of 2, and draw a line from 4 to 2.

12 is divisible by everything so far. I put 12 one cm NE of 4 (and NW of 6), and draw lines from 12 to 4 and from 12 to 6.

9 is divisible by 1 and 3, but not divisible by 2, 4, 6, or 12. I put 9 one cm NE of 3, and draw a line from 9 to 3.

18 is divisible by 6 and 9, and therefore also by 1, 2, and 3; but 18 is not divisible by 4 or 12. I put 18 one cm NE of 6 (NW of 9) and draw lines from 18 to 6 and 9.

That's the diagram. I'd draw it for you if I knew how.

Looking at the diagram, it's easy to see that it's a lower semilattice, meaning that any two elements have a greatest lower bound.

It's also easy to see that it's not an upper semilattice (and therefore not a lattice); the pairs {4,9}, {4,18}, {9,12}, and {12,18} do not have least upper bounds.

By the way, what did you think was the least upper bound of 12 and 18? Maybe there was a typo in your question, and 36 was supposed to be an element of S?

$\endgroup$
  • $\begingroup$ Wow, you are correct. I was looking at multiple sets, and a 36 was in one set, but not for this one. But the description how to draw it (even though it wasn't a lattice) was helpful. Thanks. $\endgroup$ – Tesla Nov 1 '13 at 17:25
0
$\begingroup$

"Ordered by divisibility" means that you have $y$ somewhere above $x$ in the lattice whenever $y$ is a multiple of $x$. So for example, there should be an upward path in the lattice from 4 to 12, because 12 is a multiple of 4. But there should not be a path upward from 3 to 4, or from 4 to 3, because neither is a multiple of the other.

A good way to proceed is:

  1. identify the maximal elements of the lattice, which are the elements that have nothing else above them.
  2. Put those in a top row.
  3. Then cross those out from your list of elements
  4. Find the next highest elements and put them in a row underneath the maximal elements.
  5. Draw lines from those to the appropriate maximal elements.
  6. Repeat this until you have added all the elements in the proper places.

Does this help?

$\endgroup$

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.