Archive for the ‘Logic’ Category

A note on distributive and modular lattices

No Comments »

I’ve been working a little with an old friend, modal logic, this weekend. This digressed into a study of lattices and Boolean algebras, so I thought I would write up some of my observations for archival. Also, I just like to say “lattice”.

Smock

If you know anything about lattices, you will probably find this stuff trivial. If you don’t know anything about lattices, a free and much better introduction can be found in A Course in Universal Algebra.

Definition: A distributive lattice is a lattice which satisfies the distributive laws:

D1: x \land (y \lor z) \simeq (x \land y) \lor (x \land z)
D2: x \lor (y \land z) \simeq (x \lor y) \land (x \lor z)

Actually, it can be shown that a lattice satisfies D1 iff it satisfies D2.

Definition: A lattice L is said to be modular if the modular law holds:

M : x \leq y \Rightarrow x \lor (y \land z) \simeq y \land (x \lor z)

Lemma: The modular law for lattices is equivalent to the identity

 (x \land y) \lor (y \land z) \simeq y \land ((x \land y) \lor z)

Proof
Assume that the modular law holds and consider the expression y \land ((x \land y) \lor z). Since x \land y \leq y we can apply the modular law to infer that y \land ((x \land y) \lor z) \simeq (x \land y) \lor (y \land z).

Now, assume that the identity holds and that x \leq y for some x, y, z \in L. Then x = x \land y so

x \lor (y \land z) \simeq
(x \land y) \lor (y \land z) \stackrel{\dagger}{\simeq}
y \land ((x \land y) \lor z) \simeq
y \land (x \lor z),

where the identity was used in \dagger. Thus, the modular law holds.\Box

Theorem: Every distributive lattice is modular.

Proof
Assume that x \leq y for some x, y, z \in L where L is a distributive lattice. Then y = x \lor y so
 x \lor (y \land z) \simeq (x \lor y) \land (x \lor z) \simeq y \land (x \lor z)

where we have made use of D2. The desired result now follows from the lemma.