Distributive, Bounded, and Complemented Lattices

Lattices provide the foundational mathematical framework that bridges order theory, abstract algebra, and mathematical logic. This guide explores special classes of lattices—distributive, bounded, and complemented—culminating in the formal algebraic structures of Boolean algebra.

1. Lattices as Posets

A partially ordered set (poset) is a pair $\langle P, \le \rangle$ where $\le$ is a binary relation over the set $P$ satisfying reflexivity, antisymmetry, and transitivity. A lattice is a specialized poset wherein every pair of elements has a unique supremum and infimum.

Let $\langle L, \le \rangle$ be a poset, and let $a, b \in L$ .

The greatest lower bound (GLB) of $a$ and $b$ is called their meet, denoted by $a \wedge b$ (or $a \cdot b$ , $a * b$ ). It represents the unique element $x \in L$ such that , and for any where and , we have .

A poset is a lattice if and only if both $a \wedge b$ and $a \vee b$ exist for all $a, b \in L$ .

Standard Examples of Lattices

The Power Set Lattice: Let $S$ be any set. The power set $\mathcal{P}(S)$ ordered by subset inclusion ( $\subseteq$ ) forms a lattice. Here, the meet is the set intersection ( $\cap$ ) and the join is the set union ( $\cup$ ): $A \wedge B = A \cap B \quad \text{and} \quad A \vee B = A \cup B$

text

Hasse Diagram of the Divisor Lattice D_12:
 
       12
      /  \
     4    6
     |   /|
     |  / |
     2    3
      \  /
       1

2. Properties of Lattices

For any lattice $\langle L, \le \rangle$ , the meet and join operations satisfy several fundamental algebraic identities.

The Duality Principle

The dual of any statement in a lattice $\langle L, \le \rangle$ is the statement obtained by interchanging $\le$ with $\ge$ , and consequently interchanging meet ( $\wedge$ ) with join ( $\vee$ ). If a statement is true for all lattices, its dual is also true.

Fundamental Identities

For all elements $a, b, c \in L$ , the following laws hold:

Idempotence: $a \wedge a = a \quad \text{and} \quad a \vee a = a$
Commutativity: $a \wedge b = b \wedge a \quad \text{and} \quad a \vee b = b \vee a$

Connection Between Order and Operations

The partial ordering relation $\le$ can be defined strictly through meet or join: $a \le b \iff a \wedge b = a \iff a \vee b = b$

Isotonicity (Monotonicity)

The meet and join operations are order-preserving. If $a \le b$ , then for any $c \in L$ : $a \wedge c \le b \wedge c \quad \text{and} \quad a \vee c \le b \vee c$

More generally: $\text{If } a \le c \text{ and } b \le d, \text{ then } a \wedge b \le c \wedge d \text{ and } a \vee b \le c \vee d$

3. Algebraic Characterization of Lattices

Alternatively, a lattice can be defined purely as an algebraic system $\langle L, \wedge, \vee \rangle$ consisting of a set $L$ and two binary operations satisfying the Commutative, Associative, and Absorption laws.

The partial order relation $\le$ is then defined as a derived relation: $a \le b \overset{\text{def}}{\iff} a \wedge b = a$

This derived relation is guaranteed to be reflexive, antisymmetric, and transitive:

Reflexivity: Since $a \wedge a = a$ (derived from absorption), we have $a \le a$ .
Antisymmetry: If $a \le b$ and $b \le a$ , then and . By commutativity, .

4. Sublattices

A non-empty subset $S \subseteq L$ of a lattice $\langle L, \wedge, \vee \rangle$ is a sublattice if it is closed under the meet and join operations of $L$ . That is: $\forall a, b \in S \implies (a \wedge b) \in S \quad \text{and} \quad (a \vee b) \in S$

Crucial Distinction: Sub-poset vs. Sublattice

A subset $S$ can be a lattice in its own right under the induced partial order from $L$ , yet fail to be a sublattice because its meet and join operations do not coincide with those of $L$ .

text

Let L be the lattice of subsets of {1, 2}:
             {1,2}
            /     \
         {1}       {2}
            \     /
              empty
 
Consider the subset S = { empty, {1}, {2} }.
Under the induced order, S is a poset.
However, in S, the supremum of {1} and {2} does not exist because {1,2} is missing.
Thus, S is not a sublattice of L.

5. Direct Product of Lattices

Given two lattices $\langle L_1, \wedge_1, \vee_1 \rangle$ and $\langle L_2, \wedge_2, \vee_2 \rangle$ , their is a new lattice defined on the Cartesian product set:

The partial order and operations are defined component-wise: $(a_1, b_1) \le (a_2, b_2) \iff a_1 \le_1 a_2 \text{ and } b_1 \le_2 b_2$

This concept generalizes to $n$ dimensions. For example, if $L = \{0, 1\}$ , then $L^n$ forms an $n$ -dimensional hypercube lattice.

6. Lattice Homomorphisms and Isomorphisms

A mapping $g: L \to S$ between two lattices $\langle L, \wedge_L, \vee_L \rangle$ and is a if it preserves both operations:

Classifications

Isomorphism: A bijective homomorphism. If an isomorphism exists, $L$ and $S$ are structurally identical ( $L \cong S$ ).
Endomorphism: A homomorphism from $L$ to itself.
Automorphism: An isomorphism from $L$ to itself.

Key Theorem: Order Preservation

Every lattice homomorphism $g: L \to S$ is order-preserving: $a \le_L b \implies g(a) \le_S g(b)$

Proof: If $a \le_L b$ , then $a \wedge_L b = a$ . Applying $g$ : Note, however, that not every order-preserving map is a lattice homomorphism.

7. Distributive Lattices

A lattice $\langle L, \wedge, \vee \rangle$ is distributive if the meet operation distributes over join, and the join operation distributes over meet.

$\forall a, b, c \in L:$ $a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c) \quad \text{(Distributivity of } \wedge \text{ over } \vee \text{)}$

In any lattice, these two laws are equivalent: if one holds for all elements, the other does as well.

Forbidden Sublattices (Birkhoff's Theorem)

A lattice is distributive if and only if it does not contain a sublattice isomorphic to the Pentagon lattice ( $N_5$ ) or the Diamond lattice ( $M_3$ ).

text

The Diamond Lattice (M3)            The Pentagon Lattice (N5)
           1                                   1
         / | \                                / \
        a  b  c                              a   b
         \ | /                               |   |
           0                                 |   c
                                              \ /
                                               0

In $M_3$ : $a \wedge (b \vee c) = a \wedge 1 = a$ , while $(a \land$ . Since , distributivity fails.

8. Bounded, Complete, and Complemented Lattices

Complete Lattices

A lattice $L$ is complete if every non-empty subset $S \subseteq L$ has both a greatest lower bound ( $\bigwedge S$ ) and a least upper bound ( $\bigvee S$ ). Every finite lattice is complete.

Bounded Lattices

A lattice $L$ is bounded if it contains a unique least element (denoted $0$ or $\bot$ ) and a unique greatest element (denoted $1$ or $\top$ ) such that for all $a \in L$ : $0 \le a \le 1$

The bounds satisfy the following boundary identities: $a \vee 0 = a \quad \text{and} \quad a \wedge 1 = a$ $a \wedge 0 = 0 \quad \text{and} \quad a \vee 1 = 1$

Complements

In a bounded lattice $L$ , an element $b \in L$ is a complement of $a \in L$ if: $a \wedge b = 0 \quad \text{and} \quad a \vee b = 1$

Complements are symmetric: if $b$ is a complement of $a$ , then $a$ is a complement of $b$ .
The boundary elements $0$ and $1$ are complements of each other.
In general lattices, an element may have zero, one, or multiple complements.

Complemented Lattices

A bounded lattice is a complemented lattice if every element $a \in L$ has at least one complement.

text

A non-distributive, complemented lattice (M3):
Each of the elements a, b, and c is a complement of the others.
For example, a ^ b = 0 and a v b = 1.
Hence, complements are not unique in non-distributive lattices.

9. Boolean Algebra

A Boolean algebra is defined algebraically as a complemented distributive lattice.

Formally, it is an algebraic structure $\langle B, \wedge, \vee, ', 0, 1 \rangle$ where:

$\langle B, \wedge, \vee \rangle$ is a distributive lattice.
$0$ and $1$ are the identity elements for $\vee$ and $\wedge$ , respectively.
$'$ is a unary operation representing complementation satisfying:

Theorem: Uniqueness of Complements

In any distributive lattice $L$ , if an element $a$ has a complement, that complement is unique.

Proof: Suppose $b$ and $c$ are both complements of $a$ . Then: $a \wedge b = 0, \quad a \vee b = 1 \quad \text{and} \quad a \wedge c = 0, \quad a \vee c = 1$

Using distributivity: $b = b \wedge 1 = b \wedge (a \vee c) = (b \wedge a) \vee (b \wedge c) = 0 \vee (b \wedge c) = b \wedge c$

Since $b \wedge c = c \wedge b$ , it follows that $b = c$ .

Power Set as a Boolean Algebra

For any set $S$ , $\langle \mathcal{P}(S), \cap, \cup, ^c, \emptyset, S \rangle$ is a Boolean algebra, where $A^c = S \setminus A$ is the absolute complement.

10. Atoms and Maxterms in Boolean Algebra

In finite Boolean algebras, elements can be decomposed into minimal structural building blocks.

Atoms

An element $a$ in a Boolean algebra $B$ is an atom (or minterm) if $a \neq 0$ and it covers $0$ . That is: $\forall x \in B, \quad 0 \le x \le a \implies x = 0 \text{ or } x = a$

Atomic Representation: In a finite Boolean algebra, every non-zero element $x$ can be uniquely expressed as the join of a set of atoms: $x = a_1 \vee a_2 \vee \dots \vee a_k \quad \text{where each } a_i \text{ is an atom.}$

Maxterms (Antiatoms)

An element $m \in B$ is a maxterm (or antiatom) if $m \neq 1$ and $m$ is covered by $1$ . $\forall x \in B, m \leq x \leq 1 ⟹ x = m or x =$

Maxterms are the exact complements of atoms: if $a$ is an atom, then $a'$ is a maxterm. Every element in a finite Boolean algebra can be uniquely expressed as the meet of maxterms.

11. Boolean Functions and Canonical Forms

A Boolean function of $n$ variables is a mapping $f: B^n \to B$ , where $B = \{0, 1\}$ . There are $2^{2^n}$ distinct Boolean functions of variables.

Minterms and Sum-of-Products (SOP) Form

A minterm of $n$ variables $x_1, x_2, \dots, x_n$ is a product (meet) of literals, where each literal is either a variable or its complement .

Any Boolean function $f$ can be uniquely represented as the sum (join) of the minterms for which the function evaluates to $1$ . This is the Sum-of-Products (SOP) Canonical Form (or Disjunctive Normal Form): $f(x, y, z) = (x \wedge y \wedge z) \vee (x \wedge y' \wedge z) \vee (x' \wedge y \wedge z')$

Maxterms and Product-of-Sums (POS) Form

A maxterm of $n$ variables is a sum (join) of $n$ literals, where each variable appears exactly once.

Any Boolean function $f$ can be uniquely represented as the product (meet) of the maxterms for which the function evaluates to $0$ . This is the Product-of-Sums (POS) Canonical Form (or Conjunctive Normal Form): $f(x, y, z) = (x \vee y \vee z) \wedge (x \vee y' \vee z) \wedge (x' \vee y \vee z')$

Summary

A lattice is a poset supporting unique meet ( $\wedge$ ) and join ( $\vee$ ) operations for any pair of elements.
Distributive lattices satisfy the distributive laws of meet over join (and vice versa). Structurally, they are free of $N_5$ (pentagon) and $M_3$ (diamond) sublattices.
A bounded lattice features absolute global bounds and .

Assessed progress

Distributive, Bounded, and Complemented Lattices

Key Concepts

Lattices as Posets

Distributive Lattices

Bounded Lattices

Complemented Lattices

Boolean Algebra

Quick Check

Discrete Mathematical Structures

Discrete Mathematical Structures