Key Concepts of Complete Lattices

Why This Matters

Complete lattices sit at the heart of order theory and provide the structural foundation for results you'll encounter across algebra, topology, and theoretical computer science. When you study complete lattices, you're learning about closure properties, fixed-point existence, and structural completeness—concepts that appear whenever mathematicians need guarantees that certain operations will always produce well-defined results. The Knaster-Tarski theorem alone has applications ranging from program verification to game theory equilibria.

Don't just memorize definitions here—understand why completeness matters. You're being tested on your ability to recognize when a structure qualifies as a complete lattice, how completeness enables powerful theorems, and what distinguishes complete lattices from their ordinary counterparts. Know what each concept illustrates: the power set lattice demonstrates completeness through set operations, Galois connections reveal structural dualities, and the completion process shows how we can "upgrade" incomplete structures.

---

Foundational Definitions

These core definitions establish what makes a lattice "complete" and how we formalize the key operations. Completeness requires that suprema and infima exist for all subsets—not just finite ones.

Definition of a Complete Lattice

• A complete lattice $(L, \leq)$ is a partially ordered set where every subset $S \subseteq L$ has both a supremum and an infimum
• Generalizes ordinary lattices—standard lattices only guarantee joins and meets for finite subsets, while complete lattices handle infinite collections
• Notation convention: $\bigvee S$ denotes the supremum and $\bigwedge S$ denotes the infimum of any subset $S$

Supremum and Infimum in Complete Lattices

• The supremum (join) $\bigvee S$—the least element in $L$ that is greater than or equal to every element in $S$
• The infimum (meet) $\bigwedge S$—the greatest element in $L$ that is less than or equal to every element in $S$
• Existence is guaranteed for every subset, including empty and infinite ones—this is precisely what "complete" means

The Completeness Property

• Completeness ensures robustness—every subset having suprema and infima makes the structure closed under arbitrary joins and meets
• Enables fixed-point theory—without completeness, theorems like Knaster-Tarski cannot be stated or applied
• Distinguishes complete from ordinary lattices—a lattice of finite subsets ordered by inclusion is not complete; the power set lattice is

---

Canonical Examples and Representations

Understanding complete lattices requires concrete examples. The power set lattice is your go-to example for demonstrating completeness properties.

Power Set Lattice

• $(\mathcal{P}(X), \subseteq)$ is the prototypical complete lattice—the power set of any set $X$ ordered by inclusion satisfies all completeness requirements
• Supremum is union, infimum is intersection—for any collection of subsets $\{A_i\}$, we have $\bigvee A_i = \bigcup A_i$ and $\bigwedge A_i = \bigcap A_i$
• Top element is $X$, bottom element is $\emptyset$—these arise as the supremum and infimum of the entire lattice

Hasse Diagrams for Complete Lattices

• Visual representation of order relations—nodes represent elements, edges represent covering relations with transitive edges omitted
• Complexity increases with infinite structures—finite complete lattices have clean diagrams, but infinite ones require careful abstraction or truncation
• Useful for identifying sublattice structure—Hasse diagrams reveal chains, antichains, and the overall "shape" of the lattice

---

Major Theorems and Applications

Complete lattices enable powerful existence theorems. The Knaster-Tarski theorem is arguably the most important result—know its statement and why completeness is essential.

Knaster-Tarski Fixed-Point Theorem

• Every monotone function $f: L \to L$ on a complete lattice has at least one fixed point—in fact, the set of all fixed points forms a complete lattice itself
• Applications span multiple fields—computer science (denotational semantics), economics (Nash equilibria), and game theory all rely on this result
• Completeness is essential—the theorem fails for ordinary lattices; you need arbitrary suprema to construct the least fixed point as $\bigvee \{x : x \leq f(x)\}$

Galois Connections in Complete Lattices

• A pair of monotone functions $(f, g)$ between complete lattices $(L, \leq)$ and $(M, \leq)$ satisfying $f(x) \leq y \iff x \leq g(y)$ for all $x \in L, y \in M$
• Establishes structural duality—Galois connections reveal deep correspondences between seemingly different mathematical structures
• Induces closure operators—the compositions $g \circ f$ and $f \circ g$ are closure operators, connecting to topology and algebra

Distributive Complete Lattices

• Join distributes over arbitrary meets (and vice versa)—the condition $a \vee \bigwedge S = \bigwedge_{s \in S}(a \vee s)$ holds for all elements and subsets
• Simplifies calculations and proofs—distributivity allows algebraic manipulation similar to arithmetic with addition and multiplication
• Key examples: the lattice of open sets in a topological space and the lattice of ideals in certain rings exhibit this property

---

Structural Analysis

These concepts help you understand how complete lattices relate to each other and how incomplete structures can be "completed." Sublattices preserve structure; completion constructs it.

Complete Sublattices

• A subset $M \subseteq L$ that is itself a complete lattice under the inherited order—suprema and infima computed in $M$ must match those in $L$
• Stronger than being a sublattice—a sublattice only preserves finite joins and meets; a complete sublattice preserves all of them
• Fixed-point sets are complete sublattices—by Knaster-Tarski, the set of fixed points of a monotone function forms a complete sublattice

Completion of a Lattice

• Process of extending a lattice to make it complete—adds "ideal" elements so that every subset gains a supremum and infimum
• Dedekind-MacNeille completion is the standard method—constructs the smallest complete lattice containing the original as a subposet
• Preserves existing structure—the original lattice embeds into its completion, and existing joins/meets are retained

---

Quick Reference Table

---

Self-Check Questions

1. What property distinguishes a complete lattice from an ordinary lattice, and why does this distinction matter for the Knaster-Tarski theorem?

2. Compare the power set lattice $\mathcal{P}(X)$ and a chain of real numbers: both can be complete lattices, but how do their structures differ in terms of comparability?

3. If $f: L \to L$ is a monotone function on a complete lattice, what can you conclude about the set of fixed points of $f$? What theorem guarantees this?

4. Explain why a sublattice of a complete lattice is not necessarily a complete sublattice. What additional condition must be satisfied?

5. (FRQ-style) Given a lattice that is not complete, describe the process of completion and explain what properties the completed structure will have that the original lacked.