Lattices

Lattices as Posets

A partially ordered set (A, ≼) is called a lattice if every pair of elements a and b in L has both a least upper bound (LUB) and a greatest lower bound (GLB).

The least upper bound is also called the join of a and b, denoted by a ∨ b. The greatest lower bound is also called the meet of a and b, and is denoted by a ∧ b.

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.

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,

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

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,

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.

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

Then

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,\;\;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 }\;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 \({\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:

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 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.

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

Indeed, it is easy to see that

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:

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.

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:

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

Calculate the joins and meets:

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{\phantom{w}}\) or \(\,^c.\) Given the operational notation, a Boolean lattice is considered as a Boolean algebra and is denoted by \(\left( {B,\lor, \land, \bar{\phantom{w}}} \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\}:\)

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