Lattice completions

Given a partial ordering relation there are three types of elements that can occur in it defined below.

• Minimal element : an element with no predecessors
• Maximal element : an element with no successors
• Enclosed element : an element which is neither minimal nor maximal

Any partial ordering relation can be extended to form a lattice, by adding certain elements to it. These elements are going to be either minimal, maximal, or enclosed. Here is an example of a lattice completion that demonstrates each type of element, highlighted in blue added to a partial order:

A lattice, therefore, is in some sense a special type of partial order that has certain elements added to it. The dissimilarity or the distance of a given partial order to a lattice is the number of elements that need to be added to it in order to get a lattice. It is worth considering certain classes of partial orders that have bounded dissimilarity to a lattice.

• Difference zero : these are elements that are already lattices themselves
• Difference one : meet semilattices are missing only a maximal element, join semilattices are missing only a minimal element, and partial orders that are missing only an enclosed element
• Difference two : unique extrema partial orders that are missing only minimal and maximal elements but not any enclosed elements

The unique extrema partial orders which are missing only extremal elements and which are not missing any enclosed elements seem to be an interesting particular case. They are at most distance two from a lattice, and they include semilattices which are at most distance one, and lattices themselves as special cases.

The strongly unique extrema partial orders are a special case of unique extrema partial orders, which are closed under taking suborders. Forests are a special case of strongly unique extrema partial orders, and trees are a special case that are also semilattices. Locally total orders are a special case of forests that are both upper forests and lower forests. Total orders are a special class of locally total orders. All of these classes of partial orders are at most distance two from a lattice, making them relatively similar to lattices. Other classes can be distinguished by their similarity to lattices.