View source for Dedekind–MacNeille completion

{{bots|deny=Citation bot}}<!-- Because it won't stop lobotomizing conference proceedings titles -->
{{short description|Smallest complete lattice containing a partial order}}
{{redirect|Dedekind completion|some other related concepts|Dedekind completeness}}

[[File:Dedekind-Macneille completion.svg|thumb|240px|The [[Hasse diagram]] of a partially ordered set (left) and its Dedekind–MacNeille completion (right).]]
In [[mathematics]], specifically [[order theory]], the '''Dedekind–MacNeille completion''' of a [[partially ordered set]] is the smallest [[complete lattice]] that contains it. It is named after [[Holbrook Mann MacNeille]] whose 1937 paper first defined and constructed it, and after [[Richard Dedekind]] because its construction generalizes the [[Dedekind cut]]s used by Dedekind to construct the [[real number]]s from the [[rational number]]s. It is also called the '''completion by cuts''' or '''normal completion'''.<ref>{{harvtxt|Davey| Priestley|2002|p=166}}; {{harvtxt|Schröder|2003|p=119}}.</ref>

==Order embeddings and lattice completions==
A [[partially ordered set]] (poset) consists of a [[Set (mathematics)|set]] of elements together with a [[binary relation]] {{math|''x'' ≤ ''y''}} on pairs of elements that is [[Reflexive relation|reflexive]] ({{math|''x'' ≤ ''x''}} for every ''x''), [[Transitive relation|transitive]] (if {{math|''x'' ≤ ''y''}} and {{math|''y'' ≤ ''z''}} then {{math|''x'' ≤ ''z''}}), and [[Antisymmetric relation|antisymmetric]] (if both {{math|''x'' ≤ ''y''}} and {{math|''y'' ≤ ''x''}} hold, then {{math|1=''x'' = ''y''}}). The usual numeric orderings on the [[integer]]s or real numbers satisfy these properties; however, unlike the orderings on the numbers, a partial order may have two elements that are ''incomparable'': neither {{math|''x'' ≤ ''y''}} nor {{math|''y'' ≤ ''x''}} holds. Another familiar example of a partial ordering is the [[Subset|inclusion]] ordering ⊆ on pairs of sets.{{sfnp|Roman|2007}}

If {{mvar|S}} is a partially ordered set, a ''completion'' of {{mvar|S}} means a [[complete lattice]] {{mvar|L}} with an [[order-embedding]] of {{mvar|S}} into {{mvar|L}}.<ref>{{harvtxt|Schröder|2003}}, definition 5.3.1, p.&nbsp;119.</ref> A complete lattice is a lattice in which every subset of elements of {{mvar|L}} has an [[infimum and supremum]]; this generalizes the analogous properties of the [[real number]]s. An order-embedding is a function that maps distinct elements of {{mvar|S}} to distinct elements of {{mvar|L}} such that each pair of elements in {{mvar|S}} has the same ordering in {{mvar|L}} as they do in {{mvar|S}}. The [[extended real number line]] (real numbers together with +∞ and −∞) is a completion in this sense of the rational numbers: the set of rational numbers {3, 3.1, 3.14, 3.141, 3.1415, 3.14159, ...} does not have a rational least upper bound, but in the real numbers it has the least upper bound {{pi}}.{{sfnp|O'Leary|2015}}

A given partially ordered set may have several different completions. For instance, one completion of any partially ordered set {{mvar|S}} is the set of its [[lower set|downwardly closed subsets]] ordered by [[subset|inclusion]]. {{mvar|S}} is embedded in this (complete) lattice by mapping each element {{mvar|x}} to the lower set of elements that are less than or equal to {{mvar|x}}. The result is a [[distributive lattice]] and is used in [[Birkhoff's representation theorem]]. However, it may have many more elements than are needed to form a completion of {{mvar|S}}.<ref>{{citation|title=Concept data analysis: theory and applications|first1=Claudio|last1=Carpineto|first2=Giovanni|last2=Romano|publisher=John Wiley and Sons|year=2004|isbn=978-0-470-85055-8|page=10}}.</ref> Among all possible lattice completions, the Dedekind–MacNeille completion is the smallest complete lattice with {{mvar|S}} embedded in it.<ref name="smallest-completion"/>

==Definition==
For each subset {{mvar|A}} of a partially ordered set {{mvar|S}}, let {{math|''A''<sup>u</sup>}} denote the set of [[upper bounds]] of {{mvar|A}}; that is, an element {{mvar|x}} of {{mvar|S}} belongs to {{math|''A''<sup>u</sup>}} whenever {{mvar|x}} is greater than or equal to every element in {{mvar|A}}. Symmetrically, let {{math|''A''<sup>l</sup>}} denote the set of lower bounds of {{mvar|A}}, the elements that are less than or equal to every element in {{mvar|A}}. Then the Dedekind–MacNeille completion of {{mvar|S}} consists of all subsets {{mvar|A}} for which 
:{{math|1=(''A''<sup>u</sup>)<sup>l</sup> = ''A''}};
it is ordered by inclusion: {{math|''A'' ≤ ''B''}} in the completion if and only if {{math|''A'' ⊆ ''B''}} as sets.<ref name=def/>

An element {{mvar|x}} of {{mvar|S}} embeds into the completion as its [[Ideal (order theory)|principal ideal]], the set {{math|↓<sub>''x''</sub>}} of elements less than or equal to {{mvar|x}}. Then {{math|(↓<sub>''x''</sub>)<sup>u</sup>}} is the set of elements greater than or equal to {{mvar|x}}, and {{math|1=((↓<sub>''x''</sub>)<sup>u</sup>)<sup>l</sup> = ↓<sub>''x''</sub>}}, showing that {{math|↓<sub>''x''</sub>}} is indeed a member of the completion. The mapping from {{mvar|x}} to {{math|↓<sub>''x''</sub>}} is an order-embedding.<ref name=def>{{harvtxt|MacNeille|1937}}, Lemma 11.8, p.&nbsp; 444; {{harvtxt|Davey| Priestley|2002}}, Lemma 3.9(i), p.&nbsp;166.</ref>

An alternative definition of the Dedekind–MacNeille completion that more closely resembles the definition of a Dedekind cut is sometimes used.<ref>This is the definition originally used by {{harvtxt|MacNeille|1937}}, for instance.</ref> In a partially ordered set {{mvar|S}}, define a ''cut'' to be a pair of sets {{math|(''A'',''B'')}} for which {{math|1=''A''<sup>u</sup> = ''B''}} and {{math|1=''A'' = ''B''<sup>l</sup>}}. If {{math|(''A'',''B'')}} is a cut then ''A'' satisfies the equation {{math|1=(''A''<sup>u</sup>)<sup>l</sup> = ''A''}}, and conversely if {{math|1=(''A''<sup>u</sup>)<sup>l</sup> = ''A''}} then {{math|(''A'',''A''<sup>u</sup>)}} is a cut. Therefore, the set of cuts, partially ordered by inclusion on the lower set of the cut (or the reverse of the inclusion relation on the upper set), gives an equivalent definition of the Dedekind–MacNeille completion.{{sfnp|MacNeille|1937}}

With the alternative definition, both the join and the meet operations of the complete lattice have symmetric descriptions: if {{math|(''A<sub>i</sub>'',''B<sub>i</sub>'')}} are the cuts in any family of cuts, then the meet of these cuts is the cut {{math|(''L'',''L''<sup>u</sup>)}} where {{math|1=''L'' = ∩<sub>''i''</sub>''A<sub>i</sub>''}}, and the join is the cut {{math|(''U''<sup>l</sup>,''U'')}} where {{math|1=''U'' = ∩<sub>''i''</sub>''B<sub>i</sub>''}}.{{sfnp|MacNeille|1937}}

==Examples==
If <math>\Q</math> is the set of [[rational number]]s, viewed as a totally ordered set with the usual numerical order, then each element of the Dedekind–MacNeille completion of <math>\Q</math> may be viewed as a [[Dedekind cut]], and the Dedekind–MacNeille completion of <math>\Q</math> is the total ordering on the [[real number]]s, together with the two additional values <math>\pm\infty</math>.<ref>{{harvtxt|Davey| Priestley|2002}}, Example 7.44(1), p.&nbsp;168; {{harvtxt|Schröder|2003}}, Example 5.3.3(2), p.&nbsp;120.</ref>

If {{mvar|S}} is an [[antichain]] (a set of elements no two of which are comparable) then the Dedekind–MacNeille completion of {{mvar|S}} consists of {{mvar|S}} itself together with two additional elements, a bottom element that is below every element in {{mvar|S}} and a top element that is above every element in {{mvar|S}}.<ref>{{harvtxt|Davey| Priestley|2002}}, Example 7.44(2), p.&nbsp;168.</ref>

If {{mvar|O}} is any finite set of objects, and {{mvar|A}} is any finite set of unary attributes for the objects in {{mvar|O}}, then one may form a partial order of height two in which the elements of the partial order are the objects and attributes, and in which {{math|''x'' ≤ ''y''}} when {{mvar|x}} is an object that has attribute&nbsp;{{mvar|y}}. For a partial order defined in this way, the Dedekind–MacNeille completion of {{mvar|S}} is known as a [[concept lattice]], and it plays a central role in the field of [[formal concept analysis]].{{sfnp|Ganter|Kuznetsov|1998}}

==Properties==
The Dedekind–MacNeille completion of a partially ordered set {{mvar|S}} is the smallest complete lattice with {{mvar|S}} embedded in it, in the sense that, if {{mvar|L}} is any lattice completion of {{mvar|S}}, then the Dedekind–MacNeille completion is a partially ordered subset of {{mvar|L}}.<ref name="smallest-completion">{{harvtxt|Bishop|1978}}; {{harvtxt|Schröder|2003}}, Theorem 5.3.8, p.&nbsp;121.</ref> When {{mvar|S}} is finite, its completion is also finite, and has the smallest number of elements among all finite complete lattices containing {{mvar|S}}.{{sfnp|Ganter|Kuznetsov|1998}}

The partially ordered set {{mvar|S}} is join-dense and meet-dense in the Dedekind–MacNeille completion; that is, every element of the completion is a join of some set of elements of {{mvar|S}}, and is also the meet of some set of elements in {{mvar|S}}.<ref>{{harvtxt|Schröder|2003}}, Proposition 5.3.7, p.&nbsp;121.</ref> The Dedekind–MacNeille completion is characterized among completions of {{mvar|S}} by this property.{{sfnp|Schmidt|1956}}

The Dedekind–MacNeille completion of a [[Boolean algebra (structure)|Boolean algebra]] is a [[complete Boolean algebra]]; this result is known as the '''Glivenko–Stone theorem''', after [[Valery Ivanovich Glivenko]] and [[Marshall Stone]].<ref>{{harvtxt|Birkhoff|1995}}, Theorem 27, p.&nbsp;130.</ref> Similarly, the Dedekind–MacNeille completion of a [[residuated lattice]] is a complete residuated lattice.{{sfnp|Gabbay|Shehtman|Skvortsov|2009}} However, the completion of a [[distributive lattice]] need not itself be distributive, and the completion of a [[modular lattice]] may not remain modular.<ref>{{harvtxt|Cotlar|1944}}; {{harvtxt|Funayama|1944}}.</ref>

The Dedekind–MacNeille completion is self-dual: the completion of the [[Duality (order theory)|dual]] of a partial order is the same as the dual of the completion.{{sfnp|Birkhoff|1995}}

The Dedekind–MacNeille completion of {{mvar|S}} has the same [[order dimension]] as does {{mvar|S}} itself.<ref>This result is frequently attributed to an unpublished 1961 Harvard University honors thesis by K. A. Baker, "Dimension, join-independence and breadth in partially ordered sets". It was published by {{harvtxt|Novák|1969}}.</ref>

In the [[Category (mathematics)|category]] of partially ordered sets and monotonic functions between partially ordered sets, the complete lattices form the [[injective object]]s for [[order-embedding]]s, and the Dedekind–MacNeille completion of {{mvar|S}} is the [[injective hull]] of&nbsp;{{mvar|S}}.{{sfnp|Banaschewski|Bruns|1967}}

==Algorithms==
Several researchers have investigated algorithms for constructing the Dedekind–MacNeille completion of a finite partially ordered set. The Dedekind–MacNeille completion may be exponentially larger than the partial order it comes from,{{sfnp|Ganter|Kuznetsov|1998}} and the time bounds for such algorithms are generally stated in an [[output-sensitive algorithm|output-sensitive way]], depending both on the number {{mvar|n}} of elements of the input partial order, and on the number {{mvar|c}} of elements of its completion.

===Constructing the set of cuts===
{{harvtxt|Ganter|Kuznetsov|1998}} describe an incremental algorithm, in which the input partial order is built up by adding one element at a time; at each step, the completion of the smaller partial order is expanded to form the completion of the larger partial order. In their method, the completion is represented by an explicit list of cuts. Each cut of the augmented partial order, except for the one whose two sets intersect in the new element, is either a cut from the previous partial order or is formed by adding the new element to one or the other side of a cut from the previous partial order, so their algorithm need only test pairs of sets of this form to determine which ones are cuts. The time for using their method to add a single element to the completion of a partial order is {{math|''O''(''cnw'')}} where {{mvar|w}} is the width of the partial order, that is, the size of its largest [[antichain]]. Therefore, the time to compute the completion of a given partial order is {{math|1=''O''(''cn''<sup>2</sup>''w'') = O(''cn''<sup>3</sup>)}}.{{sfnp|Ganter|Kuznetsov|1998}}

As {{harvtxt|Jourdan|Rampon|Jard|1994}} observe, the problem of listing all cuts in a partially ordered set can be formulated as a special case of a simpler problem, of listing all maximal [[antichain]]s in a different partially ordered set. If {{mvar|P}} is any partially ordered set, let {{mvar|Q}} be a partial order whose elements contain two copies of {{mvar|P}}: for each element {{mvar|x}} of {{mvar|P}}, {{mvar|Q}} contains two elements {{math|''x''<sub>0</sub>}} and {{math|''x''<sub>1</sub>}}, with {{math|''x<sub>i</sub>'' < ''y<sub>j</sub>''}} if and only if {{math|''x'' < ''y''}} and {{math|''i'' < ''j''}}. Then the cuts in {{mvar|P}} correspond one-for-one with the maximal antichains in {{mvar|Q}}: the elements in the lower set of a cut correspond to the elements with subscript 0 in an antichain, and the elements in the upper set of a cut correspond to the elements with subscript 1 in an antichain. Jourdan et al. describe an algorithm for finding maximal antichains that, when applied to the problem of listing all cuts in {{mvar|P}}, takes time {{math|1=''O''(''c''(''nw'' + ''w''<sup>3</sup>))}}, an improvement on the algorithm of {{harvtxt|Ganter|Kuznetsov|1998}} when the width {{mvar|w}} is small.{{sfnp|Jourdan|Rampon|Jard|1994}} Alternatively, a maximal antichain in {{mvar|Q}} is the same as a [[maximal independent set]] in the [[comparability graph]] of {{mvar|Q}}, or a [[maximal clique]] in the complement of the comparability graph, so algorithms for the [[clique problem]] or the independent set problem can also be applied to this version of the Dedekind–MacNeille completion problem.<ref>For the equivalence between algorithms for antichains in partial orders and for independent sets in comparability graphs, see {{harvtxt|Cameron|1985}}, p. 251.</ref>

===Constructing the covering graph===
The [[transitive reduction]] or covering graph of the Dedekind–MacNeille completion describes the order relation between its elements in a concise way:
each [[neighborhood (graph theory)|neighbor]] of a cut must remove an element of the original partial order from either the upper or lower set of the cut, so each vertex has at most {{mvar|n}} neighbors. Thus, the covering graph has {{mvar|c}} vertices and at most {{mvar|''cn''/2}} neighbors, a number that may be much smaller than the {{mvar|''c''<sup>2</sup>}} entries in a matrix that specifies all pairwise comparisons between elements. {{harvtxt|Nourine|Raynaud|1999}} show how to compute this covering graph efficiently; more generally, if {{mvar|B}} is any family of sets, they show how to compute the covering graph of the lattice of unions of subsets of {{mvar|B}}. In the case of the Dedekind–MacNeille lattice, {{mvar|B}} may be taken as the family of [[complement set]]s of principal ideals, and the unions of subsets of {{mvar|B}} are complements of the lower sets of cuts. The main idea for their algorithm is to generate unions of subsets of {{mvar|B}} incrementally (for each set in {{mvar|B}}, forming its union with all previously generated unions), represent the resulting family of sets in a [[trie]], and use the trie representation to test certain candidate pairs of sets for adjacency in the covering relation; it takes time {{math|''O''(''cn''<sup>2</sup>)}}. In later work, the same authors showed that the algorithm could be made fully incremental (capable of adding elements to the partial order one at a time) with the same total time bound.{{sfnp|Nourine|Raynaud|2002}}

==Notes==
{{reflist|colwidth=30em}}

==References==
{{refbegin|colwidth=30em}}
*{{citation
 | last1 = Banaschewski | first1 = B.
 | last2 = Bruns | first2 = G.
 | doi = 10.1007/BF01898828
 | mr = 0221984
 | journal = [[Archiv der Mathematik]]
 | pages = 369–377
 | title = Categorical characterization of the MacNeille completion
 | volume = 18
 | year = 1967| issue = 4
 | s2cid = 121216988
 }}.
*{{citation|title=Lattice Theory|first=Garrett|last=Birkhoff|authorlink=Garrett Birkhoff|edition=3rd|publisher=American Mathematical Society|series=Colloquium Publications|volume=25|year=1995|isbn=978-0-8218-1025-5|contribution=VI.9 Completion by Cuts|pages=126–128|url=https://books.google.com/books?id=o4bu3ex9BdkC&pg=PA126}}.
*{{citation
 | last = Bishop | first = Alan A.
 | mr = 0469839
 | issue = 3
 | journal = [[Algebra Universalis]]
 | pages = 349–353
 | title = A universal mapping characterization of the completion by cuts
 | volume = 8
 | year = 1978
 | doi=10.1007/bf02485405| s2cid = 121624631
 }}.
*{{citation
 | last = Cameron | first = Kathie
 | doi = 10.1007/BF00333130
 | issue = 3
 | journal = Order
 | mr = 824698
 | pages = 249–255
 | title = Antichain sequences
 | volume = 2
 | year = 1985}}
*{{citation
 | last = Cotlar | first = Mischa | author-link = Mischa Cotlar
 | mr = 0014062
 | journal = Univ. Nac. Tucumán. Revista A.
 | pages = 105–157
 | title = A method of construction of structures and its application to topological spaces and abstract arithmetic
 | volume = 4
 | year = 1944}}.
*{{citation | title=Introduction to Lattices and Order | title-link= Introduction to Lattices and Order | first1=B. A. | last1=Davey | first2=Hilary A. | last2=Priestley | author2-link = Hilary Priestley | edition=2nd | publisher=[[Cambridge University Press]] | year=2002 | isbn=978-0-521-78451-1 | contribution-url=https://books.google.com/books?id=vVVTxeuiyvQC&pg=PA166 | page=166 | contribution=7.38 The Dedekind–MacNeille completion | zbl=1002.06001 }}.
*{{citation
 | last = Funayama | first = Nenosuke
 | doi = 10.3792/pia/1195573210
 | mr = 0014063 | zbl=0063.01484 
 | journal = Proceedings of the Imperial Academy, Tokyo
 | pages = 1–2
 | title = On the completion by cuts of distributive lattices
 | volume = 20
 | year = 1944| doi-access = free
 }}.
*{{citation | title=Quantification in Nonclassical Logic, Volume 1 | volume=153 | series=Studies in logic and the foundations of mathematics | first1=Dov M. | last1=Gabbay | author1-link=Dov Gabbay | first2=Valentin | last2=Shehtman | first3=Dimitrij | last3=Skvortsov | publisher=Elsevier | year=2009 | isbn=978-0-444-52012-8 | zbl=1211.03002 | contribution=3.4.12 The Dedekind–MacNeille completion of a residuated lattice | url=https://books.google.com/books?id=Gy46SP7px7gC&pg=PA177 | pages=177–178}}.
*{{citation
 | last1 = Ganter | first1 = Bernhard
 | last2 = Kuznetsov | first2 = Sergei O.
 | contribution = Stepwise construction of the Dedekind-MacNeille completion
 | doi = 10.1007/BFb0054922
 | mr = 1673860 | zbl=0928.06004 
 | pages = 295–302
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Proc. 6th Int. Conf. Conceptual Structures: Theory, Tools and Applications (ICCS98)
 | volume = 1453
 | year = 1998}}.
*{{citation
 | last1 = Jourdan | first1 = Guy-Vincent
 | last2 = Rampon | first2 = Jean-Xavier
 | last3 = Jard | first3 = Claude
 | doi = 10.1007/BF02115811
 | mr = 1308475 | zbl=0814.06004 
 | issue = 3
 | journal = [[Order (journal)|Order]]
 | pages = 197–210
 | title = Computing on-line the lattice of maximal antichains of posets
 | volume = 11
 | year = 1994| s2cid = 120755660
 | url = https://hal.inria.fr/inria-00074400/file/RR-2271.pdf
 }}.
*{{citation
 | last = MacNeille | first = H. M. | authorlink = Holbrook Mann MacNeille
 | doi = 10.2307/1989739
 | mr = 1501929 | zbl=0017.33904  | jfm=63.0833.04 
 | issue = 3
 | journal = [[Transactions of the American Mathematical Society]]
 | pages = 416–460
 | title = Partially ordered sets
 | volume = 42
 | year = 1937| jstor = 1989739 | doi-access = free
 }}.
*{{citation
 | last1 = Nourine | first1 = Lhouari
 | last2 = Raynaud | first2 = Olivier
 | doi = 10.1016/S0020-0190(99)00108-8
 | mr = 1726978 | zbl=0998.06005 
 | issue = 5–6
 | journal = [[Information Processing Letters]]
 | pages = 199–204
 | title = A fast algorithm for building lattices
 | volume = 71
 | year = 1999| citeseerx = 10.1.1.502.3181
 }}.
*{{citation
 | last1 = Nourine | first1 = Lhouari
 | last2 = Raynaud | first2 = Olivier
 | doi = 10.1080/09528130210164152
 | zbl=1022.68027 
 | issue = 2
 | journal = [[Journal of Experimental and Theoretical Artificial Intelligence]]
 | pages = 217–227
 | title = A fast incremental algorithm for building lattices
 | volume = 14
 | year = 2002| s2cid = 38160433
 }}.
*{{citation
 | last = Novák | first = Vítězslav
 | doi = 10.1007/BF01350778
 | mr = 0240010
 | journal = [[Mathematische Annalen]]
 | pages = 337–342
 | title = Über eine Eigenschaft der Dedekind-MacNeilleschen Hülle
 | volume = 179
 | year = 1969| s2cid = 120963245
 }}.
*{{citation|title=A First Course in Mathematical Logic and Set Theory|first=Michael L.|last=O'Leary|publisher=John Wiley & Sons|year=2015|isbn=978-0-470-90588-3|page=276|url=https://books.google.com/books?id=Ci6kBgAAQBAJ&pg=PA276}}
*{{citation|title=Advanced Linear Algebra|volume=135|series=Graduate Texts in Mathematics|first=Steven|last=Roman|edition=3rd|publisher=Springer|year=2007|isbn=978-0-387-72831-5|pages=10–11|url=https://books.google.com/books?id=bSyQr-wUys8C&pg=PA10}}
*{{citation
 | last = Schmidt | first = Jürgen
 | doi = 10.1007/BF01900297
 | journal = Archiv der Mathematik
 | language = de
 | mr = 84484
 | pages = 241–249
 | title = Zur Kennzeichnung der Dedekind-MacNeilleschen Hülle einer geordneten Hülle
 | volume = 7
 | year = 1956}}
*{{citation|title=Ordered Sets: An Introduction |first1=Bernd S. W. |last1=Schröder |publisher=Birkhäuser|year=2003|isbn=978-1-4612-6591-7|contribution=5.3 Embeddings/The Dedekind/MacNeille Completion|url=https://books.google.com/books?id=2esoXnolEWgC&pg=PA119|pages=119–122}}.
{{refend}}

==External links==
*[http://planetmath.org/encyclopedia/MacNeilleCompletion.html MacNeille completion] in [[PlanetMath]]
*{{nlab|id=MacNeille+completion|title=MacNeille completion}}

{{DEFAULTSORT:Dedekind-MacNeille completion}}
[[Category:Order theory]]
[[Category:Lattice theory]]