Fact-checked by Grok 2 weeks ago

Complete lattice

A complete lattice is a partially ordered set in which every subset has both a least upper bound, known as the supremum or join, and a greatest lower bound, known as the infimum or meet.^[1]^[2] This structure inherently possesses a greatest element, or top element, which is the supremum of the entire set, and a least element, or bottom element, which is the infimum of the entire set.^[1] Every complete lattice is a lattice, as the finite subsets admit joins and meets, and conversely, every finite non-empty lattice is complete.^[1] Key properties of complete lattices include their role in embedding arbitrary lattices into larger structures; specifically, every partially ordered set has a Dedekind–MacNeille completion, which is the smallest complete lattice containing it as an order-embedded sublattice.^[3] A cornerstone result is Tarski's fixed-point theorem, which asserts that if f is any monotone increasing function from a complete lattice to itself, then f has a least fixed point and a greatest fixed point, and the set of all fixed points of f itself forms a complete lattice under the original order.^[4] Examples of complete lattices abound in mathematics, such as the power set of any set X, ordered by inclusion, where arbitrary unions serve as joins and arbitrary intersections as meets.^[5] Another is the lattice of all subspaces of a vector space, ordered by inclusion, with joins as sums and meets as intersections.^[5] Complete lattices are foundational in order theory due to their connections to closure systems and fixed-point theorems, and they find applications in topology for modeling closure spaces, in mathematical logic for algebraic semantics, and in computer science for denotational semantics, where computational domains are often taken as complete lattices to ensure the existence of fixed points for semantic functions.^[6]^[7]

Definition

Basic definition

A partially ordered set, or poset, is a set L equipped with a binary relation \leq that is reflexive (x \leq x for all x \in L), antisymmetric (if x \leq y and y \leq x, then x = y), and transitive (if x \leq y and y \leq z, then x \leq z).^[8] In a poset, for any subset S \subseteq L, the supremum of S, denoted \sup S or \bigvee S, is the least upper bound of S, meaning it is the smallest element (with respect to \leq) that is greater than or equal to every element of S; equivalently, \sup S = \bigwedge \{ x \in L \mid \forall s \in S, s \leq x \}, where \bigwedge denotes the infimum (defined analogously below).^[1]^[9] The infimum of S, denoted \inf S or \bigwedge S, is the greatest lower bound of S, the largest element less than or equal to every element of S; dually, \inf S = \bigvee \{ x \in L \mid \forall s \in S, x \leq s \}.^[1]^[9] A complete lattice is a poset (L, \leq) in which every subset S \subseteq L (including the empty set and L itself) has both a supremum and an infimum in L.^[1]^[10] This completeness property implies the existence of a top element \top, the greatest element of L (i.e., \top \geq x for all x \in L), which serves as the infimum of the empty set: \inf \emptyset = \top; and a bottom element \perp, the least element of L (i.e., x \geq \perp for all x \in L), which is the supremum of the empty set: \sup \emptyset = \perp.^[1]^[10] Equivalently, a poset is a complete lattice if and only if every non-empty subset has a supremum and an infimum, since the bounds for the empty set and full set then follow from the overall order structure.^[1]^[10] In a complete lattice, the supremum and infimum operations generalize the binary join \vee and meet \wedge, which for two elements a, b \in L are defined as \sup\{a, b\} = a \vee b and \inf\{a, b\} = a \wedge b, respectively.^[9] Bounded lattices, which possess top and bottom elements but only require finite joins and meets, form a special case where completeness holds for finite subsets.^[9]

Variants of completeness

A complete join-semilattice, also known as a suplattice, is a partially ordered set (poset) in which every subset has a supremum, or join, but not necessarily an infimum for every subset. This structure generalizes the complete lattice by relaxing the requirement for arbitrary meets, allowing for posets where lower bounds may not always exist in full generality. In such a semilattice, the existence of all joins implies that the poset is directed complete, meaning every directed subset has a supremum, though the converse does not hold without additional conditions.^[11] Dually, a complete meet-semilattice, or inf lattice, is a poset where every subset has an infimum, or meet, but suprema may not exist for all subsets.^[11] These complete semilattices often lack universal bounds; for instance, a complete join-semilattice has a bottom element as the supremum of the empty set but may not have a top element, while dually a complete meet-semilattice has a top element but may not have a bottom element, distinguishing them from a full complete lattice.^[12] The operations in these structures are inherited from the poset order, and they form algebraic categories where homomorphisms preserve the respective infinite operations.^[13] A conditionally complete lattice is a lattice in which every non-empty subset that is bounded above has a least upper bound (supremum), and every non-empty subset that is bounded below has a greatest lower bound (infimum).^[14] This variant avoids the completeness for the empty set or unbounded subsets, making it suitable for structures like the real numbers under the usual order, where the empty set has no supremum but all non-empty bounded subsets do. Unlike full complete lattices, conditionally complete ones may not possess top or bottom elements, but they ensure existence of bounds only when conditioning assumptions hold, providing a weaker form of completeness that sidesteps issues with unbounded or empty collections.^[14] A complete sublattice of a complete lattice is a non-empty subset that is itself a complete lattice under the induced order, meaning it contains the supremum and infimum (computed in the ambient lattice) of every one of its non-empty subsets.^[15] This inheritance ensures that the sublattice preserves the completeness property without requiring the subset to be closed under all operations of the larger structure beyond those needed for its own subsets. For example, in the power set lattice of a set, any subcollection closed under arbitrary intersections and unions forms a complete sublattice. These variants highlight structural differences: complete semilattices may omit one type of bound entirely, while conditional completeness and sublattices address partial or inherited forms of the full completeness axiom.^[11]

Examples

Standard examples

One prominent example of a complete lattice is the power set \mathcal{P}(X) of a set X, partially ordered by set inclusion. In this lattice, the supremum of any collection of subsets is their union, and the infimum is their intersection; the top element is X and the bottom element is the empty set.$$] ^[14] Another standard example is the lattice of all topologies on a fixed set X, ordered by inclusion, where a topology \tau_1 is finer than \tau_2 if \tau_2 \subseteq \tau_1. The supremum of a family of topologies is the smallest topology containing the union of their bases (the topology they generate), and the infimum is the set-theoretic intersection of their open sets.[$$ ^[14] The collection of all open sets in a topological space T, partially ordered by inclusion, forms a complete lattice. Arbitrary unions serve as suprema, and arbitrary intersections serve as infima.$$] ^[16] In ring theory, the set of all ideals of a ring R, ordered by inclusion, constitutes a complete lattice. The infimum of any family of ideals is their intersection, and the supremum is the smallest ideal containing their union (the ideal sum). For the ring of integers \mathbb{Z}, this lattice consists of the principal ideals n\mathbb{Z} for n \geq 0, with operations corresponding to greatest common divisors and least common multiples.[$$ ^[17] Finally, every chain (totally ordered set) that possesses all suprema and infima is a complete lattice. A concrete instance is the extended real line [-\infty, \infty] under the standard order, where the supremum and infimum of any subset coincide with its least upper bound and greatest lower bound, respectively, including \pm \infty as the top and bottom elements.$$] ^[18]

Counterexamples

The set of positive integers ordered by divisibility forms a lattice, with the meet given by the greatest common divisor and the join by the least common multiple of any two elements, but it is not a complete lattice. For instance, the subset consisting of all prime numbers has no supremum within the set, as the least common multiple of infinitely many distinct primes is not a positive integer.^[19] The rational numbers \mathbb{Q} under the usual order form a lattice, being a totally ordered set (a chain), but fail to be complete. A standard example is the bounded subset \{ q \in \mathbb{Q} \mid q^2 < 2 \}, which has no least upper bound in \mathbb{Q} since \sqrt{2} is irrational.^[19] The set of negative integers \{\dots, -3, -2, -1\} under the usual order is an infinite descending chain, hence a lattice, with -1 as the greatest element but no least element. Consequently, it lacks a supremum for the empty subset (requiring a least element) and no infimum for the entire set, as it is unbounded below.^[19] In general, any lattice without a least element fails completeness because the supremum of the empty subset does not exist, and similarly, the absence of a greatest element means the infimum of the empty subset is missing.^[19] Boolean algebras, being complemented distributive lattices, are not necessarily complete. For example, the Boolean algebra consisting of all finite and cofinite subsets of an infinite set is atomic but not complete, as the supremum of the countable collection of distinct singletons (disjoint atoms) does not exist within the algebra.^[20]

Properties

Essential properties

Every complete lattice is bounded, possessing both a least element (bottom, denoted ⊥) and a greatest element (top, denoted ⊤). This follows directly from the completeness condition: the supremum of the empty subset is ⊥, and the infimum of the empty subset is ⊤. Complete lattices are not necessarily distributive. For instance, the lattice of subspaces of a vector space of dimension at least 2 is modular yet fails distributivity, as there exist elements a, b, c such that a \vee (b \wedge c) \neq (a \vee b) \wedge (a \vee c).^[21] However, if a complete lattice is distributive—meaning finite joins distribute over finite meets and vice versa—then it is completely distributive, with arbitrary suprema distributing over arbitrary infima. In such cases, for any indexed families of elements \{a_i\}_{i \in I} and \{b_j\}_{j \in J}, [ \sup_{i \in I} \inf_{j \in J} (a_i \wedge b_j) = \inf_{j \in J} \sup_{i \in I} (a_i \wedge b_j).

This infinite distributivity law holds in complete distributive lattices and characterizes their structure.[](https://ncatlab.org/nlab/show/distributive%2Blattice) A complete lattice is algebraic if and only if it is compactly generated, meaning every element is the supremum of compact elements (those whose suprema with larger sets remain compact). Algebraic lattices thus form a key subclass where the order is generated by its compact elements under joins.[](https://www.math.hawaii.edu/~jb/math618/os3uh.pdf) ### Special cases Locally finite complete lattices are those in which every [interval](/page/Interval) between two elements is finite.[](https://webspace.maths.qmul.ac.uk/p.j.cameron/design/encyc/topics/posets.pdf) This property implies that the entire [lattice](/page/Lattice), considered as the [interval](/page/Interval) from its [bottom](/page/Bottom) to [top](/page/Top) element, must be finite, making locally finite complete lattices equivalent to finite lattices.[](https://webspace.maths.qmul.ac.uk/p.j.cameron/design/encyc/topics/posets.pdf) In such structures, the finiteness of intervals ensures limited covering relations overall, and this is tied to the [lattice](/page/Lattice) having finite height, defined as the length of its longest [chain](/page/Chain).[](https://webspace.maths.qmul.ac.uk/p.j.cameron/design/encyc/topics/posets.pdf) Consequently, locally finite complete lattices are Noetherian, meaning they contain no infinite ascending [chains](/page/Chain), since their finite size prevents unbounded increases.[](https://webspace.maths.qmul.ac.uk/p.j.cameron/design/encyc/topics/posets.pdf) Atomic complete lattices extend the atomic property to the complete setting, where every [element](/page/Element) is the supremum of the atoms beneath it.[](https://math.hawaii.edu/~jb/math618/Nation-LatticeTheory.pdf) Atoms in a [lattice](/page/Lattice) are the minimal nonzero [elements](/page/Element), and this join-irreducible [representation](/page/Representation) allows atomic complete lattices to model structures like the power set [lattice](/page/Lattice) of a set, where subsets are unions (joins) of singletons (atoms).[](https://math.hawaii.edu/~jb/math618/Nation-LatticeTheory.pdf) Unlike general complete [lattices](/page/Lattice), which may lack atoms or require infinite joins for [representation](/page/Representation), atomic ones emphasize a "basis" of minimal [elements](/page/Element), providing a discrete foundation that simplifies computations in areas such as [matroid](/page/Matroid) [theory](/page/Theory) and geometric lattices.[](https://math.hawaii.edu/~jb/math618/Nation-LatticeTheory.pdf) Continuous lattices represent a refinement of complete lattices particularly relevant in [domain theory](/page/Domain_theory), characterized by the preservation of suprema over [directed sets](/page/Directed_set).[](https://www.cs.ox.ac.uk/files/3229/PRG07.pdf) Formally, a complete lattice is continuous if every element equals the supremum of elements way-below it, where the way-below relation $ x \ll y $ holds when any [directed set](/page/Directed_set) with supremum at least $ y $ contains an element above $ x $.[](https://www.cs.ox.ac.uk/files/3229/PRG07.pdf) This ensures that directed suprema, crucial for fixed-point theorems in semantics and approximation, behave continuously with respect to the [order](/page/Order).[](https://www.cs.ox.ac.uk/files/3229/PRG07.pdf) In contrast to arbitrary complete lattices, continuous lattices exhibit infinite-dimensional yet approximable structures, often arising as ideals in algebraic lattices and supporting [Scott topology](/page/Topology) for topological investigations.[](https://www.cs.ox.ac.uk/files/3229/PRG07.pdf) These special cases highlight subclasses with enhanced structural control: locally finite ones confine to finite dimensions via bounded chains, atomic ones via minimal generators, and continuous ones via directed approximations, distinguishing them from the unbounded generality of complete lattices. ## Morphisms ### Complete lattice homomorphisms A complete lattice homomorphism between complete lattices $L$ and $M$ is a [function](/page/Function) $f: L \to M$ that preserves arbitrary suprema and infima. Specifically, for any [subset](/page/Subset) $S \subseteq L$, $f(\sup S) = \sup f(S)$ and $f(\inf S) = \inf f(S)$.[](https://proofwiki.org/wiki/Definition:Complete_Lattice_Homomorphism) This ensures that the mapping respects the full completeness structure, extending beyond finite operations to arbitrary collections. In formula terms, for any indexed family $\{a_i \mid i \in I\}$ in $L$,

f\left( \bigvee_{i \in I} a_i \right) = \bigvee_{i \in I} f(a_i)

and dually,

f\left( \bigwedge_{i \in I} a_i \right) = \bigwedge_{i \in I} f(a_i).

\text{Least fixed point} = \sup { x \in L \mid x \leq f(x) }, \quad \text{Greatest fixed point} = \inf { x \in L \mid f(x) \leq x }.

This theorem, originally formulated by Knaster in 1928 and generalized by Tarski in 1955, underpins iterative methods in [order theory](/page/Order_theory). Complete lattices play a central role in [denotational semantics](/page/Denotational_semantics), where semantic domains are modeled as complete partial orders or continuous lattices to interpret recursive definitions via fixed points of monotone functions.[33] Dana Scott's development of [domain theory](/page/Domain_theory) in the [1970s](/page/1970s) established these structures as foundational for assigning meanings to programming languages, ensuring the existence of least fixed points for denoting computable functions. Garrett Birkhoff's 1940 monograph *[Lattice Theory](/page/Lattice)* formalized many key results on complete lattices, including early discussions of compact elements and their role in approximation, influencing subsequent advancements in the field.

References

[1]
Complete Lattice -- from Wolfram MathWorld
A partially ordered set (or ordered set or poset for short) (L,<=) is called a complete lattice if every subset M of L has a least upper bound.
[2]
Complete Lattice - an overview | ScienceDirect Topics
A complete lattice is an ordered set 〈E, ≤〉 such that any subset X of E has a least upper bound and a greatest lower bound.
[3]
MacNeille completion in nLab
Sep 9, 2019 · The MacNeille or Dedekind–MacNeille (not 'Mac Neille') completion of a lattice (or even poset) L L is the universal complete lattice containing ...
[4]
Tarski's Fixed Point Theorem -- from Wolfram MathWorld
### Summary of Tarski's Fixed Point Theorem
[5]
[PDF] Lattice Theory Lecture 1 Basics - nmsu math
A lattice is a poset where every two-element set has a least upper bound and a greatest lower bound. A complete lattice has these for every subset.
[6]
[PDF] 2. Semilattices, Lattices and Complete Lattices
Complete lattices abound in mathematics because of their connection with closure ... Tarski, A lattice-theoretical fixpoint theorem and its applications ...
[7]
[PDF] Semantics of the Domain of Flow Diagrams
Our starting point is the so-called “lattice-theoretic approach” to the theory of computa- ... subsets of a domain, so that a domain is a complete lattice. Other ...
[8]
Partially Ordered Set -- from Wolfram MathWorld
A partially ordered set (or poset) is a set taken together with a partial order on it. Formally, a partially ordered set is defined as an ordered pair.
[9]
Lattice -- from Wolfram MathWorld
### Definitions of Join (Supremum) and Meet (Infimum) in Lattices or Posets
[10]
None
Below is a merged response summarizing the definitions and details of a complete lattice from Garrett Birkhoff's *Lattice Theory* (Revised Edition, 1948), based on the provided segments. To retain all information in a dense and organized manner, I will use a table in CSV format for key details, followed by a narrative summary that integrates additional context and notes. The table will capture the core definition, source, empty set considerations, top/bottom elements, and examples/context, while the narrative will provide a cohesive overview and additional insights.
[11]
complete semilattice - PlanetMath.org
Mar 22, 2013 · A complete semilattice is a join-semilattice where the arbitrary join of any subset exists, and it is also a complete meet-semilattice.
[12]
complete lattice in nLab
Mar 15, 2012 · A complete lattice is a poset with all small joins and meets, and it is a lattice. Having all joins or meets is sufficient for the other.
[13]
SupLat in nLab
Aug 9, 2020 · Sup Lat is the category whose objects are suplattices and whose morphisms are suplattice homomorphisms, that is functions which preserve all joins (including ...
[14]
[PDF] Math 222A W03 S. Complete lattices
Definition. A lattice L is said to be complete if (i) every subset S of L has a least upper bound (denoted sup S) and (ii) every subset of L has a greatest ...
[15]
[PDF] Notes on Lattice Theory J. B. Nation University of Hawaii
Let us define a complete lattice to be an ordered set L in which every subset A has a greatest lower bound VA and a least upper bound WA.3 Clearly every finite ...
[16]
[PDF] Chapter 5. Lattices, closure operators, and Galois connections.
If T is a topological space, show that the open sets in T, partially ordered by inclusion, form a complete lattice. Describe the meet and join operations ...
[17]
ideal in nLab
Jan 11, 2025 · 2. Kinds of ideals. Ideals form complete lattices where arbitrary meets are given by set-theoretic intersection. In other words, ideals form a ...Definitions · In rings (and other rigs) · In lattices (and other prosets) · In both at once
[18]
The union of two cuts is a cut? - MathOverflow
Apr 6, 2020 · When people say that cuts form a complete lattice under ⊆, they don't necessarily mean that the lattice operations are the ordinary union ...Was lattice theory central to mid-20th century mathematics?Constructive lattice completion - MathOverflowMore results from mathoverflow.net
[19]
[PDF] Universal algebra and lattice theory Lecture 7 Complete lattices
Dec 23, 2020 · A lattice L is said to be complete when for every X ⊂ L we have that both sup(X) and inf(X) exist. We define. V. X := sup(X) and. 기. X := inf(X) ...
[20]
Introduction to Lattices and Order
Download full list. ×. 2nd edition. B. A. Davey, La Trobe University, Victoria, H. A. Priestley, University of Oxford. Publisher: Cambridge University Press.
[21]
Boolean Lattice - an overview | ScienceDirect Topics
Some algebras of sets, such as P(Ω), are complete Boolean lattices. Others are not complete. For instance, let X be the algebra of all finite or cofinite ...
[22]
The Basic Theory of Ordering Relations
A lattice is a poset $(L, \unlhd)$ in which every pair of elements has both a meet and a join. A complete lattice is one in which every subset of $L$ has a ...
[23]
distributive lattice in nLab
May 31, 2025 · Definition 1.1. A distributive lattice is a lattice in which join ∨ \vee and meet ∧ \wedge distribute over each other, in that for all x , y , z ...
[24]
[PDF] 3. Algebraic Lattices
A lattice L is said to be algebraic, or compactly generated, if it is complete and Lc ... Every algebraic lattice is weakly atomic. Proof. Let a>b in an algebraic ...
[25]
[PDF] Posets
However, locally finite posets are determined by their covering pairs: Proposition 2 Let (X,R) be a locally finite poset, and x,y ∈ X. Then x ≤R y if.
[26]
[PDF] CONTINUOUS LATTICES
The proofs of these statements can be safely left to the reader. 2,3 Definition, A continuous lattice is a complete lattice D in which for every y E D \'le ...
[27]
Definition:Complete Lattice Homomorphism - ProofWiki
Apr 29, 2025 · Definition. Let L1=(S1,⪯1) and L2=(S2,⪯2) be complete lattices. Let ϕ:S1→S2 be a mapping between the underlying sets of L1 and L2.
[28]
complete lattice homomorphism - PlanetMath.org
Mar 22, 2013 · Complete lattice homomorphism is a function from one lattice. to an other lattice, which preserves arbitrary (not only finite) meets and joins.
[29]
[PDF] Introduction to Lattices and Order Second edition BA Davey
Introduction to Lattices and Order. Second edition. B.A. Davey. La Trobe University. H. A. Priestley. University of Oxford. CAMBRIDGE. UNIVERSITY PRESS. Page 2 ...
[30]
(PDF) The Complete Congruence Lattice of a Complete Lattice
For instance, there is no free complete lattice of 3 generators since there are complete lattices of arbitrarily large size completely generated by 3 elements.
[31]
https://doi.org/10.4153/CJM-1964-013-2
[32]
REPRESENTATIONS OF LATTICES BY SETS
GARRETT BIRKHOFF AND ORRIN FRINK, JR. This paper deals with the representations of a general lattice L by sets. After a preliminary.
[33]
Domains for denotational semantics - SpringerLink
Oct 22, 2005 · Scott, D.S. 1972 Continuous lattices. Springer Lecture Notes in Mathematics, vol. 274 (1972), pp. 97–136. Article MathSciNet Google Scholar.