CPOs and Lattices thomasalspaugh.org/pub/fnd/lattice.html

# 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