Dedekind–MacNeille completion
Encyclopedia
In order-theoretic mathematics
, the Dedekind–MacNeille completion of a partially ordered set
(also called the completion by cuts or normal completion) is the smallest complete lattice
that contains the given partial order. 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.
consists of a set of elements together with a binary relation
on pairs of elements that is reflexive ( for every x), transitive (if and then ), and antisymmetric (if both and hold, then ). 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 nor holds. Another familiar example of a partial ordering is the inclusion ordering ⊆ on pairs of sets.
If is a partially ordered set, a completion of means a complete lattice
with an order-embedding
of into . The notion of a complete lattice means that every subset of elements of has a unique least upper bound and a unique greatest lower bound; this generalizes the analogous upper bound and lower bound properties of the real number
s. The notion of an order-embedding enforces the requirements that distinct elements of must be mapped to distinct elements of , and that each pair of elements in has the same ordering in as they do in . The real numbers (together with +∞ and −∞) are 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 upper bound .
A given partially ordered set may have several different completions. For instance, one completion of any partially ordered set is the set of its downwardly closed subsets ordered by inclusion
. is embedded in this lattice by sending each element to the lower set that it generates. 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 . Among all possible lattice completions, the Dedekind–MacNeille completion is the smallest complete lattice with embedded in it.
it is ordered by inclusion: in the completion if and only if as sets.
An element of embeds into the completion as its principal ideal
, the set of elements less than or equal to . Then is the set of elements greater than or equal to , and , showing that is indeed a member of the completion. It is straightforward to verify that the mapping from to is an order-embedding.
An alternative definition of the Dedekind–MacNeille completion that more closely resembles the definition of a Dedekind cut is sometimes used. In a partially ordered set , define a cut to be a pair of sets for which and . If is a cut then A satisfies the equation , and conversely if then 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.
With the alternative definition, both the join and the meet operations of the complete lattice have symmetric descriptions: if are the cuts in any family of cuts, then the meet of these cuts is the cut where , and the join is the cut where .
s, viewed as a totally ordered set with the usual numerical order, then each element of the Dedekind–MacNeille completion of Q may be viewed as a Dedekind cut
, and the Dedekind–MacNeille completion of Q is the total ordering on the real number
s, together with the two additional values ±∞. The construction of the real numbers from the rational numbers is an example of the Dedekind completion of a totally ordered set, and the Dedekind–MacNeille completion generalizes this concept from total orders to partial orders.
If is an antichain
(a set of elements no two of which are comparable) then the Dedekind–MacNeille completion of consists of itself together with two additional elements, a bottom element that is below every element in and a top element that is above every element in .
If is any finite set of objects, and is any finite set of binary attributes for the objects in , 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 when is an object that has attribute . For a partial order defined in this way, the Dedekind–MacNeille completion of is known as a concept lattice, and it plays a central role in the field of formal concept analysis
.
The partially ordered set 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 , and is also the meet of some set of elements in . The Dedekind–MacNeille completion is characterized among completions of by this property.
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. Similarly, the Dedekind–MacNeille completion of a residuated lattice
is a complete residuated lattice. However, the completion of a distributive lattice
need not itself be distributive, and the completion of a modular lattice
may not remain modular.
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.
The Dedekind–MacNeille completion of has the same order dimension
as does itself.
In the 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 is the injective hull of .
. Therefore, the time to compute the completion of a given partial order is .
As 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 is any partially ordered set, let be a partial order whose elements contain two copies of : for each element of , contains two elements and , with if and only if and . Then the cuts in correspond one-for-one with the maximal antichains in : 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 , takes time , an improvement on the algorithm of when the width is small. Alternatively, a maximal antichain in is the same as a maximal independent set
in the comparability graph
of , 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.
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 neighbors. Thus, the covering graph has vertices and at most neighbors, a number that may be much smaller than the entries in a matrix that specifies all pairwise comparisons between elements. show how to compute this covering graph efficiently; more generally, if is any family of sets, they show how to compute the covering graph of the lattice of unions of subsets of . In the case of the Dedekind–MacNeille lattice, may be taken as the family of complement sets of principal ideals, and the unions of subsets of are complements of the lower sets of cuts. The main idea for their algorithm is to generate unions of subsets of incrementally (for each set in , 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 . 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.
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...
, the Dedekind–MacNeille completion of a partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
(also called the completion by cuts or normal completion) is the smallest complete lattice
Complete lattice
In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...
that contains the given partial order. It is named after Holbrook Mann MacNeille
Holbrook Mann MacNeille
Holbrook Mann MacNeille was an American mathematician who worked for the United States Atomic Energy Commission before becoming the first Executive Director of the American Mathematical Society.-Personal life:...
whose 1937 paper first defined and constructed it, and after Richard Dedekind
Richard Dedekind
Julius Wilhelm Richard Dedekind was a German mathematician who did important work in abstract algebra , algebraic number theory and the foundations of the real numbers.-Life:...
because its construction generalizes the Dedekind cut
Dedekind cut
In mathematics, a Dedekind cut, named after Richard Dedekind, is a partition of the rationals into two non-empty parts A and B, such that all elements of A are less than all elements of B, and A contains no greatest element....
s used by Dedekind to construct the real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s from the rational number
Rational number
In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
s.
Order embeddings and lattice completions
A partially ordered setPartially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
consists of a set of elements together with a binary relation
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
on pairs of elements that is reflexive ( for every x), transitive (if and then ), and antisymmetric (if both and hold, then ). 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 nor holds. Another familiar example of a partial ordering is the inclusion ordering ⊆ on pairs of sets.
If is a partially ordered set, a completion of means a complete lattice
Complete lattice
In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...
with an order-embedding
Order-embedding
In mathematical order theory, an order-embedding is a special kind of monotone function, which provides a way to include one partially ordered set into another. Like Galois connections, order-embeddings constitute a notion which is strictly weaker than the concept of an order isomorphism...
of into . The notion of a complete lattice means that every subset of elements of has a unique least upper bound and a unique greatest lower bound; this generalizes the analogous upper bound and lower bound properties of the real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s. The notion of an order-embedding enforces the requirements that distinct elements of must be mapped to distinct elements of , and that each pair of elements in has the same ordering in as they do in . The real numbers (together with +∞ and −∞) are 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 upper bound .
A given partially ordered set may have several different completions. For instance, one completion of any partially ordered set is the set of its downwardly closed subsets ordered by inclusion
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
. is embedded in this lattice by sending each element to the lower set that it generates. The result is a distributive lattice
Distributive lattice
In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...
and is used in Birkhoff's representation theorem
Birkhoff's representation theorem
In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice can be represented as finite sets, in such a way that the lattice operations correspond to unions and intersections of sets...
. However, it may have many more elements than are needed to form a completion of . Among all possible lattice completions, the Dedekind–MacNeille completion is the smallest complete lattice with embedded in it.
Definition
For each subset of a partially ordered set , let denote the set of upper bounds of ; that is, an element of belongs to whenever is greater than or equal to every element in . Symmetrically, let denote the set of lower bounds of , the elements that are less than or equal to every element in . Then the Dedekind–MacNeille completion of consists of all subsets for which- ;
it is ordered by inclusion: in the completion if and only if as sets.
An element of embeds into the completion as its principal ideal
Ideal (order theory)
In mathematical order theory, an ideal is a special subset of a partially ordered set . Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion...
, the set of elements less than or equal to . Then is the set of elements greater than or equal to , and , showing that is indeed a member of the completion. It is straightforward to verify that the mapping from to is an order-embedding.
An alternative definition of the Dedekind–MacNeille completion that more closely resembles the definition of a Dedekind cut is sometimes used. In a partially ordered set , define a cut to be a pair of sets for which and . If is a cut then A satisfies the equation , and conversely if then 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.
With the alternative definition, both the join and the meet operations of the complete lattice have symmetric descriptions: if are the cuts in any family of cuts, then the meet of these cuts is the cut where , and the join is the cut where .
Examples
If Q is the set of rational numberRational number
In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
s, viewed as a totally ordered set with the usual numerical order, then each element of the Dedekind–MacNeille completion of Q may be viewed as a Dedekind cut
Dedekind cut
In mathematics, a Dedekind cut, named after Richard Dedekind, is a partition of the rationals into two non-empty parts A and B, such that all elements of A are less than all elements of B, and A contains no greatest element....
, and the Dedekind–MacNeille completion of Q is the total ordering on the real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s, together with the two additional values ±∞. The construction of the real numbers from the rational numbers is an example of the Dedekind completion of a totally ordered set, and the Dedekind–MacNeille completion generalizes this concept from total orders to partial orders.
If is an antichain
Antichain
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable. Let S be a partially ordered set...
(a set of elements no two of which are comparable) then the Dedekind–MacNeille completion of consists of itself together with two additional elements, a bottom element that is below every element in and a top element that is above every element in .
If is any finite set of objects, and is any finite set of binary attributes for the objects in , 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 when is an object that has attribute . For a partial order defined in this way, the Dedekind–MacNeille completion of is known as a concept lattice, and it plays a central role in the field of formal concept analysis
Formal concept analysis
Formal concept analysis is a principled way of automatically deriving an ontology from a collection of objects and their properties. The term was introduced by Rudolf Wille in 1984, and builds on applied lattice and order theory that was developed by Birkhoff and others in the 1930s.-Intuitive...
.
Properties
The Dedekind–MacNeille completion is the smallest complete lattice with embedded in it, in the sense that, if is any lattice completion of , then the Dedekind–MacNeille completion is a sublattice of . When is finite, its completion is also finite, and has the smallest number of elements among all finite complete lattices containing .The partially ordered set 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 , and is also the meet of some set of elements in . The Dedekind–MacNeille completion is characterized among completions of by this property.
The Dedekind–MacNeille completion of a Boolean algebra is a complete Boolean algebra
Complete Boolean algebra
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum . Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing...
; this result is known as the Glivenko–Stone theorem, after Valery Ivanovich Glivenko
Valery Ivanovich Glivenko
Valery Ivanovich Glivenko / January 2, 1897 in Kiev, died February 15, 1940 in Moscow) was a Soviet mathematician. He worked in foundations of mathematics and probability theory. He taught at Liebknecht University until his death at age 43....
and Marshall Stone. Similarly, the Dedekind–MacNeille completion of a residuated lattice
Residuated lattice
In abstract algebra, a residuated lattice is an algebraic structure that is simultaneously a lattice x ≤ y and a monoid x•y which admits operations x\z and z/y loosely analogous to division or implication when x•y is viewed as multiplication or conjunction respectively...
is a complete residuated lattice. However, the completion of a distributive lattice
Distributive lattice
In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...
need not itself be distributive, and the completion of a modular lattice
Modular lattice
In the branch of mathematics called order theory, a modular lattice is a lattice that satisfies the following self-dual condition:Modular law: x ≤ b implies x ∨ = ∧ b,where ≤ is the partial order, and ∨ and ∧ are...
may not remain modular.
The Dedekind–MacNeille completion is self-dual: the completion of the dual
Duality (order theory)
In the mathematical area of order theory, every partially ordered set P gives rise to a dual partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the set with the inverse order, i.e. x ≤ y holds in Pop if and only if y ≤ x holds in P...
of a partial order is the same as the dual of the completion.
The Dedekind–MacNeille completion of has the same order dimension
Order dimension
In mathematics, the dimension of a partially ordered set is the smallest number of total orders the intersection of which gives rise to the partial order....
as does itself.
In the category
Category (mathematics)
In mathematics, a category is an algebraic structure that comprises "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the category of sets, whose...
of partially ordered sets and monotonic functions between partially ordered sets, the complete lattices form the injective object
Injective object
In mathematics, especially in the field of category theory, the concept of injective object is a generalization of the concept of injective module. This concept is important in homotopy theory and in theory of model categories...
s for order-embedding
Order-embedding
In mathematical order theory, an order-embedding is a special kind of monotone function, which provides a way to include one partially ordered set into another. Like Galois connections, order-embeddings constitute a notion which is strictly weaker than the concept of an order isomorphism...
s, and the Dedekind–MacNeille completion of is the injective hull of .
Algorithms
Several researchers have investigated algorithms for constructing the Dedekind–MacNeille completion of a finite partially ordered set. Because the Dedekind–MacNeille completion may be exponentially larger than the partial order it comes from, it is necessary to measure the time bounds for such algorithms both in terms of the number of elements of the input partial order, but also in terms of the number of elements of its completion, and sometimes also in terms of additional measures of the complexity of the input and output. The format in which the output lattice is represented may also affect the running time of its construction algorithms; for instance, if it is represented as a logical matrix specifying the result of a comparison between each pair of lattice elements, the output size is and this will be a lower bound on the time for a construction algorithm.Constructing the set of cuts
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 where is the width of the partial order, that is, the size of its largest antichainAntichain
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable. Let S be a partially ordered set...
. Therefore, the time to compute the completion of a given partial order is .
As 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
Antichain
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable. Let S be a partially ordered set...
s in a different partially ordered set. If is any partially ordered set, let be a partial order whose elements contain two copies of : for each element of , contains two elements and , with if and only if and . Then the cuts in correspond one-for-one with the maximal antichains in : 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 , takes time , an improvement on the algorithm of when the width is small. Alternatively, a maximal antichain in is the same as a maximal independent set
Maximal independent set
In graph theory, a maximal independent set or maximal stable set is an independent set that is not a subset of any other independent set. That is, it is a set S such that every edge of the graph has at least one endpoint not in S and every vertex not in S has at least one neighbor in S...
in the comparability graph
Comparability graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...
of , or a maximal clique in the complement of the comparability graph, so algorithms for the clique problem
Clique problem
In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs in a graph, i.e., sets of elements where each pair of elements is connected....
or the independent set problem can also be applied to this version of the Dedekind–MacNeille completion problem.
Constructing the covering graph
The transitive reductionTransitive reduction
In mathematics, a transitive reduction of a binary relation R on a set X is a minimal relation R' on X such that the transitive closure of R' is the same as the transitive closure of R. If the transitive closure of R is antisymmetric and finite, then R' is unique...
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 neighbors. Thus, the covering graph has vertices and at most neighbors, a number that may be much smaller than the entries in a matrix that specifies all pairwise comparisons between elements. show how to compute this covering graph efficiently; more generally, if is any family of sets, they show how to compute the covering graph of the lattice of unions of subsets of . In the case of the Dedekind–MacNeille lattice, may be taken as the family of complement sets of principal ideals, and the unions of subsets of are complements of the lower sets of cuts. The main idea for their algorithm is to generate unions of subsets of incrementally (for each set in , forming its union with all previously generated unions), represent the resulting family of sets in a trie
Trie
In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the...
, and use the trie representation to test certain candidate pairs of sets for adjacency in the covering relation; it takes time . 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.
External links
- MacNeille completion in PlanetMathPlanetMathPlanetMath is a free, collaborative, online mathematics encyclopedia. The emphasis is on rigour, openness, pedagogy, real-time content, interlinked content, and also community of about 24,000 people with various maths interests. Intended to be comprehensive, the project is hosted by the Digital...
- MacNeille completion in nLabNLabnLab is a wiki-lab of a novel kind, for collaborative work on mathematics, physics, and philosophy, including original research, with a focus on category theory. The nLab espouses the n-point of view : that category theory and higher category theory provide a useful unifying viewpoint for...