Complete lattice

related topics
{math, number, function}
{line, north, south}

In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet). Complete lattices appear in many applications in mathematics and computer science. Being a special instance of lattices, they are studied both in order theory and universal algebra.

Complete lattices must not be confused with complete partial orders (cpos), which constitute a strictly more general class of partially ordered sets. More specific complete lattices are complete Boolean algebras and complete Heyting algebras (locales).

Contents

Formal definition

A partially ordered set (L, ≤) is a complete lattice if every subset A of L has both a greatest lower bound (the infimum, also called the meet) and a least upper bound (the supremum, also called the join) in (L, ≤).

The meet is denoted by \bigwedge A, and the join by \bigvee A.

Note that in the special case where A is the empty set the meet of A will be the greatest element of L. Likewise, the join of the empty set yields the least element. Since the definition also assures the existence of binary meets and joins, complete lattices do thus form a special class of bounded lattices.

More implications of the above definition are discussed in the article on completeness properties in order theory.

Full article ▸

related documents
Infinity
Denotational semantics
Stone–Čech compactification
Numerical analysis
Kernel (algebra)
Cardinal number
Series (mathematics)
Gaussian elimination
Newton's method
Integration by parts
Functor
Direct sum of modules
Sequence alignment
Boolean satisfiability problem
Riemann zeta function
Ruby (programming language)
List of trigonometric identities
Huffman coding
Russell's paradox
Pascal's triangle
Principal components analysis
Lua (programming language)
Johnston diagram
Entropy (information theory)
Forcing (mathematics)
Logic programming
Hash function
Cauchy sequence
Groupoid
Interval (mathematics)