In the mathematical area of
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 int ...
, a completely distributive lattice is a
complete lattice in which arbitrary
join Join may refer to:
* Join (law), to include additional counts or additional defendants on an indictment
*In mathematics:
** Join (mathematics), a least upper bound of sets orders in lattice theory
** Join (topology), an operation combining two top ...
s
distribute over arbitrary
meet
Meet may refer to:
People with the name
* Janek Meet (born 1974), Estonian footballer
* Meet Mukhi (born 2005), Indian child actor
Arts, entertainment, and media
* ''Meet'' (TV series), an early Australian television series which aired on ABC du ...
s.
Formally, a complete lattice ''L'' is said to be completely distributive if, for any doubly indexed family
of ''L'', we have
:
where ''F'' is the set of
choice function
A choice function (selector, selection) is a mathematical function ''f'' that is defined on some collection ''X'' of nonempty sets and assigns some element of each set ''S'' in that collection to ''S'' by ''f''(''S''); ''f''(''S'') maps ''S'' to ...
s ''f'' choosing for each index ''j'' of ''J'' some index ''f''(''j'') in ''K''
''j''.
[B. A. Davey and H. A. Priestley, '' Introduction to Lattices and Order'' 2nd Edition, Cambridge University Press, 2002, , 10.23 Infinite distributive laws, pp. 239–240]
Complete distributivity is a self-dual property, i.e.
dualizing the above statement yields the same class of complete lattices.
Without the axiom of choice, no complete lattice with more than one element can ever satisfy the above property, as one can just let ''x''
''j'',''k'' equal the top element of ''L'' for all indices ''j'' and ''k'' with all of the sets ''K''
''j'' being nonempty but having no choice function.
Alternative characterizations
Various different characterizations exist. For example, the following is an equivalent law that avoids the use of choice functions. 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
In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
.
Properties
In addition, it is known that the following statements are equivalent for any complete lattice ''L'':
[G. N. Raney, ]
A subdirect-union representation for completely distributive complete lattices
', Proceedings of the American Mathematical Society, 4: 518 - 522, 1953.
* ''L'' is completely distributive.
* ''L'' can be embedded into a direct product of chains
,1by an
order embedding In order theory, a branch of mathematics, 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 str ...
that preserves arbitrary meets and joins.
* Both ''L'' and its dual order ''L''
op are
continuous posets.
Direct products of
,1 i.e. sets of all functions from some set ''X'' to
,1ordered
pointwise In mathematics, the qualifier pointwise is used to indicate that a certain property is defined by considering each value f(x) of some function f. An important class of pointwise concepts are the ''pointwise operations'', that is, operations defined ...
, are also called ''cubes''.
Free completely distributive lattices
Every
poset
In mathematics, especially order theory, a partially ordered set (also poset) 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 r ...
''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 In order theory, a branch of mathematics, 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 str ...
such that for every completely distributive lattice ''M'' and
monotonic function
In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order ...
, 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.
[Joseph M. Morris, ]
Augmenting Types with Unbounded Demonic and Angelic Nondeterminacy
', Mathematics of Program Construction, LNCS 3125, 274-288, 2004
This is an instance of the concept of
free object
In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. Informally, a free object over a set ''A'' can be thought of as being a "generic" algebraic structure over ''A'': the only equations that hold between eleme ...
. 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
* The
unit interval
In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1. It is often denoted ' (capital letter ). In addition to its role in real analysis ...
,1 ordered in the natural way, is a completely distributive lattice.
[G. N. Raney, ''Completely distributive complete lattices'', Proceedings of the ]American Mathematical Society
The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...
, 3: 677 - 680, 1952.
**More generally, any
complete chain is a completely distributive lattice.
[Alan Hopenwasser, ''Complete Distributivity'', Proceedings of Symposia in Pure Mathematics, 51(1), 285 - 305, 1990.]
* The
power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
lattice
for any set ''X'' is a completely distributive lattice.
* For every poset ''C'', there is a ''free completely distributive lattice over C''.
See the section on
Free completely distributive lattices above.
See also
*
Glossary of order theory
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 b ...
*
Distributive lattice
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 ...
References
Order theory