• Home
• Foundations
Thomas A. Alspaugh
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.