CPOs and Lattices

Complete partial orders (cpos)

Let P be an ordered set.  P is a cpo iff for every pair x,yP, their LUB xy is an elements of P. 

Another way of saying the same thing:  an ordered set P is a cpo if it is closed under the cup operation. 

A cpo with a least element ⊥ is called a cpo with bottom.  Some authors use "cpo" to mean "cpo with bottom". 

A cpo is sort of a "half-lattice" (see below).  A lattice has LUBs and GLBs, a cpo has LUBs only. 

Examples:

  1. Any powerset P, ordered by is a cpo. 

    Every powerset contains ; S for every subset SP, so is a lower bound; and no other set is a lower bound for P, so is the GLB of the entire powerset P, and thus is ⊥.  See Figure 1. 

Lattices

Let P be an ordered set.  P is a lattice iff for every pair x,yP, their LUB xy and GLB xy are both elements of P. 

Another way of saying the same thing:  an ordered set P is a lattice if it is closed under the cap and cup operations. 

A lattice may have a top and/or a bottom, but an infinite lattice need not have either.  A finite lattice always has a top and a bottom. 

Examples: 

  1. Any powerset P is a lattice. 

    The LUB (GLB) of two sets X and Y is their union (intersection), and a powerset is closed under intersection (union), so P is a lattice.  P is finite and thus has a top and a bottom; ⊤ is the set S of which P is the powerset, and ⊥ is the empty set .  See ordered set Figure 2

  2. The integers are a lattice. 

    The LUB (GLB) of two integers x and y is the lesser (greater) of the two, and so is an integer; thus the integers are closed under LUB (GLB).  The integers are an infinite set and so need not have a top or a bottom, and in fact do not; there is no greatest or least integer.  See ordered set Figure 1

For further reading

B. A. Davey and H. A. Priestley.  Introduction to Lattices and Order.  Cambridge University Press, 2002. 

Valid XHTML 1.0 Strict
Valid CSS!
2010Feb24We20:58
Thomas A. Alspaugh