Additional Background pdf
Part C: Dedekind-MacNeille Completion
In this section we want to try understand what exactly happens to a poset in a Dedekind-MacNeille Completion. Our theoretical bases is Proposition A.16 and those definitions belonging to it.
To see how we can "conjure up" a lattice from any arbitrary poset it is best we look at a concrete example. Our starting position is the P = (X, P) in Figure C.1.
Figure C.1: A poset P
P is definitely not a lattice, because, for example, elements c and d do not have a supremum. So, it makes sense to ask for a completion which then has to be a (complete) lattice.
We are interested in the image of basic set X under the operator ΓUL. Thus, we have to calculate the values of ΓUL for all subsets of X:
| Subset A of X | AU | ΓUL(A) = (AU)L |
|---|---|---|
| {a} | {a,c} | {a} |
| {b} | {b,c,d} | {b} |
| {c} | {c} | {a,b,c} |
| {d} | {d} | {b,d} |
| {a,b} | {c} | {a,b,c} |
| {a,c} | {c} | {a,b,c} |
| {a,d} | ∅ | {a,b,c,d} |
| {b,c} | {c} | {a,b,c} |
| {b,d} | {d} | {b,d} |
| {c,d} | ∅ | {a,b,c,d} |
| {a,b,c} | {c} | {a,b,c} |
| {a,b,d} | ∅ | {a,b,c,d} |
| {a,c,d} | ∅ | {a,b,c,d} |
| {b,c,d} | ∅ | {a,b,c,d} |
| {a,b,c,d} | ∅ | {a,b,c,d} |
The operator ΓUL produces the set
im(ΓUL) = {∅, {a}, {b}, {b,d}, {a,b,c}, {a,b,c,d}}.
Proposition A.16 - Dedekind-MacNeille tells us that all that's left to do to obtain our (complete) lattice which densly embeds our poset P, iis to sort the elements by set inclusion ⊆. Figure C.2 below illustrates our result.
Figure C.2: Dedekind-MacNeille completion of the poset P
Clearly illustrated by the figure is the embedding through function φX which assigns to each element in X its Down-set (φX(a) = {a}, φX(b) = {b}, φX(c) = {a,b,c}, φX(d) = {b,d}).