Completely distributive lattice

Last updated

In the mathematical area of order theory, a completely distributive lattice is a complete lattice in which arbitrary joins distribute over arbitrary meets.

Contents

Formally, a complete lattice L is said to be completely distributive if, for any doubly indexed family {xj,k | j in J, k in Kj} of L, we have

where F is the set of choice functions f choosing for each index j of J some index f(j) in Kj. [1]

Complete distributivity is a self-dual property, i.e. dualizing the above statement yields the same class of complete lattices. [1]

Alternative characterizations

Various different characterizations exist. For example, the following is an equivalent law that avoids the use of choice functions[ citation needed ]. For any set S of sets, we define the set S# to be the set of all subsets X of the complete lattice that have non-empty intersection with all members of S. We then can define complete distributivity via the statement

The operator ( )# might be called the crosscut operator. This version of complete distributivity only implies the original notion when admitting the Axiom of Choice.


Properties

In addition, it is known that the following statements are equivalent for any complete lattice L: [2]

Direct products of [0,1], i.e. sets of all functions from some set X to [0,1] ordered pointwise, are also called cubes.

Free completely distributive lattices

Every poset C can be completed in a completely distributive lattice.

A completely distributive lattice L is called the free completely distributive lattice over a poset C if and only if there is an order embedding such that for every completely distributive lattice M and monotonic function , there is a unique complete homomorphism satisfying . For every poset C, the free completely distributive lattice over a poset C exists and is unique up to isomorphism. [3]

This is an instance of the concept of free object. Since a set X can be considered as a poset with the discrete order, the above result guarantees the existence of the free completely distributive lattice over the set X.

Examples

See also

Related Research Articles

In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet). A lattice that satisfies at least one of these properties for bounded subsets is known as a conditionally complete lattice. For comparison, in a general lattice, only pairs of elements need to have a supremum and an infimum. Every non-empty finite lattice is complete, but infinite lattices may be incomplete.

In mathematics, specifically abstract algebra, the isomorphism theorems are theorems that describe the relationship between quotients, homomorphisms, and subobjects. Versions of the theorems exist for groups, rings, vector spaces, modules, Lie algebras, and various other algebraic structures. In universal algebra, the isomorphism theorems can be generalized to the context of algebras and congruences.

In mathematics, an algebraic structure consists of a nonempty set A, a collection of operations on A, and a finite set of identities, known as axioms, that these operations must satisfy.

In the mathematical areas of order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following:

In mathematics, a direct limit is a way to construct a object from many objects that are put together in a specific way. These objects may be groups, rings, vector spaces or in general objects from any category. The way they are put together is specified by a system of homomorphisms between those smaller objects. The direct limit of the objects , where ranges over some directed set , is denoted by . This notation suppresses the system of homomorphisms; however, the limit depends on the system of homomorphisms.

In mathematics, a distributive lattice is a lattice in 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. Indeed, these lattices of sets describe the scenery completely: every distributive lattice is—up to isomorphism—given as such a lattice of sets.

<span class="mw-page-title-main">Mathematical morphology</span>

Mathematical morphology (MM) is a theory and technique for the analysis and processing of geometrical structures, based on set theory, lattice theory, topology, and random functions. MM is most commonly applied to digital images, but it can be employed as well on graphs, surface meshes, solids, and many other spatial structures.

In mathematical analysis, a function of bounded variation, also known as BV function, is a real-valued function whose total variation is bounded (finite): the graph of a function having this property is well behaved in a precise sense. For a continuous function of a single variable, being of bounded variation means that the distance along the direction of the y-axis, neglecting the contribution of motion along x-axis, traveled by a point moving along the graph has a finite value. For a continuous function of several variables, the meaning of the definition is the same, except for the fact that the continuous path to be considered cannot be the whole graph of the given function, but can be every intersection of the graph itself with a hyperplane parallel to a fixed x-axis and to the y-axis.

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 introduces the field and provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary.

In mathematics, there is an ample supply of categorical dualities between certain categories of topological spaces and categories of partially ordered sets. Today, these dualities are usually collected under the label Stone duality, since they form a natural generalization of Stone's representation theorem for Boolean algebras. These concepts are named in honor of Marshall Stone. Stone-type dualities also provide the foundation for pointless topology and are exploited in theoretical computer science for the study of formal semantics.

This is a glossary of some terms used in various branches of mathematics that are related to the fields of order, lattice, and domain theory. Note that there is a structured list of order topics available as well. Other helpful resources might be the following overview articles:

A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum and a unique infimum. An example is given by the power set of a set, partially ordered by inclusion, for which the supremum is the union and the infimum is the intersection. Another example is given by the natural numbers, partially ordered by divisibility, for which the supremum is the least common multiple and the infimum is the greatest common divisor.

In mathematics, a closure operator on a set S is a function from the power set of S to itself that satisfies the following conditions for all sets

In the mathematical area of order theory, one often speaks about functions that preserve certain limits, i.e. certain suprema or infima. Roughly speaking, these functions map the supremum/infimum of a set to the supremum/infimum of the image of the set. Depending on the type of sets for which a function satisfies this property, it may preserve finite, directed, non-empty, or just arbitrary suprema or infima. Each of these requirements appears naturally and frequently in many areas of order theory and there are various important relationships among these concepts and other notions such as monotonicity. If the implication of limit preservation is inverted, such that the existence of limits in the range of a function implies the existence of limits in the domain, then one obtains functions that are limit-reflecting.

In mathematical order theory, an ideal is a special subset of a partially ordered set (poset). 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. Ideals are of great importance for many constructions in order and lattice theory.

In the mathematical area of order theory, there are various notions of the common concept of distributivity, applied to the formation of suprema and infima. Most of these apply to partially ordered sets that are at least lattices, but the concept can in fact reasonably be generalized to semilattices as well.

In mathematics, especially in order theory, a complete Heyting algebra is a Heyting algebra that is complete as a lattice. Complete Heyting algebras are the objects of three different categories; the category CHey, the category Loc of locales, and its opposite, the category Frm of frames. Although these three categories contain the same objects, they differ in their morphisms, and thus get distinct names. Only the morphisms of CHey are homomorphisms of complete Heyting algebras.

In mathematics, a join-semilattice is a partially ordered set that has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset. Every join-semilattice is a meet-semilattice in the inverse order and vice versa.

The order polynomial is a polynomial studied in mathematics, in particular in algebraic graph theory and algebraic combinatorics. The order polynomial counts the number of order-preserving maps from a poset to a chain of length . These order-preserving maps were first introduced by Richard P. Stanley while studying ordered structures and partitions as a Ph.D. student at Harvard University in 1971 under the guidance of Gian-Carlo Rota.

References

  1. 1 2 3 B. A. Davey and H. A. Priestley, Introduction to Lattices and Order 2nd Edition, Cambridge University Press, 2002, ISBN   0-521-78451-4, 10.23 Infinite distributive laws, pp. 239–240
  2. G. N. Raney, A subdirect-union representation for completely distributive complete lattices , Proceedings of the American Mathematical Society, 4: 518 - 522, 1953.
  3. 1 2 Joseph M. Morris, Augmenting Types with Unbounded Demonic and Angelic Nondeterminacy , Mathematics of Program Construction, LNCS 3125, 274-288, 2004
  4. G. N. Raney, Completely distributive complete lattices, Proceedings of the American Mathematical Society, 3: 677 - 680, 1952.
  5. Alan Hopenwasser, Complete Distributivity, Proceedings of Symposia in Pure Mathematics, 51(1), 285 - 305, 1990.