Dedekind–MacNeille completion

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

The Dedekind–MacNeille completion of a partially ordered set (poset) S is the smallest complete lattice that contains S. In other words, it is the tiniest way to fill in a poset so that every subset has a least upper bound (supremum) and a greatest lower bound (infimum), while keeping the original order intact.

What is a poset and a completion?
- A poset is a set with a relation ≤ that is reflexive, transitive, and antisymmetric. In many familiar orders (like real numbers), every pair is comparable, but in a poset some pairs may be incomparable.
- A completion of S is a complete lattice L together with an order-embedding of S into L. An order-embedding preserves the order: if x ≤ y in S, then x ≤ y in L, and different elements map to different elements.

How the Dedekind–MacNeille completion is built
- For any subset A of S, write A^u for the set of upper bounds of A (elements that are ≥ every element of A) and A^l for the set of lower bounds of A (elements that are ≤ every element of A).
- Consider the collection of all subsets A of S that satisfy A = (A^u)^l. Each such A represents a “closed” chunk of S.
- Order these subsets by inclusion. This ordered collection forms a complete lattice. The original S sits inside this lattice by sending each element x to its principal ideal ↓x = {y in S : y ≤ x}. This embedding preserves order, so S sits inside the completion without distortion.

Two viewpoints that describe the same construction
- Double-closure view: A is in the completion exactly when applying the upper-bound and lower-bound operations twice returns A, i.e., A = (A^u)^l.
- Cut view: A cut is a pair (A,B) with A ⊆ S and B ⊆ S such that B = A^u and A = B^l. The collection of all such cuts, ordered by inclusion (on A) or reverse inclusion (on B), gives the same completion.

Key properties and consequences
- Smallest completion: Among all ways to complete S into a complete lattice, the Dedekind–MacNeille completion is the smallest.
- Embedding: Each x in S embeds as ↓x in the completion; the order is preserved.
- Self-dual: Completing S and then taking the dual order gives the same result as taking the dual of S first and then completing.
- Join and meet: In the completion, joins and meets correspond to appropriate unions and intersections of the representing lower and upper sets.
- Finite case: If S is finite, its Dedekind–MacNeille completion is finite and has the smallest possible size among all finite completions containing S.
- Special cases: The completion of a Boolean algebra is a complete Boolean algebra; the completion of a residuated lattice is a complete residuated lattice. However, completing a distributive lattice need not preserve distributivity, and completing a modular lattice need not preserve modularity.
- Concept lattice: When S is built from objects and their unary attributes (and x ≤ y if “object x has attribute y”), the Dedekind–MacNeille completion is the concept lattice, central in formal concept analysis.

Why it’s useful
- It gives a canonical way to turn any poset into a complete lattice without losing information about the original order.
- It provides useful characterizations and dualities that help study lattices and their applications, from logic and algebra to data analysis.

Examples and intuition
- The rational numbers Q with the usual order have as their Dedekind–MacNeille completion the real numbers with two extra endpoints, ±∞. Each real number corresponds to a Dedekind cut, and the extended real line is obtained by closing these cuts.
- If S is an antichain (no two elements are comparable), the completion simply adds a bottom element below all of S and a top element above all of S.

Applications and algorithms
- Concept lattices in data analysis arise from specific posets and their DM completions, providing a structured way to organize objects and their attributes.
- For finite S, algorithms exist to compute the completion; these can be computationally intensive because the completion can be much larger than S. Researchers study incremental and efficient ways to generate the needed parts of the completion.

In short, the Dedekind–MacNeille completion is a principled, minimal way to turn any poset into a complete lattice, preserving its order while adding just enough elements to ensure every subset has a well-defined least upper bound and greatest lower bound.