Chapter 13 — Key Takeaways

Partial Orders, Lattices, and Boolean Algebra — the one-page reference. Reread before an exam.

The three relation "families" (Ch. 12 → 13)

Family Properties Meaning Symbol
Equivalence relation (Ch. 12) reflexive + symmetric + transitive groups into classes ("same") $\sim$
Partial order reflexive + antisymmetric + transitive ranks ("≤") $\preceq$
Total order partial order + every pair comparable a single line / chain $\le$

The one swap: equivalence → partial order is symmetric → antisymmetric.

Definitions at a glance

Term Definition
Partial order $\preceq$ reflexive, antisymmetric, transitive relation
Poset $(S,\preceq)$ a set with a partial order on it
Comparable $a\preceq b$ or $b\preceq a$
Incomparable $a\parallel b$ neither $a\preceq b$ nor $b\preceq a$
Covers: $b$ covers $a$ $a\prec b$ and no $z$ with $a\prec z\prec b$
Hasse diagram draw only covering edges; greater = higher; no loops, no arrowheads
Maximal / minimal nothing strictly above / below it (can be several)
Greatest / least $\succeq$ everyone / $\preceq$ everyone (at most one; unique if it exists)
Chain subset, all pairs comparable (= a totally ordered piece)
Antichain subset, all distinct pairs incomparable (= mutually independent)
Topological sort a total order consistent with $\preceq$ (a linear extension)
Upper / lower bound of $a,b$ $u\succeq a,b$ / $\ell\preceq a,b$
Join $a\vee b$ (lub) least upper bound
Meet $a\wedge b$ (glb) greatest lower bound
Lattice poset where every pair has a join and a meet
Bounded lattice has a bottom $0$ and top $1$ (every finite lattice is bounded)
Boolean algebra distributive, complemented, bounded lattice

Touchstone posets / lattices

Poset $\preceq$ Join $\vee$ Meet $\wedge$ Bottom / Top
$(\mathcal{P}(S),\subseteq)$ subset $\cup$ union $\cap$ intersection $\emptyset$ / $S$
$(\mathbb{Z}^{+},\mid)$ divides $\operatorname{lcm}$ $\gcd$ $1$ / (none, infinite)
$(\mathbb{Z},\le)$ $\le$ $\max$ $\min$ none / none
$\{0,1\}$ (Boolean) $0\preceq1$ OR AND $0$ / $1$

Mnemonic: $\vee$ = join goes up (lcm, $\cup$, $\max$, OR). $\wedge$ = meet goes down (gcd, $\cap$, $\min$, AND).

Key theorems / facts

Result Statement
Minimal-element lemma Every finite nonempty poset has a minimal element (no infinite descent).
Topological sort exists Every finite poset has a topological sort. Proof: peel off a minimal element, repeat; induction on $\lvert S\rvert$.
Poset ↔ DAG A finite poset = a directed acyclic graph; topo sort = linearizing it. Acyclic ⇔ antisymmetric + transitive.
Topo sort fails ⇔ cycle No topological order exists iff the dependency graph has a cycle (circular dependency).
Uniqueness of $\vee,\wedge$ When a join/meet exists it is unique — proved by antisymmetry.
Duality Every lattice/Boolean statement has a mirror under $\vee\leftrightarrow\wedge$, $0\leftrightarrow1$.
Mirsky / Dilworth longest chain = min # antichains to cover; largest antichain = min # chains to cover.

Boolean algebra laws (memorize the pairs)

Law $\vee$ form $\wedge$ form
Identity $a\vee 0=a$ $a\wedge 1=a$
Domination $a\vee 1=1$ $a\wedge 0=0$
Idempotent $a\vee a=a$ $a\wedge a=a$
Commutative $a\vee b=b\vee a$ $a\wedge b=b\wedge a$
Associative $(a\vee b)\vee c=a\vee(b\vee c)$ $(a\wedge b)\wedge c=a\wedge(b\wedge c)$
Distributive (makes it Boolean) $a\vee(b\wedge c)=(a\vee b)\wedge(a\vee c)$ $a\wedge(b\vee c)=(a\wedge b)\vee(a\wedge c)$
De Morgan $\overline{a\vee b}=\overline a\wedge\overline b$ $\overline{a\wedge b}=\overline a\vee\overline b$
Complement $a\vee\overline a=1$ $a\wedge\overline a=0$
Absorption (derived) $a\vee(a\wedge b)=a$ $a\wedge(a\vee b)=a$

Same eight laws govern: truth values (Ch. 1 logic), subsets ($\mathcal{P}(S)$), and logic gates.

Logic gates ↔ Boolean ops

Gate Op Output 1 when…
AND $a\wedge b$ (meet) both inputs 1
OR $a\vee b$ (join) at least one input 1
NOT $\overline a$ input is 0

Half adder: $\text{sum}=a\oplus b=(a\wedge\overline b)\vee(\overline a\wedge b)$, $\;\text{carry}=a\wedge b$.

"When to use what" decision rules

  • Is it a poset? → reflexive ✔ antisymmetric ✔ transitive ✔ — and state the domain (divisibility needs $\mathbb{Z}^{+}$, not $\mathbb{Z}$).
  • Is it a total order? → poset and no incomparable pair (one chain).
  • Is it a lattice? → every pair has a unique lub and glb. (The "X"/diamond-without-top poset is not a lattice: two incomparable upper bounds, no least.)
  • Need a legal sequence from constraints? → topological sort the DAG. Output shorter than node count ⇒ cycle.
  • Drawing a poset? → Hasse diagram: covers only, higher = greater, no loops/arrows.

Common pitfalls

Pitfall Fix
Calling $(\mathbb{Z},\mid)$ a poset Antisymmetry fails ($2\mid-2$, $-2\mid2$). Use $\mathbb{Z}^{+}$.
Confusing maximal with greatest Maximal = nothing above; greatest = above everyone. Many maximal, ≤1 greatest.
Drawing transitive/reflexive edges in a Hasse diagram Draw covers only; no self-loops, no implied edges.
Assuming every poset is a lattice Need a unique lub & glb for every pair (the X poset fails).
Topologically sorting a graph with a cycle No order exists; detect via in-degree (Kahn) or report circular dependency.
Forgetting distributivity is the special law Generic lattices need not distribute; Boolean algebras do.

Toolkit addition (relations.py)

topo_sort(dag)   # dag = {node: [successors]}; Kahn's algorithm.
                 # Returns a list with every edge u->v having u before v.
                 # Raises ValueError on a cycle (no valid order).

Completes relations.py (with Ch. 12's is_equivalence, closure_transitive). Reused in Ch. 28 (topo sort via DFS) and the Ch. 39 social-network capstone track.

Cross-reference compass

  • Builds on: Ch. 12 (relations & their properties; transitive closure), Ch. 1 (propositional logic / De Morgan).
  • Sets up: Ch. 28 (topological sort re-derived from DFS).
  • Lattice operations $\gcd/\operatorname{lcm}$ reappear in Ch. 22 (Euclidean algorithm).