Substructures, Products, and Homomorphisms

Lattices and Boolean algebras form the mathematical backbone of modern algebraic logic, order theory, and digital circuit design. This guide explores their structural properties, analyzing how complex algebraic systems are decomposed into sublattices, combined via direct products, and mapped using homomorphisms.

1. Algebraic Foundations of Lattices

A lattice can be formalized from two distinct mathematical perspectives: as a partially ordered set (poset) satisfying specific extremal conditions, or as an algebraic system closed under two binary operations.

The Poset Perspective

A poset $\langle L, \le \rangle$ is a lattice if, for every pair of elements $a, b \in L$ , both the greatest lower bound (GLB) and the least upper bound (LUB) exist uniquely within $L$ .

The GLB of $a$ and $b$ is called their meet, denoted by $a \wedge b$ (or $a * b$ ). $x = a \wedge b \iff (x \le a \text{ and } x \le b) \text{ and } (\forall y \in L, y \le a \text{ and } y \le b \implies y \le x)$

The Algebraic Perspective

Alternatively, a lattice can be defined as an algebraic structure $\langle L, \wedge, \vee \rangle$ featuring two binary operations that satisfy the following axiomatic properties for all $a, b, c \in L$ :

Idempotent Laws: $a \wedge a = a \quad \text{and} \quad a \vee a = a$
Commutative Laws: $a \wedge b = b \wedge a \quad \text{and} \quad a \vee b = b \vee a$

The Principle of Duality

For any lattice statement, its dual is obtained by interchanging the meet ( $\wedge$ ) and join ( $\vee$ ) operations, alongside swapping the order relations $\le$ and $\ge$ . If a theorem is valid for all lattices, its dual is also automatically valid.

2. Fundamental Properties & Order-Operation Equivalence

The algebraic operations $\wedge, \vee$ and the partial order relation $\le$ are intrinsically linked.

Theorem: Equivalence of Order and Operations

For any lattice $\langle L, \le \rangle$ and $a, b \in L$ , the following three statements are logically equivalent:

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

plaintext

          b (LUB / Join)
         / \
        /   \
       /     \
      a       c
       \     /
        \   /
         \ /
          d (GLB / Meet)

Isotonicity (Monotonicity)

The meet and join operations are order-preserving (isotonic). 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, if $a \le c$ and $b \le d$ , then: $a \wedge b \le c \wedge d \quad \text{and} \quad a \vee b \le c \vee d$

3. Sublattices

A sublattice is not merely a subset of a lattice that happens to be a lattice under the inherited order; it must be algebraically closed under the meet and join operations of the parent lattice.

Definition: Sublattice

Let $\langle L, \wedge, \vee \rangle$ be a lattice, and let $S \subseteq L$ be a non-empty subset. $S$ is a sublattice of $L$ if and only if for all $a, b \in S$ :

Crucial Distinction: Induced Lattices vs. Sublattices

Every sublattice is a lattice under the induced ordering. However, a subset $S \subseteq L$ can form a lattice under the induced order without being a sublattice of $L$ . This occurs when the LUB or GLB of two elements in $S$ differs from their LUB or GLB in $L$ .

Pedagogical Example: Divisors of 12

Let $L = D_{12} = \{1, 2, 3, 4, 6, 12\}$ under divisibility.

Let $S = \{1, 2, 3, 12\}$ .
Under the induced order, $S$ is a poset and indeed a lattice. The join of $2$ and $3$ within $S$ () is , because is the unique least upper bound of inside .

4. Direct Products of Lattices

Given two lattices $\langle L_1, \wedge_1, \vee_1 \rangle$ and $\langle L_2, \wedge_2, \vee_2 \rangle$ , their (or Cartesian product) forms a new lattice.

Definition: Direct Product

The elements of $L_1 \times L_2$ are ordered pairs $(a, b)$ where $a \in L_1$ and . The partial order on is defined coordinate-wise:

The algebraic operations are computed component-wise: $(a_1, b_1) \wedge (a_2, b_2) = (a_1 \wedge_1 a_2, \, b_1 \wedge_2 b_2)$

This formulation scales to any finite family of lattices $\prod_{i=1}^n L_i$ .

Example: Divisor Decomposition

The divisor lattice $D_{36}$ is isomorphic to the direct product of the divisor lattices $D_4$ and $D_9$ : Every divisor can be uniquely mapped to a pair where and such that .

5. Lattice Homomorphisms

A mapping between two lattices must preserve the underlying algebraic operations to be considered a structural homomorphism.

Definition: Homomorphism

Let $\langle L, \wedge_L, \vee_L \rangle$ and $\langle S, \wedge_S, \vee_S \rangle$ be two lattices. A function is a if, for all :

Classifications of Homomorphisms

Isomorphism: A bijective (one-to-one and onto) homomorphism. If an isomorphism exists, $L$ and $S$ are structurally identical ( $L \cong S$ ).
Endomorphism: A homomorphism from a lattice $L$ to itself.
Automorphism: A bijective endomorphism (an isomorphism from $L$ to itself).

Property: Order Preservation

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

Proof:

Assume $a \le_L b$ . This implies $a \wedge_L b = a$ . Applying the homomorphism $g$ : By the order-operation equivalence, .

6. Special Lattices & Boolean Algebra

To construct a Boolean algebra, we must introduce specific structural constraints on lattices.

Special Types of Lattices

Bounded Lattice: A lattice containing a unique least element (bottom, denoted $0$ ) and a unique greatest element (top, denoted $1$ ) such that $\forall a \in L$ : $a \wedge 0 = 0, \quad a \vee 0 = a, \quad a \wedge 1 = a, \quad a \vee 1 = 1$

Non-Distributive Archetypes

Any non-distributive lattice contains a sublattice isomorphic to either the Diamond Lattice ( $M_3$ ) or the Pentagon Lattice ( $N_5$ ).

text

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

Boolean Algebra

A Boolean algebra is a complemented distributive lattice. Formally, it is written as a 6-tuple $\langle B, \wedge, \vee, ', 0, 1 \rangle$ , where $'$ is the unary complementation operator satisfying: $a \land a^{'} = 0 and$

Theorem: Uniqueness of Complements

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

Proof:

Suppose $b$ and $c$ are both complements of $a$ in a distributive lattice. $a \wedge b = 0, \quad a \vee b = 1 \quad \text{and} \quad a \wedge c = 0, \quad a \vee c = 1$ Now, expand using the identity and distributive laws: Similarly, expand : By commutativity, , which implies .

7. Structural Components: Atoms, Maxterms, and Canonical Forms

Finite Boolean algebras have highly rigid, symmetric structures governed by their minimal elements.

Join-Irreducible Elements and Atoms

An element $a$ is join-irreducible if $a = b \vee c \implies a = b$ or $a = c$ .
An atom is a non-zero element $a$ that directly "covers" . That is, there is no such that .

Stone's Representation Theorem (Finite Case)

Every finite Boolean algebra $B$ is isomorphic to the power set algebra $\mathcal{P}(A)$ of its atoms $A$ . Consequently:

The cardinality of any finite Boolean algebra is always a power of 2: $|B| = 2^n$ , where $n$ is the number of atoms.
Every element $x \in B$ can be uniquely expressed as the join (sum) of the atoms that are less than or equal to $x$ .

Antiatoms and Maxterms

An antiatom (or maxterm) is an element covered by $1$ . There is no $x$ such that $a < x < 1$ .
Antiatoms are the exact complements of atoms. Every element in a finite Boolean algebra can be uniquely expressed as the meet (product) of the antiatoms that are greater than or equal to it.

Lattices can be viewed both as posets (with unique GLB and LUB for all pairs) and as algebraic systems satisfying idempotence, commutativity, associativity, and absorption.
Sublattices are subsets closed under the operations of the parent lattice, which is a stricter condition than simply being a lattice under the induced order.
Direct Products are constructed using component-wise operations, preserving properties like distributivity.
Lattice Homomorphisms are operation-preserving maps. They are always order-preserving, though the converse is not generally true.
Boolean Algebras are complemented distributive lattices, exhibiting a highly symmetric structure where every element has a unique complement and can be uniquely decomposed using atoms (minterms) or antiatoms (maxterms).

Assessed progress

Substructures, Products, and Homomorphisms

Key Concepts

Lattice Homomorphism

Sublattice

Direct Product

Complemented Distributive Lattice

Atoms and Minterms

Quick Check

Discrete Mathematical Structures

Discrete Mathematical Structures