MN Theorem Proof- Step-by-Step Explanation

What Is the MN Theorem?

The MN Theorem, formally known as the MacNeille Completion Theorem, is a fundamental result in order theory and lattice theory. It states that every partially ordered set (poset) can be embedded into a complete lattice in a way that preserves all existing suprema and infima.

In plain English: take any collection of elements with some ordering between them, and you can always find a complete lattice that contains it as a natural subset. This isn't optional—it's guaranteed.

The theorem is named after Harold M. MacNeille, who published the proof in 1937.

Why This Theorem Matters

Mathematicians and computer scientists care about this result because:

It guarantees that every algebraic structure with order has a canonical "completion" similar to how real numbers complete rational numbers
It provides a universal construction that works for any poset, not just special cases
It connects order theory to ideal/sfilter theory in algebraic structures

Prerequisites: What You Need to Know

Before diving into the proof, you need solid footing on these concepts:

Partially Ordered Sets (Posets)

A poset is a set P with a relation ≤ satisfying:

Reflexivity: a ≤ a for all a ∈ P
Antisymmetry: if a ≤ b and b ≤ a, then a = b
Transitivity: if a ≤ b and b ≤ c, then a ≤ c

Examples: ℕ with ≤, subsets of a set ordered by ⊆, real numbers with usual order.

Dedekind-MacNeille Cuts

This is the core construction in the proof. A Dedekind-MacNeille cut is a pair (A, B) where:

A is a non-empty subset of P that is downward closed (if a ∈ A and x ≤ a, then x ∈ A)
B is a non-empty subset of P that is upward closed (if b ∈ B and x ≥ b, then x ∈ B)
Every element of A is ≤ every element of B
A has no maximum and B has no minimum (unless they're singletons)

The set of all such cuts forms the MacNeille completion of P.

Complete Lattices

A complete lattice is a poset where every subset has both a supremum (join) and an infimum (meet). This is stronger than a regular lattice, which only requires binary joins and meets.

Statement of the MN Theorem

Theorem: For every partially ordered set P, there exists a complete lattice L and an embedding map φ: P → L such that:

φ preserves existing joins (suprema) of arbitrary families in P
φ preserves existing meets (infima) of arbitrary families in P
L is the smallest such complete lattice (up to isomorphism)

Step-by-Step Proof

Step 1: Define the Completion

Let P be a poset. Define the MacNeille completion MN(P) as:

MN(P) = { (A, B) ∈ 𝒫(P) × 𝒫(P) : (A, B) is a Dedekind-MacNeille cut }

This set will become our complete lattice. We need to verify it actually is one.

Step 2: Define the Embedding

For each element x ∈ P, define φ(x) = (↓x, ↑x) where:

↓x = {a ∈ P : a ≤ x} (the principal down-set of x)
↑x = {b ∈ P : b ≥ x} (the principal up-set of x)

Each pair (↓x, ↑x) is indeed a Dedekind-MacNeille cut. This gives us our embedding map φ: P → MN(P).

Step 3: Show φ Is an Order-Embedding

We need to prove: x ≤ y in P iff ↓x ⊆ ↓y

Proof: If x ≤ y, then any a ≤ x implies a ≤ y, so ↓x ⊆ ↓y. Conversely, if ↓x ⊆ ↓y, then x ∈ ↓x (by reflexivity) implies x ∈ ↓y, so x ≤ y. ∎

Since x ≤ y iff ↓x ⊆ ↓y, and ↓x ⊆ ↓y iff (↓x, ↑x) ≤ (↓y, ↑y) in the product order, φ is an order-embedding. It also preserves order.

Step 4: Define the Lattice Operations on MN(P)

For any collection of cuts {(A_i, B_i)} in MN(P), define:

Join (supremum): ⋁_i(A_i, B_i) = (⋂_iA_i, ↓(⋂_iB_i))

Meet (infimum): ⋀_i(A_i, B_i) = (↑(⋂_iA_i), ⋂_iB_i)

Here ↓X denotes the down-set generated by X, and ↑X denotes the up-set generated by X.

Step 5: Verify the Operations Are Well-Defined

For the join: We need (⋂A_i, ↓(⋂B_i)) to be a valid cut.

Check the conditions:

⋂A_i is non-empty (each A_i is non-empty)
⋂A_i is downward closed (intersection of downward closed sets)
↓(⋂B_i) is upward closed by definition
Every element of ⋂A_i is ≤ every element of ⋂B_i (each A_i ≤ each B_i)

The meet case is symmetric. Both operations produce valid Dedekind-MacNeille cuts.

Step 6: Show MN(P) Is a Complete Lattice

Any collection of elements in MN(P) has both a join and meet by Step 4. Therefore MN(P) is a complete lattice.

To verify: the join of all elements is indeed the supremum. By construction, ⋂A_i is the greatest lower bound of the A_i sets, and ↓(⋂B_i) captures the corresponding upper elements.

Step 7: Prove Preservation of Existing Joins and Meets

Claim: If S ⊆ P has a supremum sup(S) in P, then ⋁_x∈S φ(x) = φ(sup(S)) in MN(P).

Proof: For each x ∈ S, φ(x) = (↓x, ↑x). The join in MN(P) gives:

⋁_x∈S φ(x) = (⋂_x∈S ↓x, ↓(⋂_x∈S ↑x))

Now, ⋂_x∈S ↓x = {a ∈ P : a ≤ x for all x ∈ S} = ↓sup(S)

And ⋂_x∈S ↑x = {b ∈ P : b ≥ x for all x ∈ S} = ↑sup(S)

Thus the join equals (↓sup(S), ↑sup(S)) = φ(sup(S)). ∎

The meet case is analogous.

Step 8: Minimality of the Completion

If L is any complete lattice with an embedding ψ: P → L preserving suprema and infima, then there exists a unique injective homomorphism θ: MN(P) → L such that θ ∘ φ = ψ.

The map is defined by θ(A, B) = sup_L(ψ(A)) = inf_L(ψ(B)). By the preservation properties, these are equal in any complete lattice.

Concrete Example

Consider the poset P = {a, b} with no relation between a and b (incomparable elements).

Principal down-sets:

↓a = {a}
↓b = {b}

Principal up-sets:

↑a = {a}
↑b = {b}

The MacNeille completion MN(P) contains:

φ(a) = ({a}, {a})
φ(b) = ({b}, {b})
Bottom element: (∅, P) — but we need non-empty, so actually (∅, {a, b}) is valid as empty A has no max
Top element: (P, ∅)
The join of a and b: (∅, {a, b}) ∨ ({a}, {a}) = (∅, ↓{a, b}) = (∅, {a, b})

Result: MN(P) ≅ {0, a, b, 1} where 0 < a, b < 1 and a, b are incomparable. This is the 2-element antichain with top and bottom added.

Comparison with Other Completions

Completion Type	Applies To	Result Type	Preserves
MacNeille Completion	Any poset	Complete lattice	All existing suprema and infima
Dedekind Completion	Ordered groups/rings	Dedekind complete structure	All bounded suprema and infima
Cauchy Completion	Metric spaces	Complete metric space	Limits of Cauchy sequences
Ideal Completion	Any poset	Complete lattice	Directed suprema only

The MacNeille completion is strictly more general than ideal completion because it preserves both joins and meets, not just directed joins.

How to Actually Use This Construction

Here's the practical algorithm for computing the MacNeille completion of a finite poset:

List all elements of your poset P
Compute all principal ideals: ↓x for each x ∈ P
Compute all principal filters: ↑x for each x ∈ P
Form pairs (↓x, ↑x) for each x
Add the bottom element: (⋂_x∈P ↓x, P)
Add the top element: (P, ⋂_x∈P ↑x)
Close under meets and joins: repeatedly compute intersections as defined in Step 4

For finite posets, this process terminates and produces the complete lattice.

Common Misconceptions

Myth: The MacNeille completion is always the ideal completion.

Reality: They're different constructions. The ideal completion preserves only directed suprema. The MacNeille completion is finer and preserves all existing suprema and infima.

Myth: The completion is unique up to equality.

Reality: The completion is unique up to isomorphism. Different constructions may yield different underlying sets but isomorphic complete lattices.

Applications

The MN Theorem shows up in:

Domain theory in computer science (denotational semantics)
Abstract interpretation of programs
Formal concept analysis (data analysis)
MV-algebras and multi-valued logic

In domain theory, the MacNeille completion gives the free completion of a poset to a continuous domain, which is essential for modeling recursive computations.

The Bottom Line

The MacNeille completion theorem is a completeness theorem for order theory. It tells you that if you have a poset, you can always embed it into a complete lattice that respects its existing structure. The proof constructs this lattice explicitly using Dedekind-MacNeille cuts and verifies the required properties step by step.

No poset is too broken or sparse to complete. The theorem guarantees a home.