LUB and GLB on a lexicographically ordered complete lattice product

Question

I am trying to define the LUB and GLB on a product of lattices that are partially ordered lexicographically.

Is there any papers or help that I could read up on? I would particularly like proofs on those operators.

Answer 1

There are two natural orders to put on the product of two lattices, the product order and the lexical order.

• Product order: (a,b) ≤ (a',b') if and only if a ≤ a' and b ≤ b'
• Lexical order: (a,b) ≤ (a',b') if and only if a ≤ a', or a = a' and b ≤ b'

With the product order, which is commonly used, one should simply take lub or glb separately in each coordinate, and it is not difficult to see that this is a lattice order.

If one uses the lexical order, however, then the product of two lattices may not be a lattice at all.

To see this, suppose that K and L are lattices, such that K is not a linear order and L has no least element. In this case, the lexical order on K x L is not a lattice order. Let a and a' be elements of K that are incomparable, and let b be any element of L. I claim that (a,b) and (a',b) have no least upper bound in the lexical order. To see this, suppose that (x,y) is the least upper bound of (a,b) and (a',b). It must be that a and a' are both ≤ x, and so lub(a,a') ≤ x. Since a and a' are incomparable, they are both strictly less than lub(a,a'). Thus, any element of the form (lub(a,a'),y) is an upper bound. But there is no least such element, since L has no least element.

One can picture this easily, if you understand that the lexical order on K x L is the structure obtained by replacing each element of K with a copy of L. The points (a,b) and (a',b) lie in different copies of L, and there is a minimal copy of L above them at lub(a,a'), but there is no least element in that copy of L to serve as the lub of (a,b) and (a',b).

The same idea shows that if L does have a least and greatest element---call them 0 and 1---then K x L will be a lattice. The lub of (a,b) and (a',b') is simply (lub(a,a'),0), if a and a' are incomparable; it is (a',b'), if a < a'; and it is (a,lub(b,b')), if a = a'. Similarly, the glb of (a,b) and (a',b') will be (glb(a,a'),1), if a and a' are incomparable; it is (a,b), if a < a'; and it is (a,glb(b,b')), if a = a'.

In particular, if L is complete, then it will have a least and greatest element, and so K x L will be a lattice in the lexical order.

The argument also shows that if K is a linear order, then the incomparability cases above do not arise, and so K x L will be a lattice, even when L does not have least and greatest elements.

In summary, this establishes:

Theorem. Suppose that K and L are lattices.

• If L has a least and greatest element, then K x L is a lattice under the lexical order.
• If K is linearly ordered, then K x L is a lattice under the lexical order.
• In all other cases, K x L is not a lattice under the lexical order.

When both lattices are complete, then the lattice K x L under the lexical order is also complete. If X is any subset of K x L, then lub(X) will be (c,d), where c is the lub of the first coordinates of the pairs in X, and d is chosen to be least such that (c,d) is an upper bound.