Lattice Completion
Vijay K. Garg · 2015
This chapter discusses complete lattices and presents ways in which complete lattices arise in mathematics and computer science. In particular, topped ∩–structures and closure operators give us complete lattices. The chapter talks about the notion of lattice completion which is useful for both finite and infinite posets. Finite lattices are always complete. Good structures tend to have multiple, equivalent ways of defining them. This is good in at least two ways. First, it provides multiple ways of characterizing the structure, hence offering more flexibility in doing proofs. In addition, it may provide efficient algorithms for dealing with the structures. The chapter studies two alternative definitions for complete lattices and then shows their equivalence. It describes the Dedekind–MacNeille completion of a poset. A useful technique to enumerate elements of the lattice is based on the DFS order. The DFS enumeration may result in exponential savings in space.