ads Lattices

Section 13.2 Lattices

In this section, we restrict our discussion to lattices, those posets for which every pair of elements has both a greatest lower bound and least upper bound. We first introduce some notation.

🔗

Definition 13.2.1. Join, Meet.

Let

(L, ⪯)

be a poset, and

a, b \in L .

We define:

$a \lor b,$ read “ $a$ join $b$ ”, as the least upper bound of $a$ and $b,$ if it exists. and
🔗

🔗
$a \land b,$ read “ $a$ meet $b$ ”, as the greatest lower bound of $a$ and $b,$ if it exists.
🔗

🔗

🔗

Since the join and meet produce a unique result in all cases where they exist, by Theorem 13.1.6, we can consider them as binary operations on a set if they always exist. Thus the following definition:

🔗

Definition 13.2.2. Lattice.

A lattice is a poset

(L, ⪯)

for which every pair of elements has a greatest lower bound and least upper bound. Since a lattice

L

is an algebraic system with binary operations

\lor

and

\land,

it is denoted by

[L; \lor, \land] .

If we want to make it clear what partial ordering the lattice is based on, we say it is a lattice under

⪯ .

🔗

Example 13.2.3. The power set of a three element set.

Consider the poset

(P (A), \subseteq)

we examined in Example 13.1.10. It isn’t too surprising that every pair of sets had a greatest lower bound and least upper bound. Thus, we have a lattice in this case; and

A \lor B = A \cup B

and

A \land B = A \cap B .

The reader is encouraged to write out the operation tables

[P (A); \cup, \cap] .

🔗

Our first concrete lattice can be generalized to the case of any set

A,

producing the lattice

[P (A); \lor, \land],

where the join operation is the set operation of union and the meet operation is the operation intersection; that is,

\lor = \cup

and

\land = \cap .

🔗

It can be shown (see the exercises) that the commutative laws, associative laws, idempotent laws, and absorption laws are all true for any lattice. A concrete example of this is clearly

[P (A); \cup, \cap],

since these laws hold in the algebra of sets. This lattice also has distributive property in that join is distributive over meet and meet is distributive over join. However, this is not always the case for lattices in general.

🔗

Definition 13.2.4. Distributive Lattice.

Let

L = [L; \lor, \land]

be a lattice under

⪯

L

is called a distributive lattice if and only if the distributive laws hold; that is, for all

a, b, c \in L

we have

\begin{matrix} a \lor (b \land c) = (a \lor b) \land (a \lor c) \\ a n d \\ a \land (b \lor c) = (a \land b) \lor (a \land c) \end{matrix}

🔗

Example 13.2.5. A Nondistributive Lattice.

We now give an example of a lattice where the distributive laws do not hold. Let

L = {0 0, a, b, c, 1 1} .

We define the partial ordering

⪯

L

by the set

{(0 0, 0 0), (0 0, a), (0 0, b), (0 0, c), (0 0, 1 1), (a, a), (a, 1 1), (b, b), (b, 1 1), (c, c), (c, 1 1), (1 1, 1 1)}

The operation tables for

\lor

and

\land

L

are:

\begin{array}{cc} \begin{array}{cccccc} \lor & 0 0 & a & b & c & 1 1 \\ 0 0 & 0 0 & a & b & c & 1 1 \\ a & a & a & 1 1 & 1 1 & 1 1 \\ b & b & 1 1 & b & 1 1 & 1 1 \\ c & c & 1 1 & 1 1 & c & 1 1 \\ 1 1 & 1 1 & 1 1 & 1 1 & 1 1 & 1 1 \end{array} & \begin{array}{cccccc} \land & 0 0 & a & b & c & 1 1 \\ 0 0 & 0 0 & 0 0 & 0 0 & 0 0 & 0 0 \\ a & 0 0 & a & 0 0 & 0 0 & a \\ b & 0 0 & 0 0 & b & 0 0 & b \\ c & 0 0 & 0 0 & 0 0 & c & c \\ 1 1 & 0 0 & a & b & c & 1 1 \end{array} \end{array}

🔗

Since every pair of elements in

L

has both a join and a meet,

[L; \lor, \land]

is a lattice (under divides). Is this lattice distributive? We note that:

a \lor (c \land b) = a \lor 0 0 = a

and

(a \lor c) \land (a \lor b) = 1 1 \land 1 1 = 1 1 .

Therefore,

a \lor (b \land c) \neq (a \lor b) \land (a \lor c)

for some values of

a, b, c \in L .

Thus, this lattice is not distributive.

🔗

Our next observation uses the term “sublattice”, which we have not defined at this point, but we would hope that you could anticipate a definition, and we will leave it as an exercise to do so.

🔗

It can be shown that a lattice is nondistributive if and only if it contains a sublattice isomorphic to one of the lattices in Figure 13.2.6. The ordering diagram on the right of this figure, produces the diamond lattice, which is precisely the one that is defined in Example 13.2.5. The lattice based on the left hand poset is called the pentagon lattice.

🔗