Return to Answer

The usual order to put on the product of two lattices is the product order, rather than the lexical order.

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

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

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

However, if the lattices are complete, then the lexical order is a lattice order. In this case, the lub((a,b),(a',b')) = (c,d), where c = lub(a,a') and d is least such that (c,d) is an upper bound of (a,b) and (a',b'). A similar idea works for glb. Also, one can show that the product lattice in the lexical order is also complete, for is X is any subset of the product, 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 again to be least such that (c,d) is an upper bound.

In fact, if we are careful in the argument, we don't need completeness, but only boundedness (meaning that L has a least and greatest element). We didn't use any extra fact about K and for L all we need is that it has a minimal and maximal element; one needs to argue separate cases depending on whether the first coordinates a and a' are comparable or not. This appears to establish:

• If L is bounded, 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.

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.

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:

• 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.

The usual order to put on the product of two lattices is the product order, rather than the lexical order.

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

With the product order, one should simply take lub or glb separately in each coordinate, and it is not difficult to see that this is a latice 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 L and K are lattices, such that L is not a linear order and K has no least element. In this case, the lexical order on L x K is not a lattice order. Let a and b be elements of L that are incomparable, and let c be any element of L. I claim that (a,c) and (b,c) have no least upper bound in the lexical order. To see this, suppose that (x,y) is the least upper bound of (a,c) and (b,c). It must be that a and b are both ≤ x, and so lub(a,b) ≤ x. Since a and b are incomparable, they are both strictly less than lub(a,b). Thus, any element of the form (lub(a,b),y) is an upper bound. But there is no least such element, since L has no least element.

However, if the lattices are complete, then the lexical order is a lattice order. In this case, the lub((a,b),(a',b')) = (c,d), where c = lub(a,a') and d is least such that (c,d) is an upper bound of (a,b) and (a',b'). A similar idea works for glb. Also, one can show that the product lattice in the lexical order is also complete, for is X is any subset of the product, 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 again to be least such that (c,d) is an upper bound.

The usual order to put on the product of two lattices is the product order, rather than the lexical order.

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

With the product order, one should simply take lub or glb separately in each coordinate, and it is not difficult to see that this is a latice 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 L and K are lattices, such that L is not a linear order and K has no least element. In this case, the lexical order on L x K is not a lattice order. Let a and b be elements of L that are incomparable, and let c be any element of L. I claim that (a,c) and (b,c) have no least upper bound in the lexical order. To see this, suppose that (x,y) is the least upper bound of (a,c) and (b,c). It must be that a and b are both ≤ x, and so lub(a,b) ≤ x. Since a and b are incomparable, they are both strictly less than lub(a,b). Thus, any element of the form (lub(a,b),y) is an upper bound. But there is no least such element, since L has no least element.

However, if the lattices are complete, then the lexical order is a lattice order. In this case, the lub((a,b),(a',b')) = (c,d), where c = lub(a,a') and d is least such that (c,d) is an upper bound of (a,b) and (a',b'). A similar idea works for glb. Also, one can show that the product lattice in the lexical order is also complete, for is X is any subset of the product, 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 again to be least such that (c,d) is an upper bound.

In fact, if we are careful in the argument, we don't need completeness, but only boundedness (meaning that L has a least and greatest element). We didn't use any extra fact about K and for L all we need is that it has a minimal and maximal element; one needs to argue separate cases depending on whether the first coordinates a and a' are comparable or not. This appears to establish:

Theorem. Suppose that K and L are lattices.

• If L is bounded, 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.

The usual order to put on the product of two lattices is the product order, rather than the lexical order. With the product order, one should simply take lub or glb separately in each coordinate, and it is not difficult to see that this is a latice 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 L and K are lattices, such that L is not a linear order and K has no least element. In this case, the lexical order on L x K is not a lattice order. Let a and b be elements of L that are incomparable, and let c be any element of L. I claim that (a,c) and (b,c) have no least upper bound in the lexical order. To see this, suppose that (x,y) is the least upper bound of (a,c) and (b,c). It must be that a and b are both ≤ x, and so lub(a,b) ≤ x. Since a and b are incomparable, they are both strictly less than lub(a,b). Thus, any element of the form (lub(a,b),y) is an upper bound. But there is no least such element, since L has no least element.

However, if the lattices are complete, then the lexical order is a lattice order. In this case, the lub((a,b),(a',b')) = (c,d), where c = lub(a,a') and d is least such that (c,d) is an upper bound of (a,b) and (a',b'). A similar idea works for glb. Also, one can show that the product lattice in the lexical order is also complete, for is X is any subset of the product, 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 again to be least such that (c,d) is an upper bound.

The usual order to put on the product of two lattices is the product order, rather than the lexical order.

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

With the product order, one should simply take lub or glb separately in each coordinate, and it is not difficult to see that this is a latice 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 L and K are lattices, such that L is not a linear order and K has no least element. In this case, the lexical order on L x K is not a lattice order. Let a and b be elements of L that are incomparable, and let c be any element of L. I claim that (a,c) and (b,c) have no least upper bound in the lexical order. To see this, suppose that (x,y) is the least upper bound of (a,c) and (b,c). It must be that a and b are both ≤ x, and so lub(a,b) ≤ x. Since a and b are incomparable, they are both strictly less than lub(a,b). Thus, any element of the form (lub(a,b),y) is an upper bound. But there is no least such element, since L has no least element.

However, if the lattices are complete, then the lexical order is a lattice order. In this case, the lub((a,b),(a',b')) = (c,d), where c = lub(a,a') and d is least such that (c,d) is an upper bound of (a,b) and (a',b'). A similar idea works for glb. Also, one can show that the product lattice in the lexical order is also complete, for is X is any subset of the product, 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 again to be least such that (c,d) is an upper bound.