Algebraic Properties and Lattice Operations

Lattices provide a unified framework for studying both order relations and algebraic systems, bridging the gap between set theory, logic, and abstract algebra. This module explores the dual perspectives of lattices as partially ordered sets and algebraic structures, culminating in the formal construction of Boolean algebras.

1. Lattices as Posets

An order-theoretic definition of a lattice focuses on its structure as a partially ordered set (poset) with specific bounding properties.

A poset $\langle L, \leq \rangle$ is a lattice if and only if every pair of elements $a, b \in L$ has a unique greatest lower bound (GLB) and a unique least upper bound (LUB).

Greatest Lower Bound (GLB / Meet): The GLB of $a$ $a$ and $b$ $b$ is denoted as $a * b$ $a * b$ or $a \wedge b$ $a \land b$ . It is the unique element $x \in L$ $x \in L$ such that:
1. $x \leq a$ and $x \leq b$ (lower bound)
2. For any $y \in L$ , if $y \leq a$ and $y \leq b$ , then (greatest)
Least Upper Bound (LUB / Join): The LUB of $a$ $a$ and $b$ $b$ is denoted as $a + b$ $a + b$ or $a \vee b$ $a \lor b$ . It is the unique element $z \in L$ $z \in L$ such that:
1. and (upper bound)

Crucial Distinction: Posets vs. Lattices

Not all posets are lattices. If even a single pair of elements in a poset lacks a unique GLB or LUB, the poset fails to be a lattice.

Consider the Hasse diagram of the poset $P = \{a, b, c, d, e\}$ below:

text

In this poset, let us evaluate the pair $\{b, c\}$ :

Lower Bounds: The only element below both $b$ and $c$ is $a$ . Thus, $\text{GLB}(b, c) = a$ .
Upper Bounds: Both $d$ and $e$ are upper bounds for because and .

Because $\{b, c\}$ lacks a LUB, this poset is not a lattice.

Key Examples of Lattices

The Power Set Lattice: The power set $\mathcal{P}(S)$ $P (S)$ of any set $S$ $S$ ordered by subset inclusion $\subseteq$ $\subseteq$ is a lattice.
- $\text{GLB}(A, B) = A \cap B$ (Intersection)
- (Union)

2. The Duality Principle

The Duality Principle is a foundational symmetry in lattice theory. For any lattice $\mathcal{L} = \langle L, \leq \rangle$ , we can define its dual lattice $\mathcal{L}^{\partial} = \langle L, \geq \rangle$ by reversing the partial order relation.

Under this transformation: $\leq \quad \iff \quad \geq$ $\wedge \text{ (Meet)} \quad \iff \quad \vee \text{ (Join)}$

Theorem: Principle of Duality

If a general statement $\Phi$ is true for all lattices, then its dual statement $\Phi^{\partial}$ (obtained by replacing $\leq$ with $\geq$ , $\wedge$ with $\vee$ , and with ) is also true for all lattices.

This mathematical symmetry halves the effort required to prove many lattice properties: proving a property for the meet operation immediately validates the corresponding property for the join operation.

3. Algebraic Properties of Lattices

Lattices can be defined purely algebraically as a set $L$ equipped with two binary operations, meet ( $*$ , $\wedge$ ) and join ( $+$ , $\vee$ ). For any elements $a, b, c \in L$ , these operations must satisfy the following four fundamental pairs of axioms:

1. Idempotent Laws

$a \wedge a = a$ $a \vee a = a$

2. Commutative Laws

$a \wedge b = b \wedge a$ $a \vee b = b \vee a$

3. Associative Laws

$(a \wedge b) \wedge c = a \wedge (b \wedge c)$ $(a \vee b) \vee c = a \vee (b \vee c)$

4. Absorption Laws

$a \wedge (a \vee b) = a$ $a \vee (a \wedge b) = a$

Connecting the Algebraic and Order-Theoretic Definitions

The algebraic operations induce a partial order relation $\leq$ on the set $L$ . We define: $a \leq b \quad \iff \quad a \wedge b = a$

Equivalently, using the absorption laws, we can define the exact same relation via the join: $a \leq b \quad \iff \quad a \vee b = b$

To prove that the algebraically induced relation $\leq$ is a valid partial order, we must verify the three poset properties:

Reflexivity ( $a \leq a$ ): By the Idempotent Law, $a \wedge a = a$ . Therefore, $a \leq a$ .
Antisymmetry ( $a \leq b \text{ and } b \leq a \implies a = b$ ): If , then . If , then . By the Commutative Law:

4. Isotonicity and Sublattices

Isotonicity

Lattices preserve order under operations. This property, known as isotonicity, states that for any $a, b, c \in L$ : $a \leq b \implies (a \wedge c) \leq (b \wedge c)$

Proof of Isotonicity for Meet

Assume $a \leq b$ , which implies $a \wedge b = a$ . We must show that $(a \wedge c) \wedge (b \wedge c) = a \wedge c$ : Using idempotence () and our assumption (): Thus, . The proof for join follows by duality.

Sublattices

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

Crucial Warning: Simply being a lattice under the same induced order is not sufficient for $S$ to be a sublattice. The operations must yield the same elements as the parent lattice.

Counterexample:

Consider the lattice of divisors of 12, $D_{12} = \{1, 2, 3, 4, 6, 12\}$ , and a subset $S = \{1, 2, 3, 12\}$ .

Ordered by divisibility, $S$ forms a poset and is itself a lattice.
However, in the parent lattice $D_{12}$ , the join of 2 and 3 is: $2 \vee_{D_{12}} 3 = \text{lcm}(2, 3) = 6$

5. Direct Product and Lattice Homomorphisms

Direct Product

Given two lattices $\mathcal{L}_1 = \langle L_1, \wedge_1, \vee_1 \rangle$ and , their is a lattice on the Cartesian product set . The meet and join operations are defined coordinate-wise:

This extends naturally to $n$ -dimensions. A notable application is the $n$ -cube lattice $L^n$ where $L = \{0, 1\}$ with $0 < 1$ .

The Hasse diagram of the 3-cube lattice $L^3$ represents coordinate-wise ordering:

text

            111
           / | \
        110 101 011
         | \/ \/ |
        100 010 001
           \ | /
            000

Lattice Homomorphisms

Let $\mathcal{L}$ and $\mathcal{S}$ be lattices. A function $g: L \to S$ is a lattice homomorphism if it preserves both operations: $g(a \wedge_L b) = g(a) \wedge_S g(b)$

Isomorphism: A bijective homomorphism.
Endomorphism: A homomorphism from a lattice to itself ( $g: L \to L$ ).
Automorphism: A bijective endomorphism.

Theorem: Homomorphisms preserve order

If $g: L \to S$ is a lattice homomorphism, then it is order-preserving: $a \leq b \implies g(a) \leq g(b)$ .

Proof:

Assume $a \leq b$ , which means $a \wedge b = a$ . Apply $g$ to both sides: $g(a \wedge b) = g(a)$ Since is a homomorphism: By definition of the induced order in , this implies .

6. Special Types of Lattices

1. Complete Lattice

A lattice is complete if every subset (whether finite or infinite) has both a GLB and a LUB.

Every finite lattice is complete.
Complete lattices must contain a unique least element (denoted $0$ ) and a unique greatest element (denoted $1$ ).

2. Bounded Lattice

A lattice $L$ is bounded if it contains a least element $0$ and a greatest element $1$ such that for all $a \in L$ : $a \wedge 0 = 0 \quad \text{and} \quad a \vee 0 = a$

3. Complemented Lattice

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

We denote the complement of $a$ as $a'$ . A bounded lattice is complemented if every element in the lattice has at least one complement.

4. Distributive Lattice

A lattice $L$ is distributive if the meet and join operations distribute over each other: $a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$

Classic Non-Distributive Lattices

Lattices that fail these rules are non-distributive. The two canonical examples are the Diamond Lattice ( $M_5$ ) and the Pentagon Lattice ( $N_5$ ):

text

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

Proof of Non-distributivity in $M_5$ : Evaluate $a \wedge (b \vee c)$ : $b \vee c = 1 \implies a \wedge (b \vee c) = a \wedge 1 = a$ Evaluate : Since , the distributive identity fails.

Theorem: Complements in Distributive Lattices

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

Proof:

Let $b$ and $c$ be two complements of $a$ in a distributive lattice $L$ . This means: $a \wedge b = 0, \quad a \vee b = 1 \quad \text{and} \quad a \wedge c = 0, \quad a \vee c = 1$ We show : Applying the distributive law: This implies . By symmetrical steps: This implies . Since is antisymmetric, .

7. Boolean Algebra

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

It is denoted as a 6-tuple $\langle B, \wedge, \vee, ', 0, 1 \rangle$ , satisfying:

All properties of lattices (Idempotence, Commutativity, Associativity, Absorption).
Distributive properties.
Boundedness (possessing $0$ and $1$ ).
Existence of a unique complement $a'$ for every element $a$ .

Fundamental Examples

The Two-Element Boolean Algebra: $B = \{0, 1\}$ $B = {0, 1}$ under standard logical operation rules:
- $\wedge \implies \text{AND}$
- $\vee \implies \text{OR}$
- $^{'} ⟹ NOT$

8. Atoms, Maxterms, and Canonical Forms

Atoms and Maxterms

Within a Boolean algebra:

An element $a$ is join-irreducible if it cannot be written as the join of smaller elements.
An atom (or minterm) is a join-irreducible element that directly covers $0$ . That is, $a > 0$ , and there exists no $x$ such that $0 < x < a$ .
A maxterm (or anti-atom) is the complement of an atom. Maxterms are directly covered by .

In any finite Boolean algebra, every non-zero element can be expressed uniquely as the join of a set of atoms.

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

We represent these functions using two canonical forms:

Sum of Products (SOP) Canonical Form: Expresses a function as the join (sum) of distinct minterms.
Product of Sums (POS) Canonical Form: Expresses a function as the meet (product) of distinct maxterms.

This is the final SOP canonical form for the function.

Summary

Order vs. Algebra: Lattices are posets where every pair has a unique LUB (join) and GLB (meet). Algebraically, they are characterized by idempotence, commutativity, associativity, and absorption.
Dualities and Substructures: Reversing the ordering relation yields a dual lattice. Sublattices are subsets closed under both the meet and join operations of the parent lattice.
Specialized Lattices: Distributive lattices eliminate structures containing $M_5$ or $N_5$ sublattices. Complements in distributive lattices are always unique.
Boolean Algebra Foundations: A Boolean algebra is a complemented distributive lattice. It forms the core mathematical foundation for logic synthesis, digital systems design, and canonical expansions (SOP and POS).

Assessed progress

Algebraic Properties and Lattice Operations

Key Concepts

Lattices as Posets

Algebraic Axiomatization

Isotonicity and Sublattices

Special Lattices

Boolean Algebra

Quick Check

Discrete Mathematical Structures

Discrete Mathematical Structures