Completely distributive lattice

From Wikipedia, the free encyclopedia

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

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

$\begin{align}\bigwedge_{j\in J}\bigvee_{k\in K_j} x_{j,k} = \bigvee_{f\in F}\bigwedge_{j\in J} x_{j,f(j)}\end{align}$

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

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

1 Alternative characterizations
2 Properties
3 Free completely distributive lattices
4 Examples
5 See also
6 References

[edit] 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

$\begin{align}\bigwedge \{ \bigvee Y \mid Y\in S\} = \bigvee\{ \bigwedge Z \mid Z\in S^\# \}\end{align}$

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

[edit] Properties

In addition, it is known that the following statements are equivalent for any complete lattice L^{[citation needed]}:

L is completely distributive.
L can be embedded into a direct product of chains [0,1] by an order embedding that preserves arbitrary meets and joins.
Both L and its dual order L^op are continuous posets.

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

[edit] 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 $\phi:C\rightarrow L$ such that for every completely distributive lattice M and monotonic function $f:C\rightarrow M$ , there is a unique complete homomorphism $f^*_\phi:L\rightarrow M$ satisfying $f=f^*_\phi\circ\phi$ . For every poset C, the free completely distributive lattice over a poset C exists and is unique up to isomorphism.^[2]

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.

[edit] Examples

The unit interval [0,1], ordered in the natural way, is a completely distributive lattice.^[3]
- More generally, any complete chain is a completely distributive lattice.^[4]
The power set lattice $(\mathcal{P}(X),\subseteq)$ for any set X is a completely distributive lattice.^[1]
For every poset C, there is a free completely distributive lattice over C.^[2] See the section on Free completely distributive lattices above.

[edit] See also

Glossary of order theory

[edit] References

^ ^a ^b ^c B. A. Davey and H. A. Priestey, Introduction to Lattices and Order 2nd Edition, Cambridge University Press, 2002, ISBN 0-521-78451-4
^ ^a ^b Joseph M. Morris, Augmenting Types with Unbounded Demonic and Angelic Nondeterminacy, Mathematics of Program Construction, LNCS 3125, 274-288, 2004
^ G. N. Raney, Completely distributive complete lattices, Proceedings of the American Mathematical Society, 3: 677 - 680, 1952.
^ Alan Hopenwasser, Complete Distributivity, Proceedings of Symposia in Pure Mathematics, 51(1), 285 - 305, 1990.