Calculus

Set Theory

Set Theory Logo

Lattices

Lattices as Posets

A partially ordered set \(\require{AMSsymbols}{\left( {L,\preccurlyeq} \right)}\) is called a lattice if every pair of elements \(a\) and \(b\) in \(L\) has both a least upper bound \(\left( {LUB} \right)\) and a greatest lower bound \(\left( {GLB} \right).\)

The least upper bound is also called the join of \(a\) and \(b,\) denoted by \(a \lor b.\) The greatest lower bound is also called the meet of \(a\) and \(b,\) and is denoted by \(a \land b.\)

Lattice with a join and a meet.
Figure 1.

If \({\left( {L,\preccurlyeq} \right)}\) is a lattice and \(a,b,c,d \in L,\) then the meet and join have the following order properties:

  1. \(a \land b \preccurlyeq \left\{ {a,b} \right\} \preccurlyeq a \lor b\)
  2. \(a \preccurlyeq b \text{ if and only if } a \land b = a\)
  3. \(a \preccurlyeq b \text{ if and only if } a \lor b = b\)
  4. \(\text{If } a \preccurlyeq b, \text{ then } a \land c \preccurlyeq b \land c\,\) \(\text{and } a \lor c \preccurlyeq b \lor c\)
  5. \(\text{If } a \preccurlyeq b \text{ and } c \preccurlyeq d, \text{ then } a \land c \preccurlyeq b \land d\,\) \(\text{and } a \lor c \preccurlyeq b \lor d\)

By the definition of \(LUB\) and \(GLB,\) the join and meet, if they exist, are unique. Hence, we can consider them as binary operations on a lattice. This leads to an alternative definition of lattice.

Lattices as Algebraic Structures

A lattice can also be defined as an algebra \(\left( {L, \land, \lor } \right)\) on a set \(L\) with two binary operations \(\land\) (meet) and \(\lor\) (join). The algebra satisfies the following identities:

  1. Commutativity: \(a \land b = b \land a;\;\) \(a \lor b = b \lor a.\)
  2. Associativity: \(\left( {a \land b} \right) \land c = a \land \left( {b \land c} \right);\;\) \(\left( {a \lor b} \right) \lor c = a \lor \left( {b \lor c} \right).\)
  3. Idempotence: \(a \land a = a;\;\) \(a \lor a = a.\)
  4. Absorption: \(a \land \left( {a \lor b} \right) = a;\;\) \(a \lor \left( {a \land b} \right) = a,\)

where \(a,b,c \in L.\)

Both definitions of a lattice are equivalent.

Examples of Lattices

Partially Ordered Set \(\left({\mathcal{P}\left(\left\{ {1,2,3} \right\}\right), \subseteq}\right)\)

The poset consisting of all the subsets of \(A = \left\{ {1,2,3} \right\}\) under the relation \(\subseteq\) forms a lattice.

Example of lattice - the power set of the set of 3 elements.
Figure 2.

Every pair of elements in \(\mathcal{P}\left({A}\right)\) has a join and a meet. The join of two subsets is defined as their union, and the meet is defined as the intersection of the subsets. For example,

\[\mathbf{\text{join}}:\;\left\{ 1 \right\} \lor \left\{ 2 \right\} = \left\{ 1 \right\} \cup \left\{ 2 \right\} = \left\{ {1,2} \right\};\]

\[\mathbf{\text{meet}}:\;\left\{ 1 \right\} \land \left\{ 2 \right\} = \left\{ 1 \right\} \cap \left\{ 2 \right\} = \varnothing .\]

This result can be generalized to any set of \(n\) elements. So the power set \(\mathcal{P}\left({A}\right)\) of any set \(A\) under the subset ordering \(\subseteq\) forms a lattice.

Partially Ordered Set \(\left( {{D_{60}},\mid} \right)\)

The poset consisting of all the divisors of \(60,\) ordered by divisibility, is also a lattice. The divisors of the number \(60\) are represented by the set

\[{{D_{60}} \text{ = }}\kern0pt{\left\{ {1,2,3,4,5,6,10,12,15,20,30,60} \right\}.}\]

Example of lattice - divisors of 60 ordered by divisibility relation.
Figure 3.

The join of two elements \(a\) and \(b\) is their least common multiple \({LCM} \left({a,b}\right),\) and the meet is their greatest common divisor \({GCD} \left({a,b}\right).\) For example,

\[\mathbf{\text{join}}:\;6 \lor 10 = LCM(6,10) = 30;\]

\[\mathbf{\text{meet}}:\;6 \land 10 = GCD(6,10) = 2.\]

In general, any set of natural numbers ordered by the divisibility relation “|” forms a lattice.

Partition Lattice of a \(4\)-Element Set

A partition \(P\) of a set \(A\) is a set of non-empty pairwise disjoint subsets (blocks) \({A_1},{A_2},\ldots,{A_n}\) such that

  • The union of the blocks \(A_i\) in \(P,\) where \(1 \le i \le n,\) is equal to \(A.\) \[\bigcup\limits_{i = 1}^n {{A_i}} = {A_1} \cup {A_2} \cup \ldots \cup {A_n} = A\]
  • The partition \(P\) does not contain the empty set \(\varnothing.\) \[{A_i} \ne \varnothing \;\forall \,i\]
  • The intersection of any distinct blocks in \(P\) is empty. \[{A_i} \cap {A_j} = \varnothing \;\forall \,i \ne j\]

We can introduce the refinement order on the set of all partitions of \(A\). A partition \(Q\) is defined as a refinement of a partition \(P\) if every block in \(Q\) is a subset of a block in \(P.\) The partition \(Q\) is said to be finer than \(P,\) and respectively, the partition \(P\) is said to be coarser than \(Q.\) This ordering is denoted as \(Q \preccurlyeq P.\)

The “finer than” relation on the set of partitions of \(A\) is a partial order. Every pair of partitions has a least upper bound and a greatest lower bound, so this ordering is a lattice. The Hasse diagram below represents the partition lattice on a set of \(4\) elements.

Partition lattice on a set of 4 elements.
Figure 4.

The meet of two partitions is their common refinement, and the join of two partitions is their finest common coarsening. For example, let

\[{{P_1} = \left\{ {\left\{ {a,d} \right\},\left\{ b \right\},\left\{ c \right\}} \right\},\;\;}\kern0pt{{P_2} = \left\{ {\left\{ a \right\},\left\{ {b,c} \right\},\left\{ d \right\}} \right\}.}\]

Then

\[\mathbf{\text{join}}:\;{P_1} \lor {P_2} = \left\{ {\left\{ {a,d} \right\},\left\{ {b,c} \right\}} \right\};\]

\[{\mathbf{\text{meet}}:\;{P_1} \land {P_2} \text{ = }}\kern0pt{\left\{ {\left\{ a \right\},\left\{ b \right\},\left\{ c \right\},\left\{ d \right\}} \right\}.}\]

Some Other Examples of Lattices

  • Every totally ordered set \(\left({A, \preccurlyeq}\right)\) is a lattice. If \(a,b \in A\) and \(a \preccurlyeq b,\) then \[{a \lor b = b,\;\;}\kern0pt{a \land b = a.}\]
  • The set of \(n-\)dimensional vectors over natural numbers \(\mathbb{N}\) with the componentwise relation \(\le\) forms a lattice. Let \(\mathbf{a} = \left( {{a_1},{a_2}, \ldots ,{a_n}} \right)\) and \(\mathbf{b} = \left( {{b_1},{b_2}, \ldots ,{b_n}} \right)\) be two vectors. We define \[\mathbf{a} \le \mathbf{b} \;\text{ if } \;\forall\; i : {a_i} \le {b_i}.\] The join and meet of two vectors correspond to componentwise maximum and minimum. For example, if \(\mathbf{a} = \left( {1,2,3} \right),\) \(\mathbf{b} = \left( {4,5,6} \right),\) then \[\mathbf{a} \lor \mathbf{b} = \left( {4,5,6} \right) = \mathbf{b};\] \[\mathbf{a} \land \mathbf{b} = \left( {1,2,3} \right) = \mathbf{a}.\]
  • The set of real-valued functions on the interval \(\left[ {0,1} \right]\) ordered by the condition \[{f \le g \;\text{ if }\;}\kern0pt{f\left( t \right) \le g\left( t \right) \;\forall\; t \in \left[ {0,1} \right],}\] is also a lattice. The join and meet of two functions \(f\) and \(g\) are defined as follows: \[f \lor g = \max \left\{ {f\left( t \right), g\left( t \right)} \right\};\] \[f \land g = \min \left\{ {f\left( t \right), g\left( t \right)} \right\}.\]

Types of Lattices

In this section we consider some special lattices.

Complete Lattices

A partially ordered set \(\require{AMSsymbols}{\left( {L,\preccurlyeq} \right)}\) is called a complete lattice if all its subsets have both a join and a meet. This is a stronger condition than for a general lattice (where every pair of elements must have a join and a meet).

Any non-empty finite lattice is complete. Among other examples to be mentioned are

  • The power set \(\mathcal{P}\left({A}\right)\) of a set \(A\) ordered by the subset relation \(\subseteq.\)
  • A set of natural numbers \(\mathbb{N}\) ordered by the divisibility relation “|”.

Bounded Lattices

A lattice \({\left( {L,\preccurlyeq} \right)}\) is said to be bounded if it has a greatest element and a least element. The greatest and least elements are denoted by \(1\) and \(0\) respectively.

Let \(a\) be any element in \(L.\) Then the following identities hold:

\[{0 \lor a = a \lor 0 = a;\;\;}\kern0pt{0 \land a = a \land 0 = 0;}\]

\[{1 \land a = a \land 1 = a;\;\;}\kern0pt{1 \lor a = a \lor 1 = 1.}\]

It is obvious here that \(0 \preccurlyeq a \preccurlyeq 1.\)

An example of a bounded lattice is the power set \(\mathcal{P}\left({A}\right)\) containing all subsets of a set \(A\) ordered by the relation \(\subseteq.\) The greatest element of the lattice is the set \(A\) itself, and the least element is empty set \(\varnothing.\)

Complemented Lattices

Suppose \({\left( {L,\preccurlyeq} \right)}\) is a bounded lattice with greatest element \(1\) and least element \(0.\) Let \(a, b \in L.\) An element \(b\) is called a complement of \(a\) if

\[a \land b = 0 \;\text{ and } \;a \lor b = 1.\]

A bounded lattice \({\left( {L,\preccurlyeq} \right)}\) is said to be complemented if every element in \(L\) has a complement.

In particular, the complement of \(0\) is \(1,\) and the complement of \(1\) is \(0.\)

An example of a complemented lattice is the poset \(\left( {{D_{30}}, \mid} \right),\) where \(D_{30}\) is the set of divisors of \(30\) and “|” is the divisibility relation.

The partially ordered set (D30, |) is a complemented lattice.
Figure 5.

Every element in \(D_{30}\) has a complement:

\[{1 \to 30,\;\;}\kern0pt{2 \to 15,\;\;}\kern0pt{3 \to 10,\;\;}\kern0pt{5 \to 6,\;\;}\kern0pt{6 \to 5,\;\;}\kern0pt{10 \to 3,\;\;}\kern0pt{15 \to 2,\;\;}\kern0pt{30 \to 1.}\]

Indeed, it is easy to see that

\[{2 \lor 15 = LCM(2,15) = 30;\;\;}\kern0pt{ 2 \land 15 = GCD(2,15) = 1.}\]

The same is true for all other elements of \(D_{30}.\)

Note that not all lattices of kind \(\left( {{D_n},|} \right)\) are complemented. For example, the lattice \(\left( {{D_{20}},|} \right)\) is not complemented.

Distributive Lattices

A lattice \({\left( {L,\preccurlyeq} \right)}\) is called distributive if (and only if) for any elements \(a, b\) and \(c\) in \(L\) the following distributive properties hold:

\[a \lor \left( {b \land c} \right) = \left( {a \lor b} \right) \land \left( {a \lor c} \right);\]

\[a \land \left( {b \lor c} \right) = \left( {a \land b} \right) \lor \left( {a \land c} \right).\]

For any set \(A,\) the power set lattice \(\left({\mathcal{P}\left({A}\right), \subseteq}\right)\) is a distributive lattice.

The figure below shows the pentagon lattice and the diamond lattice that are examples of non-distributive lattices.

Pentagon Lattice and Diamond Lattice
Figure 6.

Modular Lattices

A lattice \({\left( {L,\preccurlyeq} \right)}\) is called modular if for any elements \(a, b\) and \(c\) in \(L\) the following property is satisfied:

\[a \preccurlyeq b \text{ implies } a \lor \left( {c \land b} \right) = \left( {a \lor c} \right) \land b.\]

An example of a modular lattice is the diamond lattice shown above. Consider, for example, two comparable elements \(a\) and \(1,\) so \(a \preccurlyeq 1.\) By taking \(b\) as the \(3\text{rd}\) element, we have

\[a \preccurlyeq 1 \text{ implies } a \lor \left( {b \land 1} \right) = \left( {a \lor b} \right) \land 1.\]

Calculate the joins and meets:

\[{LHS = a \lor \left( {b \land 1} \right) }={ a \lor b }={ 1;}\]

\[{RHS = \left( {a \lor b} \right) \land 1 }={ 1 \land 1 }={ 1.}\]

As it can be seen, \(LHS = RHS.\)

Boolean Lattices

A complemented distributive lattice is called a Boolean lattice.

An example of a Boolean lattice is the power set lattice \(\left({\mathcal{P}\left({A}\right), \subseteq}\right)\) defined on a set \(A.\)

Since a Boolean lattice is complemented (and, hence, bounded), it contains a greatest element \(1\) and a least element \(0\). As any lattice, a Boolean lattice is equipped with two binary operations – join \(\lor\) and meet \(\land.\) Complementation (if it is unique) can also be regarded as a unary operation denoted by \(\bar{\;}\) or \(\,^c.\) Given the operational notation, a Boolean lattice is considered as a Boolean algebra and is denoted by \(\left( {B,\lor, \land, \bar{\;}} \right).\)

The simplest Boolean algebra is defined on the set of two elements \(B=\left\{0,1\right\}\) and obeys the following rules:

  • Join (Boolean addition) operations: \[0 \lor 0 = 0 + 0 = 0;\] \[0 \lor 1 = 0 + 1 = 1;\] \[1 \lor 0 = 1 + 0 = 1;\] \[1 \lor 1 = 1 + 1 = 1.\]
  • Meet (Boolean product) operations: \[0 \land 0 = 0 \cdot 0 = 0;\] \[0 \land 1 = 0 \cdot 1 = 0;\] \[1 \land 0 = 1 \cdot 0 = 0;\] \[1 \land 1 = 1 \cdot 1 = 1.\]
  • Complementation operations: \[\bar{0} = 1;\] \[\bar{1} = 0.\]

This simple arithmetic results in the following Boolean identities, where \(a \in \left\{0,1\right\}:\)

\(a \cdot a = a\) \(a + a = a\)
\(a \cdot \bar{a} = 0\) \(a + \bar{a} = 1\)
\(1 \cdot a = a\) \(1 + a = 1\)
\(0 \cdot a = 0\) \(0 + a = a\)
\(a \cdot a = a\)
\(a + a = a\)
\(a \cdot \bar{a} = 0\)
\(a + \bar{a} = 1\)
\(1 \cdot a = a\)
\(1 + a = 1\)
\(0 \cdot a = 0\)
\(0 + a = a\)

The two-element Boolean algebra is used in mathematical logic and has many applications in computer science and digital circuitry.


Solved Problems

Click or tap a problem to see the solution.

Example 1

Which of the Hasse diagrams represent a lattice?
Hasse diagrams for lattices and non-lattices - example 1.

Example 2

Which of the Hasse diagrams represent a lattice?
Hasse diagrams for lattices and non-lattices - example 2.

Example 3

Show that the diamond lattice is not distributive.

Example 4

Show that the pentagon lattice is not distributive.

Example 5

Simplify the Boolean expressions:
  1. \(ab + a\bar{b}\)
  2. \(a + ab\)
  3. \(a\left({\bar{a} + b}\right)\)
Here \(a,b \in \left\{{0,1}\right\}.\)

Example 6

Simplify the Boolean expressions:
  1. \(a + \bar{a}b\)
  2. \(\left({\bar{a} + \bar{b}}\right)\left({\bar{a} + b}\right)\)
  3. \(\left({a + b}\right)\left({a + c}\right)\)
Here \(a,b,c \in \left\{{0,1}\right\}.\)

Example 1.

Which of the Hasse diagrams (Figure \(7\)) represent a lattice?

Solution.

Hasse diagrams for lattices and non-lattices - example 1.
Figure 7.
  1. The elements \(b\) and \(c\) do not have a least upper bound (lub). The upper bounds for them are \(d, e\) and \(f.\) The element \(f\) cannot be the lub, since \(d \preccurlyeq f\) and \(e \preccurlyeq f.\) However, the elements \(d\) and \(e\) are not comparable, so we cannot identify the least of them. Hence, this poset is not a lattice.
  2. This poset is not a lattice since the elements \(a\) and \(b\) have no greatest lower bound (glb).
  3. A lattice.
  4. A lattice.

Example 2.

Which of the Hasse diagrams (Figure \(8\)) represent a lattice?

Solution.

Hasse diagrams for lattices and non-lattices - example 2.
Figure 8.
  1. A lattice.
  2. The elements \(b\) and \(c\) have no least upper bound (lub). The upper bounds for them are \(d\) and \(e.\) However they are incomparable, so we cannot identify which of them is the lub. Therefore, this poset is not a lattice.
  3. This poset is not a lattice since the elements \(e\) and \(f\) have no lub.
  4. A lattice.

Example 3.

Show that the diamond lattice is not distributive.

Solution.

Diamond lattice
Figure 9.

To prove that a lattice \({\left( {L,\preccurlyeq} \right)}\) is not distributive, we must show that there are \(3\) elements in \(L\) such that a distributive law does not hold for them.

Let’s take the elements \(a, b\) and \(c,\) and consider the distributive law

\[a \land \left( {b \lor c} \right) = \left( {a \land b} \right) \lor \left( {a \land c} \right).\]

For the diamond lattice, we have

\[{LHS = a \land \left( {b \lor c} \right) }={ a \land 1 }={ a.}\]

\[{RHS = \left( {a \land b} \right) \lor \left( {a \land c} \right) }={ 0 \lor 0 }={ 0.}\]

As it can be seen, \(LHS \ne RHS,\) which proves that the diamond lattice is not distributive.

Example 4.

Show that the pentagon lattice is not distributive.

Solution.

Pentagon lattice
Figure 10.

We take the elements \(a, b, c\) and check for the distributive law

\[b \land \left( {c \lor a} \right) = \left( {b \land c} \right) \lor \left( {b \land a} \right).\]

Calculate the left and right sides of the identity:

\[{LHS = b \land \left( {c \lor a} \right) }={ b \land 1 }={ b.}\]

\[{RHS = \left( {b \land c} \right) \lor \left( {b \land a} \right) }={ 0 \lor a }={ a.}\]

Since \(LHS \ne RHS,\) the distributive law fails for pentagon lattice.

Example 5.

Simplify the Boolean expressions:
  1. \(ab + a\bar{b}\)
  2. \(a + ab\)
  3. \(a\left({\bar{a} + b}\right)\)
Here \(a,b \in \left\{{0,1}\right\}.\)

Solution.

Given that Boolean algebras satisfy the commutative, associative, and distributive laws, we have

  1. \(ab + a\bar{b} = ab + a\left( {1 – b} \right)\) \(\require{cancel}{= \cancel{ab} + a – \cancel{ab} = a.}\)
  2. We can write \(a + ab = a\left({1 + b}\right).\) Since \(1 + b = 1,\) we obtain \[{a + ab = a\left( {1 + b} \right) }={ a \cdot 1 }={ a.}\]
  3. \(a\left( {\bar{a} + b} \right) = a\bar{a} + ab.\) The first term is given by \[{a\bar{a} = a\left( {1 – a} \right) }={ a – aa }={ a – a }={ 0.}\] Hence, \(a\left( {a + b} \right) = ab.\)

Example 6.

Simplify the Boolean expressions:
  1. \(a + \bar{a}b\)
  2. \(\left({\bar{a} + \bar{b}}\right)\left({\bar{a} + b}\right)\)
  3. \(\left({a + b}\right)\left({a + c}\right)\)
Here \(a,b,c \in \left\{{0,1}\right\}.\)

Solution.

Recall that Boolean algebras satisfy the commutative, associative, and distributive laws.

  1. We proved in the previous example that \(a + ab = a.\) Therefore, we can write \[a + \bar{a}b = a + ab + \bar{a}b.\] Using the identities \(aa = a,\) \(a + \bar{a} = 1,\) \(a\bar{a} = 0,\) and \(1 \cdot a = a,\) we have \[{a + \bar{a}b = a + ab + \bar{a}b }={ aa + ab + a\bar{a} + \bar{a}b }={ a\left( {a + b} \right) + \bar{a}\left( {a + b} \right) }={ \left( {a + \bar{a}} \right)\left( {a + b} \right) }={ 1 \cdot \left( {a + b} \right) }={ a + b.}\]
  2. We write this expression as follows: \[{\left( {\bar{a} + \bar{b}} \right)\left( {\bar{a} + b} \right) }={ \bar{a}\bar{a} + \bar{b}\bar{a} + \bar{a}b + \bar{b}b.}\] Since \(\bar{a}\bar{a} = \bar{a},\) \(\bar{b}b = 0,\) \(b + \bar{b} = 1,\) and \(1 \cdot \bar{a} = \bar{a},\) we get \[{\left( {\bar{a} + \bar{b}} \right)\left( {\bar{a} + b} \right) }={ \bar{a}\bar{a} + \bar{b}\bar{a} + \bar{a}b + \bar{b}b }={ \bar{a} + \bar{a}\bar{b} + \bar{a}b + 0 }={ \bar{a}\left( {1 + \bar{b} + b} \right) }={ \bar{a}\left( {1 + 1} \right) }={ \bar{a} \cdot 1 }={ \bar{a}.}\]
  3. We apply here the following identities: \(aa = a,\) \(1 + b = 1,\) \(1 \cdot a = a.\) This yields: \[{\left( {a + b} \right)\left( {a + c} \right) }={ aa + ac + ba + bc }={ a + ac + ba + bc }={ a\left( {1 + c} \right) + ab + bc }={ a \cdot 1 + ab + bc }={ a + ab + bc }={ a\left( {1 + b} \right) + bc }={ a \cdot 1 + bc }={ a + bc.}\]