HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, specifically
order theory Order theory is a branch of mathematics that investigates the 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 intr ...
, the Dedekind–MacNeille completion of a
partially ordered set In mathematics, especially order theory, a partial order on a Set (mathematics), set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements need ...
is the smallest
complete lattice In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum ( join) and an infimum ( meet). A conditionally complete lattice satisfies at least one of these properties for bounded subsets. For compariso ...
that contains it. It is named after
Holbrook Mann MacNeille Holbrook Mann MacNeille (May 11, 1907 – September 30, 1973) was an Americans, American mathematician who worked for the United States Atomic Energy Commission before becoming the first Executive Director of the American Mathematical Society. ...
whose 1937 paper first defined and constructed it, and after
Richard Dedekind Julius Wilhelm Richard Dedekind (; ; 6 October 1831 – 12 February 1916) was a German mathematician who made important contributions to number theory, abstract algebra (particularly ring theory), and the axiomatic foundations of arithmetic. H ...
because its construction generalizes the
Dedekind cut In mathematics, Dedekind cuts, named after German mathematician Richard Dedekind (but previously considered by Joseph Bertrand), are а method of construction of the real numbers from the rational numbers. A Dedekind cut is a partition of a set, ...
s used by Dedekind to construct the
real number In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...
s from the
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (for example, The set of all ...
s. It is also called the completion by cuts or normal completion.


Order embeddings and lattice completions

A
partially ordered set In mathematics, especially order theory, a partial order on a Set (mathematics), set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements need ...
(poset) consists of a
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
of elements together with a
binary relation In mathematics, a binary relation associates some elements of one Set (mathematics), set called the ''domain'' with some elements of another set called the ''codomain''. Precisely, a binary relation over sets X and Y is a set of ordered pairs ...
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
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
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 nor holds. Another familiar example of a partial ordering is the
inclusion Inclusion or Include may refer to: Sociology * Social inclusion, action taken to support people of different backgrounds sharing life together. ** Inclusion (disability rights), promotion of people with disabilities sharing various aspects of lif ...
ordering ⊆ on pairs of sets. If is a partially ordered set, a ''completion'' of means a
complete lattice In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum ( join) and an infimum ( meet). A conditionally complete lattice satisfies at least one of these properties for bounded subsets. For compariso ...
with an order-embedding of into . A complete lattice is a lattice in which every subset of elements of has an
infimum and supremum In mathematics, the infimum (abbreviated inf; : infima) of a subset S of a partially ordered set P is the greatest element in P that is less than or equal to each element of S, if such an element exists. If the infimum of S exists, it is unique, ...
; this generalizes the analogous properties of the
real number In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...
s. An order-embedding is a function that maps distinct elements of to distinct elements of such that each pair of elements in has the same ordering in as they do in . The
extended real number line In mathematics, the extended real number system is obtained from the real number system \R by adding two elements denoted +\infty and -\infty that are respectively greater and lower than every real number. This allows for treating the potential ...
(real numbers together with +∞ and −∞) is a completion in this sense of the rational numbers: the set of rational numbers does not have a rational least upper bound, but in the real numbers it has the least 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 Inclusion or Include may refer to: Sociology * Social inclusion, action taken to support people of different backgrounds sharing life together. ** Inclusion (disability rights), promotion of people with disabilities sharing various aspects of lif ...
. is embedded in this (complete) lattice by mapping each element to the lower set of elements that are less than or equal to . The result is a
distributive lattice In mathematics, a distributive lattice is a lattice (order), lattice in which the operations of join and meet distributivity, distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice o ...
and is used in
Birkhoff's representation theorem :''This is about lattice theory. For other similarly named results, see Birkhoff's theorem (disambiguation).'' In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice ...
. 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 In mathematics, specifically ring theory, a principal ideal is an ideal I in a ring R that is generated by a single element a of R through multiplication by every element of R. The term also has another, similar meaning in order theory, where ...
, 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. The mapping from to is an order-embedding., Lemma 11.8, p.  444; , Lemma 3.9(i), p. 166. 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 number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (for example, The set of all ...
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 In mathematics, Dedekind cuts, named after German mathematician Richard Dedekind (but previously considered by Joseph Bertrand), are а method of construction of the real numbers from the rational numbers. A Dedekind cut is a partition of a set, ...
, and the Dedekind–MacNeille completion of \Q is the total ordering on the
real number In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...
s, together with the two additional values \pm\infty. If is an
antichain In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable. The size of the largest antichain in a partially ordered set is known as its wid ...
(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 unary 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 In information science, formal concept analysis (FCA) is a principled way of deriving a ''concept hierarchy'' or formal ontology from a collection of objects and their properties. Each concept in the hierarchy represents the objects sharing som ...
.


Properties

The Dedekind–MacNeille completion of a partially ordered set 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 partially ordered subset of .; , Theorem 5.3.8, p. 121. 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 the 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 In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variable (mathematics), variables are the truth values ''true'' and ''false'', usually denot ...
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 In abstract algebra, a residuated lattice is an algebraic structure that is simultaneously a lattice (order), lattice ''x'' ≤ ''y'' and a monoid ''x''•''y'' which admits operations ''x''\''z'' and ''z''/''y'', loosely analogous to division or i ...
is a complete residuated lattice. However, the completion of a
distributive lattice In mathematics, a distributive lattice is a lattice (order), lattice in which the operations of join and meet distributivity, distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice o ...
need not itself be distributive, and the completion of a
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: implies where are arbitrary elements in the lattice,  ≤  is the partial order, and & ...
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 Category, plural categories, may refer to: General uses *Classification, the general act of allocating things to classes/categories Philosophy * Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) * Category ( ...
of partially ordered sets and monotonic functions between partially ordered sets, the complete lattices form the
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 cohomology, in homotopy theory and in the theory of model categories. ...
s for order-embeddings, and the Dedekind–MacNeille completion of is the
injective hull In mathematics, particularly in algebra, the injective hull (or injective envelope) of a module is both the smallest injective module containing it and the largest essential extension of it. Injective hulls were first described in . Definition ...
of .


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


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
antichain In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable. The size of the largest antichain in a partially ordered set is known as its wid ...
. 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 In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable. The size of the largest antichain in a partially ordered set is known as its wid ...
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 graph theory, a maximal independent set (MIS) or maximal stable set is an Independent set (graph theory), independent set that is not a subset of any other independent set. In other words, there is no Vertex (graph theory), vertex outside th ...
in the
comparability graph In graph theory and order theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partial ...
of , or a
maximal clique In graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is complete. Cliques are one of t ...
in the complement of the comparability graph, so algorithms for the
clique problem In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which c ...
or the independent set problem can also be applied to this version of the Dedekind–MacNeille completion problem.For the equivalence between algorithms for antichains in partial orders and for independent sets in comparability graphs, see , p. 251.


Constructing the covering graph

The
transitive reduction In the mathematical field of graph theory, a transitive reduction of a directed graph is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices , a (directed) path from to in exists ...
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 set In set theory, the complement of a set , often denoted by A^c (or ), is the set of elements not in . When all elements in the universe, i.e. all elements under consideration, are considered to be members of a given set , the absolute complement ...
s 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 In computer science, a trie (, ), also known as a digital tree or prefix tree, is a specialized search tree data structure used to store and retrieve strings from a dictionary or set. Unlike a binary search tree, nodes in a trie do not store t ...
, 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.


Notes


References

*. *. *. * *. *. *. *. *. *. *. *. *. *. * * * *.


External links


MacNeille completion
in
PlanetMath PlanetMath is a free content, free, collaborative, mathematics online encyclopedia. Intended to be comprehensive, the project is currently hosted by the University of Waterloo. The site is owned by a US-based nonprofit corporation, "PlanetMath.org ...
* {{DEFAULTSORT:Dedekind-MacNeille completion Order theory Lattice theory