Proof of glb and lub of lexicographic product of poset

Question

Is there a book, or a paper where the lexicographic glb and lub are proven commutative, associative, idempotent and absorbing. I have already proven this, but would like to check proofs, and a short citation in a page limited paper, is better than a list of long proofs. Thank you.

Given 2 complete lattices $L_1 = (A_1,\vee_1,\wedge_1)$ and $L_2 = (A_2,\vee_2,\wedge_2)$, we form the lexicographic product $(A_1\times A_2, \vee, \wedge)$ where

$$ (a,b) \vee (a',b') = \left\{ \begin{aligned} (a,b) & \hbox{ if $a' < a$} \\ (a'b') & \hbox{ if $a < a'$} \\ (a,b \vee_2 b') & \hbox{ if $a = a'$} \\ (a \vee_1 a',0_2) & \hbox{ if $a || a'$} \end{aligned}\right. $$

$$ (a,b) \wedge (a',b') = \left\{ \begin{aligned} (a,b) & \hbox{ if $a < a'$} \\ (a',b') & \hbox{ if $a' < a$} \\ (a,b \wedge_2 b') & \hbox{ if $a = a'$} \\ (a \wedge_1 a',1_2) & \hbox{ if $a || a'$} \end{aligned}\right. $$

Answer 1

Surely this information is in Ralph Mackenzie's book on universal algebra.

But let me just sketch some quick proofs. First, note that you were right to consider complete lattices, since in general the lexicographic order on lattices may not be a lattice order, as I explain in this MO answer. So we suppose that $L_1$ and $L_2$ are complete lattices.

My suggestion is that you focus on the order, rather than on the algebraic operations as you defined them. That is, we can define the lexical order on the product $L_1\times L_2$, and then prove that this order is a lattice order. The lexical order is just the dictionary order, placing (a,b) below (a',b') just in case $a\leq a'$ or $a=a'$ and $b\leq b'$. It is not difficult to prove that this order is reflexive, transitive and antisymmetric, so it is indeed a partial order. Furthermore, when the lattices are complete, it is a lattice order (that is, has lub's and glb's). To see this, consider two points $(a,b)$ and $(a',b')$. The lub of $(a,b)$ and $(a',b')$ is easily seen to be $(lub(a,a'),0)$, if $a$ and $a'$ are incomparable, since this is an upper bound, and any other upper bound must be at least as big as this. The lub of $(a,b)$ and $(a',b')$ is clearly $(a',b')$, if $a\lt 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 \lt a'$; and it is $(a,glb(b,b'))$, if $a = a'$. These answers amount to the definition of $\vee$ and $\wedge$ you gave in your question.

The essence of this suggestion is that you should derive the operations you mentioned as expressing the right lub and glb properties for the lexical order, as a consequence of the order, rather than defining those operations first and then trying to prove it has the lattice algebraic properties.

Now, knowing that this is a lattice order, we may easily derive that lub and glb are commutative and associative, etc., since these properties hold in any lattice order. That is, once you get the order correct, the algebraic properties follow for free:

• Note that $glb(a,b)$ depends only on the set {a,b} and not on the pair $\langle a,b\rangle$, so we clearly get commutativity $glb(a,b)=glb(b,a)$.
• The same is true for $lub(a,b)$, for the same reason.
• These operations are associative, since if d=glb(a,glb(b,c)), then d is an lower bound of a and glb(b,c), and therefore a lower bound of all three a,b,c. Thus, it is an lower bound of glb(a,b) and c and so is at most glb(glb(a,b),c). The converse is similar.
• One can show lub is associative in a very similar manner.
• I'm not sure what you mean by idempotent, but clearly glb(a,a)=a, since obviously a is the least upper bound of a and a.
• A stronger result would be to show that the lexical order on $L_1\times L_2$ is also a complete lattice order, which it is, since any subset $X\subset L_1\times L_2$ has a lub in the product simply by taking the lub's in the first coordinate, and then glb among elements of the second coordinate that work with that first element. This argument does not work when the lattices are not complete, unless $L_1$ is linear.

Answer 2

I don't know a reference that does it this way. What is the advantage over showing that in the lexicographic product poset every subset has a sup and inf, and for two-element sets, sup and inf satisfy these formulas?