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

Sets

Relations

Correspondences

Ordered Sets

Lattices

Graphs

Powersets

Binary Strings

Logic

AIA

Greek

Glossary

Abstracts

Argument

Inquiry Cycle

Legal Relations

Presentations

Elicitation

Glossaries

Goals

i*

SCR

Tracing

Design Patterns

Javadoc

Java Packages

Java Types

Let P be an ordered set. P is a cpo iff for every pair x,y∈P, their LUB x∨y 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:

- Any powerset P, ordered by ⊆ is a cpo.
Every powerset contains ∅; ∅⊆S for every subset S∈P, 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.

Let P be an ordered set. P is a lattice iff for every pair x,y∈P, their LUB x∨y and GLB x∧y 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:

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

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

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