Partial Orders and Lattices

Many collections are ordered, but not totally: subsets ordered by inclusion, tasks ordered by "must finish before", integers ordered by divisibility. In each case some pairs are comparable and others are not. A partially ordered set (poset) captures this. A lattice is a poset in which every two elements have a best common upper bound and a best common lower bound; lattices underlie Boolean algebra, data-flow analysis in compilers, and type hierarchies.

A relation $\preceq$ on a set $S$ is a partial order if it is

$(S, \preceq)$ is a poset. Elements $a, b$ are comparable if $a \preceq b$ or $b \preceq a$, otherwise incomparable. A poset in which every pair is comparable is a total (linear) order, or chain. A set of pairwise incomparable elements is an antichain. We write $a \prec b$ for $a \preceq b$ and $a \ne b$ (a strict order: irreflexive and transitive).

Standard examples: $(\mathbb{Z}, \le)$ (total); $(\mathcal{P}(A), \subseteq)$ (not total when $|A| \ge 2$); $(\mathbb{Z}^{+}, \mid)$ where $a \mid b$ means "$a$ divides $b$" (not total: 2 and 3 are incomparable). Divisibility on all of $\mathbb{Z}$ is not a partial order, because $2 \mid -2$ and $-2 \mid 2$ with $2 \ne -2$.

A well-ordered set is a total order in which every non-empty subset has a least element: $(\mathbb{N}, \le)$ is well-ordered, $(\mathbb{Z}, \le)$ is not. Well-ordering is the basis of mathematical induction.

A Hasse diagram draws a finite poset without redundant information. $b$ covers $a$ if $a \prec b$ and there is no $c$ with $a \prec c \prec b$. Draw an upward edge from $a$ to $b$ for each covering pair only: omit loops (reflexivity), omit edges implied by transitivity, and omit arrowheads (larger elements are higher).

Let $(S, \preceq)$ be a poset and $T \subseteq S$.

Key distinctions:

Every finite partial order can be extended to a total order compatible with it (a linear extension, or topological sort): repeatedly remove a minimal element and append it to the output. This is how a build system or a course planner orders tasks; the graph version is in Depth-First Search. $D_{12}$ has 5 linear extensions, for example $1, 2, 3, 4, 6, 12$ and $1, 3, 2, 6, 4, 12$.

A poset $(L, \preceq)$ is a lattice if every pair $a, b \in L$ has both a least upper bound and a greatest lower bound in $L$:

Joins and meets in any lattice satisfy, for all $a, b, c$: commutativity, associativity, idempotence ($a \lor a = a$), and the absorption laws $a \lor (a \land b) = a$ and $a \land (a \lor b) = a$. Conversely, a set with two operations satisfying these laws is a lattice under $a \preceq b \iff a \land b = a$. Also $a \preceq b \iff a \lor b = b$.

To show a poset is not a lattice, find a pair with no lub (two or more minimal upper bounds, or none) or no glb.

Test for distributivity (Birkhoff's theorem): a lattice is distributive if and only if it contains no sublattice isomorphic to the pentagon $N_5$ or the diamond $M_3$.

Both are complemented but not distributive; in $M_3$, $a$ has the two complements $b$ and $c$.

$D_n$, the positive divisors of $n$ under divisibility, is always a distributive lattice with $0 = 1$ (the number one) and top $= n$. The complement of $d$, if it exists, must be $n/d$ with $\gcd(d, n/d) = 1$. Hence:

Examples: $D_{30}$ ($30 = 2 \cdot 3 \cdot 5$) is a Boolean algebra with 8 elements, isomorphic to $\mathcal{P}(\{2, 3, 5\})$. $D_{12}$ is not complemented: 2 has no complement, since $\operatorname{lcm}(2, d) = 12$ needs $4 \mid d$ and then $\gcd(2, d) \ge 2$.

Poset $(\{2, 3, 4, 6, 9, 12, 18\}, \mid)$. Minimal elements: 2 and 3 (no proper divisor in the set). Maximal: 12 and 18. No least or greatest element. Upper bounds of $\{2, 3\}$: 6, 12, 18; least upper bound 6. Upper bounds of $\{4, 6\}$: only 12, so the lub is 12. Upper bounds of $\{12, 18\}$: none in the set, so this poset is not a lattice.

$S = \{1, 2, 3, 12, 18, 36\}$ under divisibility. Upper bounds of $\{2, 3\}$ in $S$: 12, 18, 36. Since 12 and 18 are incomparable and both are minimal upper bounds, $\{2, 3\}$ has no lub. Not a lattice.

In $D_{30}$: complement of 6 is 5 ($\operatorname{lcm} = 30$, $\gcd = 1$); complement of 10 is 3. Every element has exactly one complement.

In $D_{36}$ ($36 = 2^2 3^2$, not square-free): elements $1, 2, 3, 4, 6, 9, 12, 18, 36$. Only 1, 4, 9, 36 have complements (the pairs $1 \leftrightarrow 36$ and $4 \leftrightarrow 9$); 2, 3, 6, 12 and 18 have none.

In $D_{12}$, how many ordered pairs $(a, b)$ satisfy $a \mid b$? For each $b$, count its divisors: $1 + 2 + 2 + 3 + 4 + 6 = 18$. This includes the 6 reflexive pairs, so the strict order has 12 pairs, of which 7 are covering edges.