# Calculus

## Set Theory # Lattices

## Lattices as Posets

A partially ordered set $${\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.$$

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,

$\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}} = \left\{ {1,2,3,4,5,6,10,12,15,20,30,60} \right\}.$

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.

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

$0 \lor a = a \lor 0 = a;\;\;0 \land a = a \land 0 = 0;$
$1 \land a = a \land 1 = a;\;\;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.

Every element in $$D_{30}$$ has a complement:

$1 \to 30,\;\;2 \to 15,\;\;3 \to 10,\;\;5 \to 6,\;\;6 \to 5,\;\;10 \to 3,\;\;15 \to 2,\;\;30 \to 1.$

Indeed, it is easy to see that

$2 \lor 15 = LCM(2,15) = 30;\;\;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.

### 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{\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:

$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\}:$$