Introduction to Lattice Theory with Computer Science Applications

Chapter 9Distributive Lattices

9.1 INTRODUCTION

Recall that a lattice is distributive if

9.1

Distributive lattices form one of the most interesting class of lattices. Many lattices that arise in distributed computing and combinatorics are distributive. The set of all consistent global states in a distributed computation forms a distributive lattice. The set of all subsets of any set forms a distributive lattice under the subset relation.

In this chapter, we discuss some of the crucial properties of distributive lattices. Section 9.2 gives a characterization of distributive lattices using forbidden sublattices. In Section 9.4, we discuss a duality between finite distributive lattices and finite posets. Every finite distributive lattice can be recovered from the poset of its join-irreducible elements. This result due to Birkhoff,is known as the fundamental theorem of finite distributive lattices.

9.2 FORBIDDEN SUBLATTICES

Given a modular lattice, the following theorem is useful in determining if the lattice is distributive.

Theorem 9.1

[Diamond] A modular lattice is distributive iff it does not contain a diamond, , as a sublattice.

Proof:

(): If the lattice contains a ...