Completely distributive lattice

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 {xj,k | j in J, k in Kj} of L, we have

⋀ j ∈ J ⋁ k ∈ K j x j , k = ⋁ f ∈ F ⋀ j ∈ J x j , f ( j ) {\displaystyle \bigwedge _{j\in J}\bigvee _{k\in K_{j}}x_{j,k}=\bigvee _{f\in F}\bigwedge _{j\in J}x_{j,f(j)}}

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

[edit]

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

⋀ { ⋁ Y ∣ Y ∈ S } = ⋁ { ⋀ Z ∣ Z ∈ S # } {\displaystyle {\begin{aligned}\bigwedge \\{\bigvee Y\mid Y\in S\\}=\bigvee \\{\bigwedge Z\mid Z\in S^{\\#}\\}\end{aligned}}}

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

[edit]

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

* 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 Lop are continuous posets.[citation needed]

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

[edit]

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 ϕ : C -> L {\displaystyle \phi :C\rightarrow L} such that for every completely distributive lattice M and monotonic function f : C -> M {\displaystyle f:C\rightarrow M} , there is a unique complete homomorphism f ϕ ∗ : L -> M {\displaystyle f_{\phi }^{*}:L\rightarrow M} satisfying  f = f ϕ ∗ ∘ ϕ {\displaystyle 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.[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

[edit]

* The unit interval [0,1], ordered in the natural way, is a completely distributive lattice.[4]
* More generally, any complete chain is a completely distributive lattice.[5]
* The power set lattice  ( P ( X ) , ⊆ ) {\displaystyle ({\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.[3] See the section on Free completely distributive lattices above.

## See also

[edit]

* Glossary of order theory
* Distributive lattice

## References

[edit]

1. ^ a b c 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. ^ a b 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.