nLab distributive lattice

Contents

Contents

Definition

Definition

A distributive lattice is a lattice in which join \vee and meet \wedge distribute over each other, in that for all x,y,zx,y,z in the lattice, the distributivity laws are satisfied:

  • x(yz)=(xy)(xz)x \vee (y \wedge z) = (x \vee y) \wedge (x \vee z),
  • x(yz)=(xy)(xz)x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z).
Remark

The nullary forms of distributivity hold in any lattice:

  • x=x \vee \top = \top,
  • x=x \wedge \bot = \bot.

Distributive lattices and lattice homomorphisms form a concrete category DistLat.

Remark

Any lattice that satisfies one of the two binary distributivity laws must also satisfy the other; isn't that nice? (This may safely be left as an exercise.) This also means that a distributive lattice is precisely a lattice (or indeed a poset) which is a distributive category (when viewed as a thin category.)

This convenience does not extend to infinitary distributivity, however.

Remark

Each distributivity law holds in one direction in any lattice (the proofs of which may be left as an exercise):

  • x(yz)(xy)(xz)x \vee (y \wedge z) \leq (x \vee y) \wedge (x \vee z)
  • x(yz)(xy)(xz)x \wedge (y \vee z) \geq (x \wedge y) \vee (x \wedge z)

As a result, the real content of the definition consists of the converse directions (and as remarked above, either one suffices):

  • x(yz)(xy)(xz)x \vee (y \wedge z) \geq (x \vee y) \wedge (x \vee z)
  • x(yz)(xy)(xz)x \wedge (y \vee z) \leq (x \wedge y) \vee (x \wedge z)

Alternative characterizations

As mentioned above, the theory of distributive lattices is self-dual, something that is proved in almost any account (or left as an exercise), but which is not manifestly obvious from the standard definition which chooses one of the two distributivity laws and goes from there. In this section we provide some other characterizations or axiomatizations which are manifestly self-dual.

Here is one such characterization:

Proposition

A lattice is distributive if and only if the identity

(ab)(ac)(bc)=(ab)(ac)(bc)(a \wedge b) \vee (a \wedge c) \vee (b \wedge c) = (a \vee b) \wedge (a \vee c) \wedge (b \vee c)

is satisfied.

Again this may be left as a (somewhat mechanical) exercise.

Perhaps more useful in practice is the characterization in terms of “forbidden sublattices” due to Birkhoff. Namely, introduce the “pentagon” N 5N_5 as the 5-element lattice {a,b,c}\{\bot \leq a, b, c \leq \top\} where bcb \leq c and aa is incomparable to b,cb, c, so that =ac\bot = a \wedge c and ab=a \vee b = \top. Introduce the “thick diamond” M 3M_3 as the 5-element lattice {a,b,c}\{\bot \leq a', b', c' \leq \top\} with a,b,ca', b', c' pairwise incomparable. Both N 5N_5 and M 3M_3 are self-dual. Birkhoff’s characterization is the following (manifestly self-dual) criterion.

Theorem

A lattice LL is distributive if and only if there is no embedding of N 5N_5 or M 3M_3 into LL that preserves binary meets and binary joins.

This can be useful for determining distributivity or its failure, especially in cases where one can visualize a lattice via its Hasse diagram.

The necessity of the forbidden sublattice condition is clear in view of the fact that the cancellation law stated in the next result fails in N 5N_5 and M 3M_3. This result gives another self-dual axiomatization of distributive lattices.

Proposition

A lattice LL is distributive if and only if the cancellation law holds: for all y,zLy, z \in L, we have y=zy = z whenever xy=xzx \wedge y = x \wedge z and xy=xzx \vee y = x \vee z (for some xx).

Proof

“Only if”: if xy=xzx \wedge y = x \wedge z and xy=xzx \vee y = x \vee z, then

y=y(xy)=y(xz)=(yx)(yz)=(xz)(yz)=(xy)zy = y \vee (x \wedge y) = y \vee (x \wedge z) = (y \vee x) \wedge (y \vee z) = (x \vee z) \wedge (y \vee z) = (x \wedge y) \vee z

which implies zyz \leq y, and similarly we have yzy \leq z.

“If”: this is harder. Assuming the cancellation law for LL, we first show LL is modular. Recall from modular lattice that for any lattice LL and a,bLa, b \in L, there is a covariant Galois connection

([ab,b][a,ab]:xax)([a,ab][ab,b]:yby)([a \wedge b, b] \to [a, a \vee b]: x \mapsto a \vee x) \; \dashv \; ([a, a \vee b] \to [a \wedge b, b]: y \mapsto b \wedge y)

and that LL is modular if this Galois connection is a Galois correspondence (or adjoint equivalence) for all a,ba, b. Now, if x[ab,b]x \in [a \wedge b, b], then ax=a(b(ax))a \vee x = a \vee (b \wedge (a \vee x)) because f=fgff = f g f for any Galois connection fgf \dashv g. From abxba \wedge b \leq x \leq b we also have

ax=abx=ab=ab(ax)a \wedge x = a \wedge b \wedge x = a \wedge b = a \wedge b \wedge (a \vee x)

and so by cancellation of the aa's, we conclude x=b(ax)x = b \wedge (a \vee x). Similarly (dually), for y[a,ab]y \in [a, a \vee b], we have y=a(by)y = a \vee (b \wedge y). Hence LL is modular.

Now we show LL is distributive. Let x,y,zLx, y, z \in L and consider the three elements

u [x(yz)](yz) = [x(yz)](yz) v [y(xz)](xz) = [y(xz)](xz) w [z(xy)](xy) = [z(xy)](xy)\array{ u & \coloneqq & [x \wedge (y \vee z)] \vee (y \wedge z) & = & [x \vee (y \wedge z)] \wedge (y \vee z) \\ v & \coloneqq & [y \wedge (x \vee z)] \vee (x \wedge z) & = & [y \vee (x \wedge z)] \wedge (x \vee z) \\ w & \coloneqq & [z \wedge (x \vee y)] \vee (x \wedge y) & = & [z \vee (x \wedge y)] \wedge (x \vee y) }

where the non-definitional equalities follow from modularity. Using the first expressions, we compute

uv = [x(yz)](yz)[y(xz)](xz) = [x(yz)][y(xz)] = [(x(yz))y](xz) = (xy)(xz)(yz)\array{ u \vee v & = & [x \wedge (y \vee z)] \vee (y \wedge z) \vee [y \wedge (x \vee z)] \vee (x \wedge z) \\ & = & [x \wedge (y \vee z)] \vee [y \wedge (x \vee z)] \\ & = & [(x \wedge (y \vee z)) \vee y] \wedge (x \vee z) \\ & = & (x \vee y) \wedge (x \vee z) \wedge (y \vee z) }

where the third and fourth lines use modularity. By symmetry in the letters x,y,zx, y, z, we also have uw=vw=(xy)(xz)(yz)u \vee w = v \vee w = (x \vee y) \wedge (x \vee z) \wedge (y \vee z). Now the second expressions are dual to the first, so by duality we compute

uv=uw=vw=(xy)(xz)(yz).u \wedge v = u \wedge w = v \wedge w = (x \wedge y) \vee (x \wedge z) \vee (y \wedge z).

Now by cancellation of the uu's, we may conclude v=wv = w, but in that case we obtain

(xy)(xz)(yz)=vw=vw=(xy)(xz)(yz)(x \vee y) \wedge (x \vee z) \wedge (y \vee z) = v \vee w = v \wedge w = (x \wedge y) \vee (x \wedge z) \vee (y \wedge z)

so that LL is distributive by Proposition .

Remark

While the expressions for u,v,wu, v, w in the preceding proof may look as though they come out of thin air, the underlying idea is that the sublattice of LL generated by x,y,zx, y, z is the image of a lattice map F(3)LF(3) \to L out of the free modular lattice F(3)F(3) on three elements. The only obstruction to distributivity in F(3)F(3) is the presence of an M 3M_3-sublattice appearing in the center of its Hasse diagram. The middle elements of that sublattice correspond to the formal expressions for u,v,wu, v, w given above, and the proof shows that under the cancellation law, we have u=v=wu = v = w in LL, making the thick diamond collapse to a point in LL and removing the obstruction to distributivity.

From Proposition , it is not very hard to deduce Birkhoff’s theorem. The presence of a copy of M 3M_3 or N 5N_5 in a non-distributive lattice LL is deduced from a failure of the cancellation law where we have three elements x,y,zx, y, z with xy=xzx \wedge y = x \wedge z, xy=xzx \vee y = x \vee z, and yzy \neq z. If y,zy, z are comparable, say yzy \leq z, then the set {xy,x,y,z,xy}\{x \wedge y, x, y, z, x \vee y\} forms an N 5N_5. If y,zy, z are incomparable, then we have either yz<xyy \vee z \lt x \vee y, or yz>xyy \wedge z \gt x \wedge y, or both yz=xyy \vee z = x \vee y and yz=xyy \wedge z = x \wedge y; in the first two cases we get an N 5N_5 (e.g., {xy,x,y,yz,xy}\{x \wedge y, x, y, y \vee z, x \vee y\} for the first case), and in the third case the set {xy,x,y,z,xy}\{x \wedge y, x, y, z, x \vee y\} forms an M 3M_3.

Examples

Any Boolean algebra, and even any Heyting algebra, is a distributive lattice.

Every frame and every σ \sigma -frame is a distributive lattice.

Any linear order is a distributive lattice.

An integral domain is a Prüfer domain? iff its lattice of ideals is distributive. The classical example is \mathbb{Z}; equivalently, the (opposite of the) multiplicative monoid \mathbb{N} ordered by divisibility, with 11 at the bottom and 00 at the top.

The lattice of Young diagrams ordered by inclusion is distributive.

Infinitely distributive property

A distributive lattice that is complete (not necessarily completely distributive) may be infinitely distributive or said to satisfiy the infinite distributive law :

x( iy i)= i(xy i) x \wedge (\bigvee_i y_i) = \bigvee_i (x\wedge y_i)

This property is sufficient to give the lattice Heyting algebra stucture where the implication aba\Rightarrow b (or exponential object b ab^a) is:

(uv)= xuvx(u \Rightarrow v) = \bigvee_{x \wedge u \leq v} x

Note that this property does not imply the dual co-infinitely distributive property:

x( iy i)= i(xy i) x \vee (\bigwedge_i y_i) = \bigwedge_i (x\vee y_i)

Instead this dual gives the lattice co-Heyting structure where the co-implication or “subtraction” (\\backslash) is

(u\v)= uvxx(u \backslash v) = \bigwedge_{u \leq v \vee x} x

If a lattice has both properties, as in a completely distributive lattice, then it has bi-Heyting structure (both Heyting and co-Heyting) and the two exponentials are equal.

(uv)= xuvx=(u\v)= uvxx(u \Rightarrow v) = \bigvee_{x \wedge u \leq v} x \qquad = \qquad (u \backslash v) = \bigwedge_{u \leq v \vee x} x

Does it make sense to define “infinitely distributive property” for non-complete lattices? (Something like: “Whenever the join exists, it satisfies the infinite distributive law.”)

Properties

Finite distributive lattices

Since a finite distributive lattice is completely distributive it is a bi-Heyting lattice, as shown above.

Let FinDistLatFinDistLat be the category of finite distributive lattices and lattice homomorphisms, and let FinPosetFinPoset be the category of finite posets and order-preserving functions. These are contravariantly equivalent, thanks to the presence of an ambimorphic object:

Proposition. The opposite category of FinDistLatFinDistLat is equivalent to FinPosetFinPoset:

FinDistLat opFinPoset. FinDistLat^{op} \simeq FinPoset.

One direction of this equivalence is given by the hom-functor

[,2]:FinDistLat opFinPoset [-,2] \;\colon\; FinDistLat^{op} \stackrel{\simeq}{\to} FinPoset

where 22 is the 2-element distributive lattice and for any XFinDistLatX \in FinDistLat, [X,2][X,2] is the poset of distributive lattice morphisms from XX to 22. The other direction is given by

[,2]:FinPoset opFinDistLat [-,2] \;\colon\; FinPoset^{op} \stackrel{\simeq}{\to} FinDistLat

where 2={0,1}2 = \{0,1\} is the 2-element poset with 0<10 \lt 1 and for any YFinPosetY \in \FinPoset, [Y,2][Y,2] is the distributive lattice of poset morphisms from YY to 22.

This Birkhoff duality is (in one form or another) mentioned in many places; the formulation in terms of hom-functors may be found in

  • Gavin C. Wraith, Using the generic interval, Cah. Top. Géom. Diff. Cat. XXXIV 4 (1993) pp.259-266. (pdf)

The functorial nature of the correspondence means that morphisms of finite posets (i.e. order-preserving maps) naturally correspond to morphisms of finite distributive lattices (i.e. order-preserving maps that also respect meet and join).

It follows from Birkhoff’s representation theorem that every finite distributive lattice can be seen as a lattice of sets (i.e. sets with join and meet given by union and intersection) – in particular, sets whose elements are the join-irreducible elements of the lattice. Furthermore, a good intuition for why this duality holds is that either an element is generated as the join of existing elements, or it is join-irreducible. Hence given any existing poset, we can simply add all missing joins, and also a bottom (i.e. the nullary join). By general results (the adjoint functor theorem for posets) this suffices to ensure that all meets exist as well. This is analogous to the free colimit completion of a category, and indeed Birkhoff representation can be seen as a very special case of the Yoneda lemma as applied to (0,1)-category theory (i.e., order theory), since (0,1)-presheaves are functors into Bool rather than Set and hence correspond to lower sets.

Birkhoff duality does not hold for infinite distributive lattices. However, in the general case of not-necessarily-finite distributive lattices there is a correspondence not to posets, but instead to a class of spaces known as Priestley spaces. This is an instance of a general phenomena known as Stone-type duality.

The free distributive lattice

Posets also give rise to a “free” distributive lattice, which is not the same as their Birkhoff dual. Instead, it is formed by the following procedure: First, take the poset of upsets with the reverse ordering (this is the free finite meet completion). Then form the distributive lattice of finitely generated downsets in that.

In the case that one begins with a discrete poset (i.e., a set) then the number of elements in the resultant free distributive lattice is known as a Dedekind number, which also counts the number of monotone Boolean functions in nn variables. Dedekind numbers increase extremely rapidly, and there is no good known closed-form summation to compute them. The first ten (and only known) Dedekind numbers are (starting at n=0n = 0): 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, and 286386577668298411128469151667598498812366; see OEIS A000372.

Categorification

Every distributive lattice, regarded as a category (a (0,1)-category), is a coherent category. Conversely, the notion of coherent category may be understood as a categorification of the notion of distributive lattice. A different categorification is the notion of distributive category.

Completion

The completely distributive algebraic lattices (the frames of opens of Alexandroff locales ) form a reflective subcategory of that of all distributive lattices. The reflector is called canonical extension.

References

Last revised on February 12, 2024 at 17:03:07. See the history of this page for a list of all contributions to it.