Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
The last two lines here are quite mysterious to me. I suggest you try to edit this to make it more readable, and improve the notation. –  Dan Ramras May 3 '10 at 5:52
    
I've reformatted the original -- hopefully I haven't introduced any errors. Could the original questioner please check and let us know if the formulas above are still correct? –  Yemon Choi May 3 '10 at 7:04
    
For the last clause of meet, I would expect to get $(a \wedge_1 a', 1_2)$ –  Gerald Edgar May 3 '10 at 12:33
    
Arr, if I knew you could put TeX I would of just gone straight for that. Cheers, also corrected the meet. –  GrahamJenson May 3 '10 at 20:46

2 Answers 2

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.
share|improve this answer
    
I was the person who asked the other question about lexicographic order that you answered. Sir, you get my respect for your help. –  GrahamJenson May 3 '10 at 20:54
    
As far as MO is concerned, that was a different Unregistered User with the same name as yours... That other Graham has 21 reputation, whereas this one only has 11. –  Gerald Edgar May 3 '10 at 23:09

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?

share|improve this answer
    
Gerald, I see (after posting my answer) that we have both made the same suggestion... –  Joel David Hamkins May 3 '10 at 12:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.