Partial Orders and Lattices

Introduction

While equivalence relations capture the notion of sameness, partial orders capture the notion of comparison or ranking. Many mathematical structures have natural orderings: numbers by magnitude, sets by inclusion, divisibility of integers. Partial orders formalize these comparison relationships.

The term partial indicates that not every pair of elements need be comparable. In a collection of sets ordered by inclusion, two sets may have neither as a subset of the other. This distinguishes partial orders from total orders like the usual ordering on real numbers.

Definition of Partial Order

A partial order on a set P is a relation ≤ satisfying three properties for all a,b,c∈P

Reflexivity

a≤a

Antisymmetry

a≤b* and *b≤a⟹a=b

Transitivity

a≤b* and *b≤c⟹a≤c

A set equipped with a partial order is called a partially ordered set or poset, denoted (P,≤). We write a<b to mean a≤b and a≠b

Note the key difference from equivalence relations: antisymmetry replaces symmetry. If a≤b and b≤a both hold, then a and b must be equal.

Hasse Diagrams

A Hasse diagram is a graphical representation of a finite poset. Elements are drawn as points with a below b when a<b An edge connects a to b if a<b and there is no c with a<c<b (we say b covers a).

Reflexivity and transitivity are implicit: every element is related to itself, and if a path goes upward from a to b then a≤b

Special Elements

Maximal and Minimal Elements

An element m∈P is maximal if there is no x∈P with m<x An element m is minimal if there is no x with x<m A poset may have multiple maximal or minimal elements.

Greatest and Least Elements

An element M∈P is the greatest element if x≤M for all x∈P An element m is the least element if m≤x for all x∈P If they exist, greatest and least elements are unique.

Upper and Lower Bounds

Let A⊆P be a subset of a poset. An element u∈P is an upper bound of A if a≤u for all a∈A Similarly, ℓ is a lower bound if ℓ≤a for all a∈A

The least upper bound (supremum) of A denoted (sup_)(A) or (⋁_^)(A) is an upper bound that is less than or equal to every other upper bound. The greatest lower bound (infimum), denoted (inf_)(A) or (⋀_^)(A) is a lower bound greater than or equal to every other lower bound.

Lattices

A lattice is a poset in which every pair of elements has both a least upper bound (join) and a greatest lower bound (meet). For elements a,b we write:

a∨b=(sup_)(a,b) (join)

a∧b=(inf_)(a,b) (meet)

Lattice Laws

The join and meet operations satisfy several algebraic identities:

Commutativity: a∨b=b∨a and a∧b=b∧a

Associativity: (a∨b)∨c=a∨(b∨c) and (a∧b)∧c=a∧(b∧c)

Idempotence: a∨a=a and a∧a=a

Absorption: a∨(a∧b)=a and a∧(a∨b)=a

Examples of Lattices

The power set 𝒫*(X) ordered by inclusion is a lattice with A∨B=A∪B and A∧B=A∩B

The positive integers under divisibility form a lattice with a∨b=lcm(a,b) and a∧b=gcd(a,b)

Special Types of Lattices

Bounded Lattices

A lattice is bounded if it has both a greatest element 1 (top) and a least element 0 (bottom). For any element a

a∨0=a,a∧1=a,a∨1=1,a∧0=0

Distributive Lattices

A lattice is distributive if the following equivalent conditions hold:

a∧(b∨c)=(a∧b)∨(a∧c)

a∨(b∧c)=(a∨b)∧(a∨c)

The power set lattice and divisibility lattice are both distributive.

Complemented Lattices

In a bounded lattice, an element a′ is a complement of a if:

a∨a′=1*and*a∧a′=0

A lattice is complemented if every element has at least one complement.

Boolean Algebras

A Boolean algebra is a bounded, distributive, complemented lattice. In a Boolean algebra, each element has a unique complement. The power set 𝒫*(X) with union, intersection, and set complement is a Boolean algebra. The connection to Boolean logic is direct: join corresponds to OR, meet to AND, and complement to NOT.

Chains and Antichains

A chain in a poset is a subset in which every pair of elements is comparable. An antichain is a subset in which no two distinct elements are comparable.

The length of a finite poset is one less than the maximum size of a chain. The width is the maximum size of an antichain. Dilworth's theorem states that in any finite poset, the minimum number of chains needed to partition the poset equals the maximum size of an antichain.

Well-Founded Orders

A partial order is well-founded if every nonempty subset has a minimal element. A total order that is well-founded is called a well-order. The natural numbers with the usual ordering are well-ordered, which is the basis for mathematical induction.

Applications

Partial orders appear throughout mathematics and computer science. Scheduling problems often involve finding a linear extension of a partial order. Concept hierarchies in databases use lattice structures. The semantics of programming languages frequently involves complete lattices and fixed point theorems.

Summary

A partial order is a reflexive, antisymmetric, and transitive relation, capturing the notion of comparison where not all elements need be comparable. Key examples include set inclusion and divisibility.

A lattice is a poset where every pair of elements has a join (least upper bound) and meet (greatest lower bound). Lattices satisfy algebraic laws including commutativity, associativity, idempotence, and absorption.

Special lattices include bounded lattices (with top and bottom), distributive lattices (where join and meet distribute), and Boolean algebras (bounded, distributive, and complemented). Boolean algebras provide the algebraic foundation for logic and set operations.

Partial orders and lattices provide essential structures for reasoning about hierarchies, dependencies, and logical relationships throughout mathematics and its applications.