Section 12.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 12.2.1. Join, Meet.
Let \((L, \preceq)\) be a poset, and \(a, b \in L\text{.}\) We define:
\(a \lor b\text{,}\) read “\(a\) join \(b\)”, as the least upper bound of \(a\) and \(b\text{,}\) if it exists. and
\(a \land b\text{,}\) read “\(a\) meet \(b\)”, as the greatest lower bound of \(a\) and \(b\text{,}\) if it exists.
Since the join and meet produce a unique result in all cases where they exist, by Theorem 12.1.6, we can consider them as binary operations on a set if they always exist. Thus the following definition:
Definition 12.2.2. Lattice.
A lattice is a poset \((L, \preceq)\) 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\text{,}\) it is denoted by \([L; \lor, \land]\text{.}\) If we want to make it clear what partial ordering the lattice is based on, we say it is a lattice under \(\preceq\text{.}\)
Example 12.2.3. The power set of a three element set.
Consider the poset \((\mathcal{P}(A),\subseteq)\) we examined in Example 12.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\text{.}\) The reader is encouraged to write out the operation tables \([\mathcal{P}(A); \cup, \cap]\text{.}\)
Our first concrete lattice can be generalized to the case of any set \(A\text{,}\) producing the lattice \([\mathcal{P}(A); \lor, \land]\text{,}\) 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\text{.}\)
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 \([\mathcal{P}(A); \cup, \cap ]\text{,}\) 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.4. Distributive Lattice.
Let \(\mathcal{L}=[L; \lor, \land ]\) be a lattice under \(\preceq\) . \(\mathcal{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
Example 12.2.5. A Nondistributive Lattice.
We now give an example of a lattice where the distributive laws do not hold. Let \(L = \{\pmb{0},a,b,c,\pmb{1}\}\text{.}\) We define the partial ordering \(\preceq\) on \(L\) by the set
The operation tables for \(\lor\) and \(\land\) on \(L\) are:
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 \pmb{0} = a\) and \((a \lor c) \land (a \lor b) = \pmb{1} \land \pmb{1} = \pmb{1}\text{.}\) Therefore, \(a \lor (b \land c) \neq (a \lor b) \land (a \lor c)\) for some values of \(a, b, c \in L\text{.}\) 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.6. The Hasse diagram on the right of this figure, produces the diamond lattice, which is precisely the one that is defined in Example 12.2.5. The lattice based on the left hand poset is called the pentagon lattice.
Exercises Exercises
¶1.
Let \(L\) be the set of all propositions generated by \(p\) and \(q\text{.}\) What are the meet and join operations in this lattice under implication? What are the maximum and minimum elements?
2.
Which of the posets in Exercise 12.1.3 are lattices? Which of the lattices are distributive?
3.
State the commutative laws, associative laws, idempotent laws, and absorption laws for lattices.
Prove laws you stated.
4.
Demonstrate that the pentagon lattice is nondistributive.
5.
What is a reasonable definition of the term sublattice?
One reasonable definition would by this: Let \([L; \lor, \land ]\) be a lattice and let \(K\) be a nonempty subset of \(L\text{.}\) Then \(K\) is a sublattice of \(L\) if and only if \(K\) is closed under both \(\lor\) and \(\land\)
6.
Let \([L; \lor , \land ]\) be a lattice based on a partial ordering \(\preceq\text{.}\) Prove that if \(a, b, c \in L\text{,}\)
\(a \preceq a \lor b \text{.}\)
\(a \land b \preceq a\text{.}\)
\(b \preceq a\) and \(c \preceq a \Rightarrow b \lor c \preceq a\text{.}\)