## You are here

Homecomplete distributivity

## Primary tabs

# complete distributivity

A lattice $L$ is said to be *completely distributive* if it is a complete lattice such that, given any sets $K\subseteq I\times J$ such that $K$ projects onto $I$, and any subset $\{x_{{ij}}\mid(i,j)\in K\}$ of $L$,

$\bigwedge_{{i\in I}}(\bigvee_{{j\in K(i)}}x_{{ij}})=\bigvee_{{f\in A}}(% \bigwedge_{{i\in I}}x_{{if(i)}}),$ | (1) |

where $K(i):=\{j\in J\mid(i,j)\in K\}$, and $A=\{f:I\to J\mid f(i)\in K(i)\mbox{ for all }i\in I\}$.

By setting $I=J=\{1,2\}$ and $K=\{(1,1),(2,1),(2,2)\}$, then $K(1)=\{1\}$, $K(2)=\{1,2\}$, and $A$ consists of two functions $\{(1,1),(2,1)\}$ and $\{(1,1),(2,2)\}$. Then, the equation above reads:

$(x_{{11}})\wedge(x_{{21}}\vee x_{{22}})=(x_{{11}}\wedge x_{{21}})\vee(x_{{11}}% \wedge x_{{22}})$ |

which is one of the distributive laws, so that complete distributivity implies distributivity.

More generally, setting $I=\{1,2\}$ and $J$ containing $1$ but otherwise arbitrary, and $K=\{(2,j)\mid j\in J\}\cup\{(1,1)\}$. Then $K(1)=\{1\}$, $K(2)=J$, and $A$ is the set of functions from $I$ to $J$ fixing $1$, and the equation (1) above now looks like

$x_{{11}}\wedge(\bigvee\{x_{{2j}}\mid j\in J\}=\bigvee\{x_{{11}}\wedge x_{{2j}}% \mid j\in J\}$ |

which shows that completely distributivity implies *join infinite distributivity*.

Remarks.

1. Dualizing the above equation results in the same lattice. In other words, a completely distributive lattice may be equivalently defined using the dual of Equation (1). As a result, a completely distributive lattice also satisfies MID, and hence is infinite distributive.

2. However, a complete distributive lattice does not have to be completely distributive. Here’s an example: let $\mathbb{N}$ be the set of natural numbers with the usual ordering, and $\mathbb{N}^{{\prime}}$ be an identical copy of $\mathbb{N}$ such that each natural number $n$ corresponds to $n^{{\prime}}\in\mathbb{N}^{{\prime}}$. Then $\mathbb{N}^{{\prime}}$ has a natural ordering induced by the usual ordering on $\mathbb{N}$. Take the union $N$ of these two sets. Then $N$ becomes a lattice if we extend the meets and joins on $\mathbb{N}$ and $\mathbb{N}^{{\prime}}$ by additionally setting

$a^{{\prime}}\vee b:=\left\{\begin{array}[]{ll}a^{{\prime}}&\textrm{if }b\leq a% ,\\ b^{{\prime}}&\textrm{otherwise.}\end{array}\right.$ and

$a^{{\prime}}\wedge b:=\left\{\begin{array}[]{ll}b&\textrm{if }b\leq a,\\ a&\textrm{otherwise.}\end{array}\right.$ Finally, let $L$ be the lattice formed from $N$ by adjoining an extra element $\infty$ to be its top element. It is not hard to see that $L$ is complete and distributive. However, $L$ is not completely distributive, for $0^{{\prime}}\wedge(\bigvee\{a\mid a\in\mathbb{N}\})=0^{{\prime}}\wedge\infty=0% ^{{\prime}}$, whereas $\bigvee\{0^{{\prime}}\wedge a\mid a\in\mathbb{N}\}=\bigvee\{0\}=0\neq 0^{{% \prime}}$.

3. In some literature, completeness assumption is not required, so that the equation (1) above is conditionally defined. In other words, the equation is defined only when each side of the equation exists first.

4. Another generalization is the so-called $(\mathfrak{m},\mathfrak{n})$-distributivity, where $\mathfrak{m}$ and $\mathfrak{n}$ are cardinal numbers. Specifically, a lattice $L$ is $(\mathfrak{m},\mathfrak{n})$-distributive if it is complete and equation (1) is true whenever $I$ has cardinality $\leq\mathfrak{m}$ and each $K(i)$ has cardinality $\leq\mathfrak{n}$ for each $i\in I$.

# References

- 1 G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. W. Mislove, D. S. Scott, Continuous Lattices and Domains, Cambridge University Press, Cambridge (2003).

## Mathematics Subject Classification

06D10*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections