1 Basic definitions
A complete lattice is a partially ordered set in which arbitrary families of elements admit both a least upper bound and a greatest lower bound. In practice, this means that the order is rich enough to support not only finite lattice operations, but also infinite ones. Complete lattices form one of the most important settings for order-theoretic constructions, especially those involving limits, closure operations, and fixed points.
1.1 Partially ordered sets
A partially ordered set, or poset, is a set equipped with a relation that is reflexive, antisymmetric, and transitive. The relation is usually written as ≤. In such a structure, some pairs of elements may be comparable, while others need not be. Posets provide the underlying language for lattice theory, since joins and meets are defined relative to the order.
1.2 Supremum and infimum
Given a subset of a poset, an upper bound is an element that lies above every member of the subset, and a lower bound lies below every member. The supremum, or least upper bound, is the smallest among the upper bounds when it exists. Dually, the infimum, or greatest lower bound, is the largest among the lower bounds. These notions generalize maximum and minimum, but they do not require the relevant element to belong to the subset.
1.3 Definition of a complete lattice
A complete lattice is a poset in which every subset has a supremum and an infimum. The empty subset is included, so a complete lattice necessarily has a least element and a greatest element. This definition strengthens that of an ordinary lattice, where only binary joins and meets are required.
1.3.1 Arbitrary joins
For any collection of elements, their join is the least element that dominates all of them. Arbitrary joins allow one to combine infinitely many pieces of information in a single order-theoretic operation. In a complete lattice, joins exist for all subsets, including infinite and empty ones.
1.3.2 Arbitrary meets
The meet of a subset is the greatest element below every member of the collection. As with joins, the requirement applies to all subsets without restriction. Arbitrary meets are the dual notion to arbitrary joins and often encode intersection-like behavior.
1.4 Examples and non-examples
Complete lattices appear in many familiar settings, but not every lattice is complete. Some structures naturally support all joins and meets, while others fail for infinite families. The distinction is often determined by whether the underlying order has enough limiting elements to summarize arbitrary collections.
1.4.1 Power set lattices
For any set X, the collection of all subsets of X ordered by inclusion is a complete lattice. The join of any family of subsets is their union, and the meet is their intersection. This is one of the simplest and most fundamental examples.
1.4.2 Boolean algebras
Every Boolean algebra is a lattice with complements, and many standard examples are complete lattices as well. When a Boolean algebra is complete, arbitrary unions and intersections are available in the corresponding order structure. Such lattices are common in measure theory, logic, and set-theoretic constructions.
1.4.3 Finite lattices
Every finite lattice is complete. Since only finitely many elements exist, any subset has a join and meet that can be computed by repeated binary operations. This makes finite lattices a basic source of examples and a convenient testing ground for general results.
1.4.4 Lattices that are not complete
Some lattices fail to be complete because certain infinite subsets lack a supremum or infimum. For example, a lattice may support finite joins and meets but not arbitrary ones. Such cases show that completeness is a stronger and genuinely additional property, not automatic from the lattice axioms.
2 Fundamental properties
Complete lattices have several structural features that make them especially flexible. The existence of arbitrary joins and meets forces the presence of extremal elements, supports dual interpretations, and yields strong monotonicity properties for order-preserving maps. These properties are frequently used in both pure and applied contexts.
2.1 Top and bottom elements
Every complete lattice contains a greatest element, often called the top element, and a least element, called the bottom element. The top element is the join of the empty set, while the bottom element is the meet of the empty set. These elements serve as universal bounds for the entire lattice.
2.2 Duality
Many statements about complete lattices have dual forms obtained by reversing the order relation. This symmetry allows one to transfer results about joins to meets and vice versa. Duality is a pervasive organizing principle in lattice theory.
2.2.1 Order dual of a complete lattice
The order dual of a complete lattice is obtained by reversing the order. Because arbitrary joins in the original order become arbitrary meets in the reversed order, the dual of a complete lattice is again complete. This simple observation often reduces proofs to one-sided arguments.
2.2.2 Self-dual examples
Some complete lattices are isomorphic to their order duals. Power set lattices are a classical instance when paired with set complementation. Self-duality is especially useful because it allows join-based and meet-based statements to be treated in parallel.
2.3 Closure under arbitrary intersections and unions
In many complete lattices, especially those realized as families of subsets, arbitrary intersections and unions remain within the structure. This closure behavior reflects the existence of meets and joins in concrete set-theoretic terms. It is one reason complete lattices are so closely connected with closure systems.
2.4 Monotone maps on complete lattices
A monotone map preserves the order: if x ≤ y, then f(x) ≤ f(y). Such maps are central in the study of complete lattices because they interact well with joins, meets, and fixed points. Even when they do not preserve all lattice operations, monotonicity often suffices for strong existence theorems.
3 Substructures and special classes
Complete lattices admit a range of substructures and refinements. Some subclasses are defined by algebraic identities, while others are characterized by the behavior of special elements or generating sets. These distinctions help organize the broad variety of complete lattices encountered in mathematics.
3.1 Sublattices
A sublattice is a subset closed under finite joins and finite meets. It inherits a lattice structure from the ambient lattice, though it need not be complete. Sublattices are useful for isolating smaller order-theoretic fragments that retain essential algebraic behavior.
3.2 Complete sublattices
A complete sublattice is a sublattice that is also closed under arbitrary joins and meets taken in the larger lattice. Such substructures preserve completeness rather than merely finite lattice operations. They often arise as fixed-point sets, closure systems, or families defined by universal properties.
3.3 Distributive complete lattices
A complete lattice is distributive when finite meets distribute over finite joins, and in many contexts this behavior extends compatibly with arbitrary operations. Distributive complete lattices include many familiar order structures built from sets and logical propositions. They are especially important in representation theorems and semantic applications.
3.4 Modular complete lattices
Modular complete lattices satisfy the modular identity, a weakening of distributivity that still imposes substantial structure. This class includes lattices arising from subspaces of vector spaces and related algebraic objects. Completeness adds the ability to take arbitrary intersections and closed spans in the same framework.
3.5 Atomistic and coatomistic lattices
An atomistic lattice is one in which every element is the join of atoms, where an atom is a minimal non-bottom element. Dually, a coatomistic lattice is generated by coatoms, the maximal elements below the top. These properties describe how complicated elements can be assembled from simple building blocks.
4 Morphisms
Maps between complete lattices are often studied according to how much order-theoretic structure they preserve. Because arbitrary joins and meets are available, one can ask for stronger compatibility conditions than in ordinary lattice theory. Such morphisms are central to categorical and semantic interpretations.
4.1 Complete lattice homomorphisms
A complete lattice homomorphism is a map that respects the full family of join and meet operations. These maps are the natural notion of structure-preserving morphism for complete lattices. They are typically required to preserve arbitrary suprema, arbitrary infima, or both.
4.1.1 Preservation of joins
A join-preserving map sends the supremum of any subset to the supremum of its image, provided the relevant joins exist in the source and target. Such maps are often called suprema-preserving or join-continuous. They play a major role in fixed-point theory and domain theory.
4.1.2 Preservation of meets
A meet-preserving map respects arbitrary infima. These maps are sometimes described as infima-preserving or meet-continuous. In many contexts, they are the dual counterparts of join-preserving maps and arise from the same abstract patterns.
4.2 Galois connections
A Galois connection consists of two monotone maps between ordered sets that stand in an adjoint relationship. In complete lattices, Galois connections frequently connect closure operators with their generating data. They provide a powerful mechanism for translating between different order structures.
4.3 Adjoints
Adjoints are maps that satisfy a universal comparison property relative to another map. In complete lattices, adjunctions are especially well behaved and often determine preservation properties automatically. They are a central tool in categorical order theory.
4.3.1 Left adjoints
A left adjoint typically preserves arbitrary joins. It captures the idea of a map that freely generates the least output compatible with the order. Left adjoints are common in constructions that extend data while maintaining minimality.
4.3.2 Right adjoints
A right adjoint typically preserves arbitrary meets. It expresses a maximality condition and often corresponds to a restriction or approximation process. Right adjoints are dual to left adjoints and frequently appear in closure and semantics problems.
5 Fixed-point theory
Complete lattices provide the natural setting for fixed-point theorems because arbitrary joins and meets allow one to define extremal solutions to monotone equations. This makes them indispensable in logic, semantics, and abstract computation. Fixed-point theory is one of the main reasons complete lattices are so widely studied.
5.1 Knaster–Tarski theorem
The Knaster–Tarski theorem states that every monotone self-map on a complete lattice has a complete lattice of fixed points. In particular, there exist least and greatest fixed points. This theorem is a cornerstone of order-theoretic semantics and many related areas.
5.2 Least fixed points
The least fixed point is the smallest element x such that f(x) = x. It often represents the minimal solution to a recursive specification or inductive definition. In complete lattices, least fixed points can frequently be obtained by taking the join of all pre-fixed points or by iterating from the bottom element.
5.3 Greatest fixed points
The greatest fixed point is the largest solution of the equation f(x) = x. It commonly models coinductive or persistent behavior. In a complete lattice, it can be characterized dually as the meet of all post-fixed points or as a limit of descending approximations.
5.4 Iteration and transfinite construction
When simple iteration does not stabilize after finitely many steps, transfinite methods may be used. One forms ascending or descending chains indexed by ordinals until a fixed point is reached. This approach is especially important for large or highly nonconstructive complete lattices.
6 Constructions and examples
Many complete lattices arise from standard constructions that combine sets, functions, or closure conditions. These examples show how completeness can be built into a structure from the beginning, rather than deduced afterward. They also illustrate the breadth of the theory.
6.1 Power set construction
The power set of a set, ordered by inclusion, is the prototypical complete lattice. Joins are unions and meets are intersections. This construction is foundational because it provides a concrete model for arbitrary suprema and infima.
6.2 Product lattices
A product of complete lattices is again complete when ordered componentwise. Joins and meets are computed coordinate by coordinate. This makes products a convenient way to assemble large complete lattices from simpler factors.
6.3 Function lattices
The set of all functions from one set to a complete lattice, ordered pointwise, is itself a complete lattice. Joins and meets are taken pointwise across the codomain. Function lattices are common in semantics, where elements represent valuations, states, or approximations.
6.4 Lattices of subsets ordered by inclusion
Families of subsets closed under union and intersection often form complete lattices under inclusion. Such structures include many natural collections of geometric, algebraic, or combinatorial objects. They are often easier to analyze because the order relation has a direct set-theoretic interpretation.
6.5 Closure systems and Moore families
A closure system, or Moore family, is a collection of subsets closed under arbitrary intersections. Ordered by inclusion, it forms a complete lattice in which meets are intersections and joins are obtained by closure of unions. These systems provide a canonical representation of many complete lattices.
7 Applications
Complete lattices are used across mathematics and theoretical computer science because they support robust notions of approximation, closure, and recursion. Their abstract properties translate into practical tools in several disciplines. The following areas illustrate their broad influence.
7.1 Domain theory
In domain theory, complete or related lattice-like structures are used to model computation and approximation. They help formalize the idea that information can grow by successive refinement. Order-theoretic completeness is crucial for defining semantic domains with stable limits.
7.2 Logic and semantics
Complete lattices provide semantics for logical systems in which propositions or predicates are ordered by strength or inclusion. They also support interpretation of quantifiers, modalities, and truth values in generalized logical frameworks. Many semantic constructions become natural lattice operations in this setting.
7.3 Fixed-point semantics in computer science
Recursive definitions, program meanings, and state-transition systems are often interpreted via least or greatest fixed points in complete lattices. This viewpoint gives precise mathematical meaning to iterative behavior. It also underlies several formal methods for reasoning about programs.
7.4 Formal concept analysis
Formal concept analysis studies relations between objects and attributes by organizing them into concept lattices. These lattices are often complete, allowing systematic movement between extents and intents. The resulting structure captures hierarchical relations among descriptions of data.
7.5 Algebra and topology
Complete lattices occur in algebra through ideals, subalgebras, and closure operators, and in topology through open and closed set systems. They provide a unifying language for operations that behave like union, intersection, span, or closure. Their versatility makes them a recurring tool across structural mathematics.