Dedekind–MacNeille completion

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 cuts used by Dedekind to construct the real numbers from the rational numbers. It is also called the completion by cuts or normal completion.[1]
Order embeddings and lattice completions
[edit]A partially ordered set (poset) consists of a set of elements together with a binary relation x ≤ y on pairs of elements that is reflexive (x ≤ x for every x), transitive (if x ≤ y and y ≤ z then x ≤ z), and antisymmetric (if both x ≤ y and y ≤ x hold, then x = y). The usual numeric orderings on the integers or real numbers satisfy these properties; however, unlike the orderings on the numbers, a partial order may have two elements that are incomparable: neither x ≤ y nor y ≤ x holds. Another familiar example of a partial ordering is the inclusion ordering ⊆ on pairs of sets.[2]
If S is a partially ordered set, a completion of S means a complete lattice L with an order-embedding of S into L.[3] A complete lattice is a lattice in which every subset of elements of L has an infimum and supremum; this generalizes the analogous properties of the real numbers. An order-embedding is a function that maps distinct elements of S to distinct elements of L such that each pair of elements in S has the same ordering in L as they do in 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 π.[4]
A given partially ordered set may have several different completions. For instance, one completion of any partially ordered set S is the set of its downwardly closed subsets ordered by inclusion. S is embedded in this (complete) lattice by mapping each element x to the lower set of elements that are less than or equal to 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 S.[5] Among all possible lattice completions, the Dedekind–MacNeille completion is the smallest complete lattice with S embedded in it.[6]
Basic definitions and notation
[edit]Let be a partially ordered set. For every , define:
The set is called the principal upper set of , and is called the principal lower set of .
Additionally, for every , define:
Thus, is the set of all upper bounds of , while is the set of all lower bounds of .
For any set , let denote its power set.
Dedekind–MacNeille theorem
[edit]Let be a partially ordered set. Define:
Then:
- is a complete lattice.
- There exists an order embedding from into .
- If is a complete lattice and there exists an order embedding from into , then there also exists an order embedding from into .
The complete lattice is called the Dedekind–MacNeille completion of , denoted by .[7]
Proof of the Dedekind–MacNeille theorem
[edit]Lemma
[edit]To prove the Dedekind–MacNeille theorem, first observe that the pair of operations forms a Galois connection on , with both operations reversing inclusion.
To show this, let . It is necessary to prove that:
First, suppose that . Let . For every , since , it follows that . Therefore, . Since this holds for every , it follows that .
Conversely, suppose that . Let . For every , since , it follows that . Therefore, . Since this holds for every , it follows that .
Consequently,
which establishes the Galois connection.
Proof of the first statement
[edit]Define the function by:
Since is a Galois connection, the composition is a closure operator. In particular, it is extensive, monotone and idempotent.
By idempotence, the image of coincides with its set of fixed points. Thus,
The partially ordered set is a complete lattice, in which arbitrary unions are suprema and arbitrary intersections are infima.
A standard property of closure operators on complete lattices states that their fixed points, ordered by the inherited order, also form a complete lattice. Indeed, the infimum of any family of fixed points is their intersection, while their supremum is obtained by applying the closure operator to their union.
Since , it follows that is a complete lattice.
Proof of the second statement
[edit]Define by:
First, it must be shown that for every .
By the properties of the Galois connection, for every ,
Moreover, for every ,
Consequently,
Therefore, , so is well-defined.
Next, let such that . For every , one has , and hence . Thus,
Therefore, is order-preserving.
Conversely, suppose that . Since , it follows that:
and therefore . Thus, is order-reflecting.
Consequently,
and is an order embedding from into .
Proof of the third statement
[edit]Let be a complete lattice, and let be an order embedding.
Define by:
where denotes the supremum taken in .
Since is a complete lattice, every subset of has a supremum. Hence, is well-defined.
It remains to prove that is an order embedding.
First, suppose that and . Then . Since taking the supremum is monotone with respect to set inclusion,
Therefore, is order-preserving.
Conversely, suppose that satisfy
Let . By the definition of supremum,
Now let . By definition, for every . Since is an order embedding, it follows that for every .
Thus, is an upper bound of , so
Combining the inequalities gives:
Since is order-reflecting, . This holds for every , and therefore
Since this holds for every , it follows that .
Hence, is also order-reflecting. Therefore,
and is an order embedding, as required.
This proves that the Dedekind–MacNeille completion is the smallest complete lattice containing an order-embedded copy of , in the stated sense.
Examples
[edit]If is the set of rational numbers, viewed as a totally ordered set with the usual numerical order, then each element of the Dedekind–MacNeille completion of may be viewed as a Dedekind cut, and the Dedekind–MacNeille completion of is the total ordering on the real numbers, together with the two additional values .[8]
If S is an antichain (a set of elements no two of which are comparable) then the Dedekind–MacNeille completion of S consists of S itself together with two additional elements, a bottom element that is below every element in S and a top element that is above every element in S.[9]
If O is any finite set of objects, and A is any finite set of unary attributes for the objects in 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 x ≤ y when x is an object that has attribute y. For a partial order defined in this way, the Dedekind–MacNeille completion of S is known as a concept lattice, and it plays a central role in the field of formal concept analysis.[10]
Properties
[edit]The Dedekind–MacNeille completion of a partially ordered set S is the smallest complete lattice with S embedded in it, in the sense that, if L is any lattice completion of S, then the Dedekind–MacNeille completion is a partially ordered subset of L.[6] When S is finite, its completion is also finite, and has the smallest number of elements among all finite complete lattices containing S.[10]
The partially ordered set S is join-dense and meet-dense in the Dedekind–MacNeille completion; that is, every element of the completion is the join of some set of elements of S, and is also the meet of some set of elements in S.[11] The Dedekind–MacNeille completion is characterized among completions of S by this property.[12]
The Dedekind–MacNeille completion of a Boolean algebra is a complete Boolean algebra; this result is known as the Glivenko–Stone theorem, after Valery Ivanovich Glivenko and Marshall Stone.[13] Similarly, the Dedekind–MacNeille completion of a residuated lattice is a complete residuated lattice.[14] However, the completion of a distributive lattice need not itself be distributive, and the completion of a modular lattice may not remain modular.[15]
The Dedekind–MacNeille completion is self-dual: the completion of the dual of a partial order is the same as the dual of the completion.[16]
The Dedekind–MacNeille completion of S has the same order dimension as does S itself.[17]
In the category of partially ordered sets and monotonic functions between partially ordered sets, the complete lattices form the injective objects for order-embeddings, and the Dedekind–MacNeille completion of S is the injective hull of S.[18]
Relation to Dedekind cuts
[edit]In his original construction of the real numbers from the rational numbers , Richard Dedekind defined a cut as a pair of subsets satisfying the following conditions:[19]
- .
- .
- Both and are nonempty.
- is a lower set in ; that is, if and , then .
- has no greatest element.
Dedekind showed that the real numbers can be constructed from the collection of all such cuts. If the requirement that both sets be nonempty is removed, the construction also includes the two additional elements and , yielding the extended real number line.
For any nonempty proper subset , the pair is a Dedekind cut if and only if
Indeed, the equation implies that is a lower set with no greatest element, while is its complement in . Conversely, every Dedekind cut satisfies and .
Thus, the lower components of Dedekind cuts are precisely the elements of the Dedekind–MacNeille completion of , excluding and . Consequently, the Dedekind–MacNeille completion of the rational numbers is order-isomorphic to the extended real number line:
Generalized cuts
[edit]In his original 1937 paper, Holbrook Mann MacNeille generalized Dedekind's construction by defining cuts in arbitrary partially ordered sets. In Section 11.1 of the paper, MacNeille defined a cut using a pair of subsets, rather than a single lower set, and in Section 11.4 constructed the completion from such cuts.[7]
In modern notation, a generalized cut of a partially ordered set is a pair of subsets of satisfying:
It follows immediately that
Conversely, if satisfies , then is a generalized cut.
Therefore, the collection of generalized cuts provides an equivalent construction of the Dedekind–MacNeille completion. The ordering is defined by:
Equivalently,
Under this construction, each element is represented by the generalized cut .
Unlike the original Dedekind cuts of the rational numbers, generalized cuts do not require the two sets to be disjoint or to cover the entire partially ordered set. They may also contain the same element, or one of the sets may be empty.
Algorithms
[edit]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,[10] and the time bounds for such algorithms are generally stated in an output-sensitive way, depending both on the number n of elements of the input partial order, and on the number c of elements of its completion.
Constructing the set of cuts
[edit]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 O(cnw) where 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 O(cn2w) = O(cn3).[10]
As 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 antichains in a different partially ordered set. If P is any partially ordered set, let Q be a partial order whose elements contain two copies of P: for each element x of P, Q contains two elements x0 and x1, with xi < yj if and only if x < y and i < j. Then the cuts in P correspond one-for-one with the maximal antichains in 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 P, takes time O(c(nw + w3)), an improvement on the algorithm of Ganter & Kuznetsov (1998) when the width w is small.[20] Alternatively, a maximal antichain in Q is the same as a maximal independent set in the comparability graph of 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.[21]
Constructing the covering graph
[edit]The transitive reduction or covering graph of the Dedekind–MacNeille completion describes the order relation between its elements in a concise way: each 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 n neighbors. Thus, the covering graph has c vertices and at most cn/2 neighbors, a number that may be much smaller than the c2 entries in a matrix that specifies all pairwise comparisons between elements. Nourine & Raynaud (1999) show how to compute this covering graph efficiently; more generally, if B is any family of sets, they show how to compute the covering graph of the lattice of unions of subsets of B. In the case of the Dedekind–MacNeille lattice, B may be taken as the family of complement sets of principal ideals, and the unions of subsets of B are complements of the lower sets of cuts. The main idea for their algorithm is to generate unions of subsets of B incrementally (for each set in 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 O(cn2). 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.[22]
Notes
[edit]- ↑ Davey & Priestley (2002, p. 166); Schröder (2003, p. 119).
- ↑ Roman (2007).
- ↑ Schröder (2003), definition 5.3.1, p. 119.
- ↑ O'Leary (2015).
- ↑ Carpineto, Claudio; Romano, Giovanni (2004), Concept data analysis: theory and applications, John Wiley and Sons, p. 10, ISBN 978-0-470-85055-8.
- 1 2 Bishop (1978); Schröder (2003), Theorem 5.3.8, p. 121.
- 1 2 MacNeille, Holbrook Mann (1937). "Partially ordered sets". Transactions of the American Mathematical Society. 42 (3): 416–460. doi:10.1090/S0002-9947-1937-1501929-X.
- ↑ Davey & Priestley (2002), Example 7.44(1), p. 168; Schröder (2003), Example 5.3.3(2), p. 120.
- ↑ Davey & Priestley (2002), Example 7.44(2), p. 168.
- 1 2 3 4 Ganter & Kuznetsov (1998).
- ↑ Schröder (2003), Proposition 5.3.7, p. 121.
- ↑ Schmidt (1956).
- ↑ Birkhoff (1995), Theorem 27, p. 130.
- ↑ Gabbay, Shehtman & Skvortsov (2009).
- ↑ Cotlar (1944); Funayama (1944).
- ↑ Birkhoff (1995).
- ↑ 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 Novák (1969).
- ↑ Banaschewski & Bruns (1967).
- ↑ Dedekind, Richard. Essays on the Theory of Numbers.
- ↑ Jourdan, Rampon & Jard (1994).
- ↑ For the equivalence between algorithms for antichains in partial orders and for independent sets in comparability graphs, see Cameron (1985), p. 251.
- ↑ Nourine & Raynaud (2002).
References
[edit]- Banaschewski, B.; Bruns, G. (1967), "Categorical characterization of the MacNeille completion", Archiv der Mathematik, 18 (4): 369–377, doi:10.1007/BF01898828, MR 0221984, S2CID 121216988.
- Birkhoff, Garrett (1995), "VI.9 Completion by Cuts", Lattice Theory, Colloquium Publications, vol. 25 (3rd ed.), American Mathematical Society, pp. 126–128, ISBN 978-0-8218-1025-5.
- Bishop, Alan A. (1978), "A universal mapping characterization of the completion by cuts", Algebra Universalis, 8 (3): 349–353, doi:10.1007/bf02485405, MR 0469839, S2CID 121624631.
- Cameron, Kathie (1985), "Antichain sequences", Order, 2 (3): 249–255, doi:10.1007/BF00333130, MR 0824698
- Cotlar, Mischa (1944), "A method of construction of structures and its application to topological spaces and abstract arithmetic", Univ. Nac. Tucumán. Revista A., 4: 105–157, MR 0014062.
- Davey, B. A.; Priestley, Hilary A. (2002), "7.38 The Dedekind–MacNeille completion", Introduction to Lattices and Order (2nd ed.), Cambridge University Press, p. 166, ISBN 978-0-521-78451-1, Zbl 1002.06001.
- Funayama, Nenosuke (1944), "On the completion by cuts of distributive lattices", Proceedings of the Imperial Academy, Tokyo, 20: 1–2, doi:10.3792/pia/1195573210, MR 0014063, Zbl 0063.01484.
- Gabbay, Dov M.; Shehtman, Valentin; Skvortsov, Dimitrij (2009), "3.4.12 The Dedekind–MacNeille completion of a residuated lattice", Quantification in Nonclassical Logic, Volume 1, Studies in logic and the foundations of mathematics, vol. 153, Elsevier, pp. 177–178, ISBN 978-0-444-52012-8, Zbl 1211.03002.
- Ganter, Bernhard; Kuznetsov, Sergei O. (1998), "Stepwise construction of the Dedekind-MacNeille completion", Proc. 6th Int. Conf. Conceptual Structures: Theory, Tools and Applications (ICCS98), Lecture Notes in Computer Science, vol. 1453, Springer-Verlag, pp. 295–302, doi:10.1007/BFb0054922, MR 1673860, Zbl 0928.06004.
- Jourdan, Guy-Vincent; Rampon, Jean-Xavier; Jard, Claude (1994), "Computing on-line the lattice of maximal antichains of posets" (PDF), Order, 11 (3): 197–210, doi:10.1007/BF02115811, MR 1308475, S2CID 120755660, Zbl 0814.06004.
- MacNeille, H. M. (1937), "Partially ordered sets", Transactions of the American Mathematical Society, 42 (3): 416–460, doi:10.2307/1989739, JFM 63.0833.04, JSTOR 1989739, MR 1501929, Zbl 0017.33904.
- Nourine, Lhouari; Raynaud, Olivier (1999), "A fast algorithm for building lattices", Information Processing Letters, 71 (5–6): 199–204, doi:10.1016/S0020-0190(99)00108-8, MR 1726978, Zbl 0998.06005.
- Nourine, Lhouari; Raynaud, Olivier (2002), "A fast incremental algorithm for building lattices", Journal of Experimental and Theoretical Artificial Intelligence, 14 (2): 217–227, doi:10.1080/09528130210164152, S2CID 38160433, Zbl 1022.68027.
- Novák, Vítězslav (1969), "Über eine Eigenschaft der Dedekind-MacNeilleschen Hülle", Mathematische Annalen, 179: 337–342, doi:10.1007/BF01350778, MR 0240010, S2CID 120963245.
- O'Leary, Michael L. (2015), A First Course in Mathematical Logic and Set Theory, John Wiley & Sons, p. 276, ISBN 978-0-470-90588-3
- Roman, Steven (2007), Advanced Linear Algebra, Graduate Texts in Mathematics, vol. 135 (3rd ed.), Springer, pp. 10–11, ISBN 978-0-387-72831-5
- Schmidt, Jürgen (1956), "Zur Kennzeichnung der Dedekind-MacNeilleschen Hülle einer geordneten Hülle", Archiv der Mathematik (in German), 7: 241–249, doi:10.1007/BF01900297, MR 0084484
- Schröder, Bernd S. W. (2003), "5.3 Embeddings/The Dedekind/MacNeille Completion", Ordered Sets: An Introduction, Birkhäuser, pp. 119–122, ISBN 978-1-4612-6591-7.