6
$\begingroup$

Partial orders can be thought of as a set $S$, and a partial relation on that set, $\le$. If a greatest lower bound and least upper bound exist for any subset of $S$, the poset defines a lattice.

The sum operator can be defined on lattices as follows:

$$ L_1 + L_2+...+ L_n = \{ (i, x_i)\ \vert \ x_i \in L_i \backslash \{\bot, \top \}\} \cup \{ \bot, \top\} $$

where $\top$ and $\bot$ are the trivial greatest and least elements, respectively, when dealing with lattices over finite sets. This can be very elegantly visualized as the lattices lined up, with both top and bottom joined at a single point, respectively.

I now have a question in two parts.

1) Is there is an easy way to visually understand the Lattice product, as defined by:

$$ L_1 \times L_2\times\ ...\times\ L_n = \{(x_1, x_2, ..., x_n)\ \vert \ x_i \in L_i\} $$

2) According to defintions, $\le$ and g.u.b and l.u.b are defined point-wise on lattice products.

Computing $\le$ pointwise makes sense to me, but pointwise bounds has my head creaking. Could someone provide some intuition behind this, or otherwise help my understanding?

$\endgroup$

1 Answer 1

7
$\begingroup$

Whether or not this is easy depends on $n$ and the lattices involved.

For $n\leq 2$, the answer is yes, (especially if the lattices are bounded) there is an easy way to visualize direct product of two lattices (see explanation below). For $n=3$, as long as the lattices are not too complicated, it's fairly easy to visualize the direct product. For larger $n$, unless you are very good at thinking in $n>3$ spatial dimensions, it seems hard to draw a good Hasse diagram for the direct product of lattices by hand. Of course, there are computer programs which do it for you, like the UA Calculator, and Ralph Freese (author of UACalc) has a paper about automated lattice drawing available here.

I'll explain how to visualize direct products of lattices in the easy cases I mentioned above. Let's start with the smallest non-trivial example. Let $L_1$ be the two element lattice with universe $\{x_0, x_1\}$, and $x_0 < x_1$. We sometimes say $L_1 \cong \mathbf 2$. Let $L_2$ be another two element lattice with universe $\{y_0, y_1\}$, and $y_0<y_1$. Then $L_1 \times L_2 \cong \mathbf 2 \times \mathbf 2$ is just the lattice whose Hasse diagram looks like a diamond. The top is the element $(x_1, y_1)$. The bottom is $(x_0, y_0)$. The other elements $(x_0, y_1)$ and $(x_1, y_0)$ are incomparable.

Now lets look at a slightly more complicated example. Consider $L_1 \times L_2 \times L_3$, where $L_3 \cong \mathbf 3$ is the three element chain. The Hasse diagram in this case is the lattice on the left in the figure below. You can see in this case how the figure is just the diamond (that represents $L_1 \times L_2$) crossed with the three element chain (so there are three diamonds, as you move up and to the right in the diagram).

More generally. Take two arbitrary bounded lattices $L_1$ and $L_2$. You can visualize the direct product $L_1 \times L_2$ just as we did with the $\mathrm 2 \times \mathrm 2$ example, except now there may be other points $(x,y)$ in the middle of the diagram, where $x\in L_1$ and $y\in L_2$.

enter image description here

As for the second part of your question, point-wise simply means coordinate-wise; i.e. $(x_1, \dots, x_n) \leq (y_1,\dots, y_n)$ iff $x_i \leq y_i$ for each $i$. It should be clear that this is the order being used in the figures above.

$\endgroup$
2
  • $\begingroup$ Thank you - The system decided to stop sending me mails when my questions are answered for one reason or the other, so that explains the delay! About the second part of my question, I have since then been reading a little more on it. My next hurdle is the 'map lattice' concept - I'll mull it over a little more before posting again : ) $\endgroup$
    – justkris
    Feb 21, 2012 at 18:42
  • $\begingroup$ @Kris Sure, no problem. As for the second part of your question, I will add to my answer to address it. $\endgroup$ Feb 21, 2012 at 19:15

You must log in to answer this question.

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