Dedekind–MacNeille completion

From testwiki
Revision as of 09:00, 11 January 2024 by imported>Sir Ibee (Open access status updates in citations with OAbot #oabot)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Template:Bots Template:Short description Template:Redirect

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 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

A partially ordered set (poset) consists of a set of elements together with a binary relation Template:Math on pairs of elements that is reflexive (Template:Math for every x), transitive (if Template:Math and Template:Math then Template:Math), and antisymmetric (if both Template:Math and Template:Math hold, then Template:Math). 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 Template:Math nor Template:Math holds. Another familiar example of a partial ordering is the inclusion ordering ⊆ on pairs of sets.Template:Sfnp

If Template:Mvar is a partially ordered set, a completion of Template:Mvar means a complete lattice Template:Mvar with an order-embedding of Template:Mvar into Template:Mvar.[2] A complete lattice is a lattice in which every subset of elements of Template:Mvar 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 Template:Mvar to distinct elements of Template:Mvar such that each pair of elements in Template:Mvar has the same ordering in Template:Mvar as they do in Template:Mvar. 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 Template:Pi.Template:Sfnp

A given partially ordered set may have several different completions. For instance, one completion of any partially ordered set Template:Mvar is the set of its downwardly closed subsets ordered by inclusion. Template:Mvar is embedded in this (complete) lattice by mapping each element Template:Mvar to the lower set of elements that are less than or equal to Template:Mvar. 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 Template:Mvar.[3] Among all possible lattice completions, the Dedekind–MacNeille completion is the smallest complete lattice with Template:Mvar embedded in it.[4]

Definition

For each subset Template:Mvar of a partially ordered set Template:Mvar, let Template:Math denote the set of upper bounds of Template:Mvar; that is, an element Template:Mvar of Template:Mvar belongs to Template:Math whenever Template:Mvar is greater than or equal to every element in Template:Mvar. Symmetrically, let Template:Math denote the set of lower bounds of Template:Mvar, the elements that are less than or equal to every element in Template:Mvar. Then the Dedekind–MacNeille completion of Template:Mvar consists of all subsets Template:Mvar for which

Template:Math;

it is ordered by inclusion: Template:Math in the completion if and only if Template:Math as sets.[5]

An element Template:Mvar of Template:Mvar embeds into the completion as its principal ideal, the set Template:Math of elements less than or equal to Template:Mvar. Then Template:Math is the set of elements greater than or equal to Template:Mvar, and Template:Math, showing that Template:Math is indeed a member of the completion. The mapping from Template:Mvar to Template:Math is an order-embedding.[5]

An alternative definition of the Dedekind–MacNeille completion that more closely resembles the definition of a Dedekind cut is sometimes used.[6] In a partially ordered set Template:Mvar, define a cut to be a pair of sets Template:Math for which Template:Math and Template:Math. If Template:Math is a cut then A satisfies the equation Template:Math, and conversely if Template:Math then Template:Math 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.Template:Sfnp

With the alternative definition, both the join and the meet operations of the complete lattice have symmetric descriptions: if Template:Math are the cuts in any family of cuts, then the meet of these cuts is the cut Template:Math where Template:Math, and the join is the cut Template:Math where Template:Math.Template:Sfnp

Examples

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 ±∞.[7]

If Template:Mvar is an antichain (a set of elements no two of which are comparable) then the Dedekind–MacNeille completion of Template:Mvar consists of Template:Mvar itself together with two additional elements, a bottom element that is below every element in Template:Mvar and a top element that is above every element in Template:Mvar.[8]

If Template:Mvar is any finite set of objects, and Template:Mvar is any finite set of unary attributes for the objects in Template:Mvar, 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 Template:Math when Template:Mvar is an object that has attribute Template:Mvar. For a partial order defined in this way, the Dedekind–MacNeille completion of Template:Mvar is known as a concept lattice, and it plays a central role in the field of formal concept analysis.Template:Sfnp

Properties

The Dedekind–MacNeille completion of a partially ordered set Template:Mvar is the smallest complete lattice with Template:Mvar embedded in it, in the sense that, if Template:Mvar is any lattice completion of Template:Mvar, then the Dedekind–MacNeille completion is a partially ordered subset of Template:Mvar.[4] When Template:Mvar is finite, its completion is also finite, and has the smallest number of elements among all finite complete lattices containing Template:Mvar.Template:Sfnp

The partially ordered set Template:Mvar 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 Template:Mvar, and is also the meet of some set of elements in Template:Mvar.[9] The Dedekind–MacNeille completion is characterized among completions of Template:Mvar by this property.Template:Sfnp

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.[10] Similarly, the Dedekind–MacNeille completion of a residuated lattice is a complete residuated lattice.Template:Sfnp However, the completion of a distributive lattice need not itself be distributive, and the completion of a modular lattice may not remain modular.[11]

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.Template:Sfnp

The Dedekind–MacNeille completion of Template:Mvar has the same order dimension as does Template:Mvar itself.[12]

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 Template:Mvar is the injective hull of Template:Mvar.Template:Sfnp

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,Template:Sfnp and the time bounds for such algorithms are generally stated in an output-sensitive way, depending both on the number Template:Mvar of elements of the input partial order, and on the number Template:Mvar of elements of its completion.

Constructing the set of cuts

Template:Harvtxt 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 Template:Math where Template:Mvar 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 Template:Math.Template:Sfnp

As Template:Harvtxt 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 Template:Mvar is any partially ordered set, let Template:Mvar be a partial order whose elements contain two copies of Template:Mvar: for each element Template:Mvar of Template:Mvar, Template:Mvar contains two elements Template:Math and Template:Math, with Template:Math if and only if Template:Math and Template:Math. Then the cuts in Template:Mvar correspond one-for-one with the maximal antichains in Template:Mvar: 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 Template:Mvar, takes time Template:Math, an improvement on the algorithm of Template:Harvtxt when the width Template:Mvar is small.Template:Sfnp Alternatively, a maximal antichain in Template:Mvar is the same as a maximal independent set in the comparability graph of Template:Mvar, 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.[13]

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 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 Template:Mvar neighbors. Thus, the covering graph has Template:Mvar vertices and at most Template:Mvar neighbors, a number that may be much smaller than the Template:Mvar entries in a matrix that specifies all pairwise comparisons between elements. Template:Harvtxt show how to compute this covering graph efficiently; more generally, if Template:Mvar is any family of sets, they show how to compute the covering graph of the lattice of unions of subsets of Template:Mvar. In the case of the Dedekind–MacNeille lattice, Template:Mvar may be taken as the family of complement sets of principal ideals, and the unions of subsets of Template:Mvar are complements of the lower sets of cuts. The main idea for their algorithm is to generate unions of subsets of Template:Mvar incrementally (for each set in Template:Mvar, 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 Template:Math. 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.Template:Sfnp

Notes

Template:Reflist

References

Template:Refbegin

Template:Refend

  1. ↑ Template:Harvtxt; Template:Harvtxt.
  2. ↑ Template:Harvtxt, definition 5.3.1, p. 119.
  3. ↑ Template:Citation.
  4. ↑ 4.0 4.1 Template:Harvtxt; Template:Harvtxt, Theorem 5.3.8, p. 121.
  5. ↑ 5.0 5.1 Template:Harvtxt, Lemma 11.8, p.  444; Template:Harvtxt, Lemma 3.9(i), p. 166.
  6. ↑ This is the definition originally used by Template:Harvtxt, for instance.
  7. ↑ Template:Harvtxt, Example 7.44(1), p. 168; Template:Harvtxt, Example 5.3.3(2), p. 120.
  8. ↑ Template:Harvtxt, Example 7.44(2), p. 168.
  9. ↑ Template:Harvtxt, Proposition 5.3.7, p. 121.
  10. ↑ Template:Harvtxt, Theorem 27, p. 130.
  11. ↑ Template:Harvtxt; Template:Harvtxt.
  12. ↑ 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 Template:Harvtxt.
  13. ↑ For the equivalence between algorithms for antichains in partial orders and for independent sets in comparability graphs, see Template:Harvtxt, p. 251.
Retrieved from "https://en.wiki.beta.math.wmflabs.org/w/index.php?title=Dedekind–MacNeille_completion&oldid=26309"