12.2: Lattices
- Last updated
- Sep 29, 2021
- Save as PDF
- Page ID
- 86178
( \newcommand{\kernel}{\mathrm{null}\,}\)
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.
Let (L,⪯) be a poset, and a,b∈L. We define:
- a∨b, read “a join b”, as the least upper bound of a and b, if it exists. and
- a∧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.1, we can consider them as binary operations on a set if they always exist. Thus the following definition:
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 ∨ and ∧, it is denoted by [L;∨,∧]. If we want to make it clear what partial ordering the lattice is based on, we say it is a lattice under ⪯.
Example 12.2.1: The Power Set of a Three Element Set
Consider the poset (P(A),⊆) we examined in Example 13.1.3. 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∨B=A∪B and A∧B=A∩B. The reader is encouraged to write out the operation tables [P(A);∪,∩].
Our first concrete lattice can be generalized to the case of any set A, producing the lattice [P(A);∨,∧], where the join operation is the set operation of union and the meet operation is the operation intersection; that is, ∨=∪ and ∧=∩.
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);∪,∩], 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 12.2.3: Distributive Lattice
Let L=[L;∨,∧] 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∈L we have
a∨(b∧c)=(a∨b)∧(a∨c)anda∧(b∨c)=(a∧b)∨(a∧c)
Example 12.2.2: A Nondistributive Lattice
We now give an example of a lattice where the distributive laws do not hold. Let L={00,a,b,c,11}. We define the partial ordering ⪯ on L by the set
{(00,00),(00,a),(00,b),(00,c),(00,11),(a,a),(a,11),(b,b),(b,11),(c,c),(c,11),(11,11)}
The operation tables for ∨ and ∧ on L are:
∨00abc110000abc11aaa111111bb11b1111cc1111c11111111111111∧00abc11000000000000a00a0000ab0000b00bc000000cc1100abc11
Since every pair of elements in L has both a join and a meet, [L;∨,∧] is a lattice (under divides). Is this lattice distributive? We note that: a∨(c∧b)=a∨00=a and (a∨c)∧(a∨b)=11∧11=11. Therefore, a∨(b∧c)≠(a∨b)∧(a∨c) for some values of a,b,c∈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 exercises 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 12.2.1. The ordering diagram on the right of this figure, produces the diamond lattice, which is precisely the one that is defined in Example 12.2.2. The lattice based on the left hand poset is called the pentagon lattice.

13.2.1: Exercises
Exercise 12.2.1
Let L be the set of all propositions generated by p and q. What are the meet and join operations in this lattice under implication? What are the maximum and minimum elements?
Exercise 12.2.2
Which of the posets in Exercise 13.1.3 are lattices? Which of the lattices are distributive?
Exercise 12.2.3
- State the commutative laws, associative laws, idempotent laws, and absorption laws for lattices.
- Prove laws you stated.
Exercise 12.2.4
Demonstrate that the pentagon lattice is nondistributive.
Exercise 12.2.5
What is a reasonable definition of the term sublattice?
- Answer
-
One reasonable definition would be this: Let [L;∨,∧] be a lattice and let K be a nonempty subset of L. Then K is a sublattice of L if and only if K is closed under both ∨ and ∧
Exercise 12.2.6
Let [L;∨,∧] be a lattice based on a partial ordering ⪯. Prove that if a,b,c∈L,
- a⪯a∨b.
- a∧b⪯a.
- b⪯a and c⪯a⇒b∨c⪯a.