# Why wouldn't the distributive laws hold for a lattice?

My understanding is that the distributive laws $$A\cap (B\cup C) = (A\cap B) \cup (A\cap C)$$ $$A\cup (B\cap C) = (A\cup B) \cap (A\cup C)$$ hold for any set.

A lattice is defined as a partially ordered set in which every two elements have a least upper bound and a greatest lower bound.

I'm reading that these distributive laws, although they make sense for a lattice, does not necessarily hold for a lattice. How can this be?

• Examples of non-distributive lattices include $M_3$ and the even worse (= not even modular) $N_5$. You should check for yourself that these are non-distributive. Incidentally, they're universal in a precise sense: a lattice $L$ $(i)$ is non-distributive iff $L$ contains a sublattice isomorphic to $M_3$ or $N_5$, and $(ii)$ is non-modular iff $L$ contains a sublattice isomorphic to $N_5$. Commented Jan 29, 2019 at 16:08

## 3 Answers

Your confusion stems from a misunderstanding of what the operations $$\cap, \cup$$ mean in a lattice. When you say that your two equations "hold for any set", what this more formally is that for any set $$X$$, if $$A, B, C$$ are subsets of $$X$$, then \begin{align*} A\cap (B\cup C) = (A\cap B) \cup (A\cap C),\\ A\cup (B\cap C) = (A\cup B) \cap (A\cup C). \end{align*} A lattice $$(Y, \land, \lor)$$ is a set together with two binary operations $$\land, \lor$$ which satisfy some rules. These rules include, for example, $$a \land (a \lor b) = a$$, and $$a \land b = b \land a$$. The lattice $$(Y, \land, \lor)$$ -- usually just referred to as $$Y$$, unless confusion can occur -- may or may not satisfy the additional rules \begin{align*} a\land (b\lor c) = (a\land b) \lor (a\land c),\\ a\lor (b\land c) = (a\lor b) \land (a\lor c). \end{align*} If it satisfies these additional rules, we call $$Y$$ a distributive lattice.

Rephrasing the first statement in terms of the language of lattices: if $$X$$ is a set, then $$(\mathcal P(X), \cap, \cup)$$ forms a lattice, and this lattice is distributive.

Now you hopefully see that you have mixed up the following two statements. For a lattice $$(Y, \land, \lor)$$, it may be distributive or not. However, the lattice $$(\mathcal P(Y), \cap, \cup)$$ is certainly distributive. But this is a statement about a different lattice.

Define $$(X, \le_X)$$ by $$X = \{ (0,0), (1,0), (1,1), (1,2), (2,0) \}$$ and $$(a,b) \le_X (c,d)$$ if and only if either $$a \le c$$ and $$b=d$$, or $$a.

This lattice has joins and meets, but meets do not distribute over joins since for example $$(1,0) \wedge ((1,1) \vee (1,2)) = (1,0) \wedge (2,0) = (1,0)$$ but $$((1,0) \wedge (1,1)) \vee ((1,0) \wedge (1,2)) = (0,0) \vee (0,0) = (0,0)$$

A dual example demonstrates that joins don't distribute over meets in this lattice.

A lattice in which meets distribute over joins and vice versa is called a distributive lattice. [In fact, it suffices that meets distribute over joins—the fact that joins distribute over meets follows from this.]

Fun fact: a lattice is distributive if and only if it doesn't contain one of two non-distributive lattices as a sub-lattice. One of these lattices is the one I mentioned above.

• In your first displayed formula, the final result should be $(1,0)$, right? Commented Jan 29, 2019 at 15:10
• @amrsa: Yes, thanks. Commented Jan 29, 2019 at 15:56

Although you have already two excellent answers, I think it is instructive to have yet another approach.

It is true that intersection and union distribute over each other for any set.
However, sometimes we're considering not the whole powerset of some set, but just some other family of subsets.

In this example, I'm considering the same lattice as in Clive's answer, but as a lattice of subsets of a set.
Let $$X=\{a,b,c\}$$, and $$L = \{\varnothing, \{a\}, \{b\}, \{c\}, X\}$$.
Then $$L$$ is a family of subsets of $$X$$, and under set inclusion, it forms a lattice which is not distributive.
Again, using the same members of the lattice that Clive did, but under this new guise, we have $$\{a\} \wedge (\{b\} \vee \{c\}) = \{a\} \wedge X = \{a\},$$ while $$(\{a\}\wedge\{b\})\vee(\{a\}\wedge\{c\}) = \varnothing \vee \varnothing = \varnothing.$$ Here, the meet of two elements is always the intersection, since the family $$L$$ of subsets of $$X$$ is closed for intersections, but the join is not the union, since, for example, $$\{b\}\vee\{c\}=X$$ because $$\{b,c\}\notin L$$; so the least subset of $$X$$ that belongs to $$L$$ and contains both $$b$$ and $$c$$, is $$X$$. So $$L$$ is not closed under unions, and in fact, it is not distributive.
(Note, however, that not being closed under intersection or union doesn't imply that it is not distributive.)