Day 40 — Partial orders

Day 40 — Partial orders

Stage IV · concept day
Goal: Define partial orders and posets; draw Hasse diagrams; use comparable vs incomparable; work with chains and antichains; connect to topological order; meet/join lattices lite; product orders.

Why this matters

Dependencies among tasks, package versions, subset inclusion, and integer divisibility are orders that need not compare every pair. Topological sort linearizes a partial order—the algorithm side of DAGs. Lattices appear in type systems and program analysis (awareness).

Theory

Partial order

A relation \(\le\) on \(A\) is a partial order when it is reflexive, antisymmetric, and transitive.
The pair \((A,\le)\) is a poset (partially ordered set).

Strict order \(<\) often defined by \(a < b \Leftrightarrow a\le b \wedge a\neq b\) (irreflexive, transitive).

Total (linear) order

A partial order is total if every pair is comparable: \(\forall a,b,\; a\le b \lor b\le a\).
\((\mathbb{Z},\le)\) total; \((\mathcal{P}(X),\subseteq)\) not total if \(|X|\ge 2\).

Comparability

\(a\) and \(b\) are comparable if \(a\le b\) or \(b\le a\); otherwise incomparable (\(a \parallel b\)).

Hasse diagrams

For finite posets: draw \(a\) below \(b\) with an edge if \(a < b\) and no \(c\) with \(a < c < b\) (cover relation). Omit transitive edges and loops. Read upward as increasing.

Chains and antichains

• Chain: subset where every two elements are comparable (totally ordered subset).
  
• Antichain: subset where no two distinct elements are comparable.

Height ≈ size of largest chain (conventions vary by inclusive).
Width ≈ size of largest antichain (Dilworth’s theorem awareness: width = min number of chains in a chain partition).

Extrema

• Maximal: no strictly larger element.
  
• Maximum: \(\ge\) all elements (unique if exists).
  
• Minimal / minimum dual.

Finite nonempty posets have maximal elements; not always a unique maximum.

Topological order

A topological order of a finite poset is a total order \(\preceq\) that extends \(\le\): \(a\le b \Rightarrow a\preceq b\).
Exists iff the strict order is acyclic (always for partial orders).
For a DAG of tasks: edge \(a\to b\) means \(a\) before \(b\); topo sort lists a linear schedule.

Lattices (lite)

A poset is a lattice if every two elements \(a,b\) have a meet \(a\wedge b = \mathrm{glb}\{a,b\}\) and join \(a\vee b = \mathrm{lub}\{a,b\}\).
Bounded lattice has top \(1\) and bottom \(0\).
Examples: \((\mathcal{P}(X),\subseteq)\) with \(\cap,\cup\); \((\mathbb{N},\mid)\) with \(\gcd,\mathrm{lcm}\) (on positives).
Not all posets are lattices (missing joins).

Product order

On \(A\times B\), set \((a,b) \le (a',b')\) iff \(a\le a'\) and \(b\le b'\).
Componentwise. Used for multi-criteria comparison (Pareto: incomparable tradeoffs).

Dual poset

Reverse the order: \(a \le^{\mathrm{op}} b \Leftrightarrow b\le a\).

Worked examples

Example 1 — Divisibility poset

\((\{1,2,3,4,6,12\},\mid)\). Hasse: \(1\) at bottom; \(12\) at top; \(2,3\) above \(1\); etc.

Example 2 — Power set

\(\mathcal{P}(\{1,2\})\) Boolean lattice: \(\emptyset\) bottom, full set top, two middle incomparable singletons.

Example 3 — Incomparable

\(\{1\}\) and \(\{2\}\) under \(\subseteq\).

Example 4 — Chain

\(\emptyset \subset \{1\} \subset \{1,2\}\) chain of size \(3\).

Example 5 — Antichain

All singletons in \(\mathcal{P}([n])\) form an antichain (Sperner capacity awareness).

Example 6 — Maximal vs maximum

In \(\{2,3,4\}\) under divisibility: \(4\) and \(3\) maximal; no maximum.

Example 7 — Topological order

Tasks \(A\le C\), \(B\le C\) (must finish \(A,B\) before \(C\)): orders \(A,B,C\) or \(B,A,C\).

Example 8 — Product order

\((1,3)\) and \((2,2)\) incomparable in \(\mathbb{R}^2\) with product order if using usual \(\le\).

Example 9 — Meet join

In \(\mathcal{P}(X)\), meet \(= \cap\), join \(=\cup\).

Example 10 — Not lattice

A four-element “bowtie” or certain truncated posets missing glb—standard textbook V shape with two tops can lack join if two maxima… actually two maxima lack join if no common upper bound unique—use a poset with two maxima and no top.

Example 11 — Total order Hasse

A path (line) Hasse diagram.

Example 12 — Package versions

Version constraints as order—often not total across products.

Example 13 — Schedule

Critical path ≈ long chain of dependencies.

Example 14 — Dual

Maximal become minimal in dual.

Exercises

1. Prove \(\subseteq\) is a partial order on \(\mathcal{P}(X)\).
   
2. Prove \(\mid\) is a partial order on \(\mathbb{Z}^+\).
   
3. Draw Hasse diagram for \((\{1,2,3,4,6,12\},\mid)\).
   
4. Find all maximal elements in that poset.
   
5. Find a largest chain and a largest antichain in \(\mathcal{P}(\{1,2,3\})\).
   
6. Give two topological orders for a poset you draw with \(4\) elements.
   
7. Show \((\mathbb{Z},\le)\) is total.
   
8. Product order on \(\{0,1\}^2\): draw Hasse.
   
9. Prove: in a poset, at most one maximum.
   
10. Finite nonempty poset has a maximal element (use finite chain extension / proof).
    
11. Is “proper subset” \(\subsetneq\) a partial order? (Reflexive?)
    
12. Meet and join of \(\{1,2\}\) and \(\{1,3\}\) in \(\mathcal{P}(\{1,2,3\})\).
    
13. \(\gcd\) and \(\mathrm{lcm}\) as meet and join for divisibility—compute for \(12,18\).
    
14. CS: list files with include-dependencies as topo sort requirement.
    
15. Dilworth awareness: width of Boolean lattice middle level.
    
16. Can a partial order have two distinct minima? Yes—example.
    
17. Prove antisymmetry of \(\le\) from a Hasse (no—prove from definition on divisibility).
    
18. Strict order \(<\) is not reflexive—confirm.
    
19. Extend a small partial order to a total order (linear extension) by listing.
    
20. Why does a cycle in “must before” prevent topo sort?
    
21. Lattice or not: chain of \(3\) elements.
    
22. Lattice or not: antichain of \(2\) elements with no extra bounds—add top and bottom?
    
23. Prove product of two posets is a poset.
    
24. Find incomparable tasks in a real project sketch (3–5 tasks).
    
25. Explain Pareto front as antichain in product order of objectives.

CS connection

• Topological sort of build/package/task DAGs.
  
• Subtype lattices and inheritance (not always lattices).
  
• Version constraints and dependency resolution.
  
• Program analysis abstract domains as lattices (awareness).
  
• Git history is not a total order (merges)—poset of commits.
  
• Scheduling and critical path = long chain.

Common pitfalls

Pitfall	What to do instead
Assuming all pairs comparable	Check total vs partial
Maximal = maximum	Maximum compares to all
Drawing all transitive edges in Hasse	Only covers
Confusing chain with path in unrelated graph	Chain = totally ordered subset
Forcing joins that do not exist	Not every poset is a lattice
Topo sort on cyclic deps	Impossible—fix cycle

Checkpoint

• Define partial order / poset
  
• Draw a Hasse diagram
  
• Chain vs antichain examples
  
• Maximal vs maximum
  
• Topological order connection
  
• Meet/join lite on power set or divisibility
  
• Product order example
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — linear extensions

A linear extension of a poset is a total order refining it—exactly a topological order of the Hasse DAG. Counting linear extensions is hard in general (#P); for small posets, list them by hand.

Multisets and schedules

If tasks have duration, longest chain ≈ critical path length (in unit durations, chain size). Width ≈ maximum parallel antichain (Dilworth/Mirsky dualities awareness).

Boolean lattice structure

\((\mathcal{P}([n]),\subseteq)\):

• Rank levels by cardinality.
  
• Largest antichain is middle level(s) (Sperner’s theorem awareness).
  
• Height \(n+1\) (chain empty to full).
  
• Complements give order-reversing involution.

Product order vs lexicographic order

Lex order on \(A\times B\): \((a,b)\le_{lex}(a',b')\) if \(a<a'\) or (\(a=a'\) and \(b\le b'\)).
This is total if \(A,B\) are total—different from product order, which can have incomparabilities. Dictionary order is lex.

More worked examples

Example 15 — Hasse for product
\(\{0,1\}^2\) product order: square with bottom \((0,0)\), top \((1,1)\), two mids incomparable.

Example 16 — Minimal elements of divisors of 30
On divisors of \(30\) under \(\mid\): minimal is \(1\), maximal \(30\).

Example 17 — Topo
Edges \(1\to 2,1\to 3,2\to 4,3\to 4\): linear extensions include \(1,2,3,4\) and \(1,3,2,4\).

Example 18 — Not lattice
Poset with elements \(a,b\) maximal incomparable and no top has no join \(a\vee b\).

Additional exercises

26. Draw Hasse of \(\mathcal{P}(\{1,2,3\})\).
    
27. Prove at most one maximum in a poset.
    
28. Count linear extensions of a 3-element V-shaped poset.
    
29. Meet/join in divisibility lattice for \(12\) and \(18\).
    
30. Explain Pareto front of two-objective optimization as an antichain.

Extended practice workshop

Hasse drawing practice (paper)

1. Divisors of \(60\) under \(\mid\)—draw Hasse; mark maximal/minimal.
   
2. \(\mathcal{P}(\{1,2,3\})\)—draw; identify a maximum chain; middle-level antichain.
   
3. Product order on \(\{1,2\}\times\{1,2,3\}\)—draw; find width and height roughly.

Topological orders

4. Dependency edges: build→test→deploy, lint→test, docs parallel to build. List \(\ge 3\) valid schedules.
   
5. Add a cycle docs→build→docs—explain impossibility.

Lattice checks

6. Is a total order a lattice? (Yes: min/max.)
   
7. Antichain of \(3\) elements with no extra bounds—lattice? (No.)
   
8. Add top and bottom to that antichain—now a lattice?

Proofs

9. Prove \(\subseteq\) antisymmetric on \(\mathcal{P}(X)\).
   
10. Prove product of posets is a poset.
    
11. Prove finite nonempty poset has a minimal element (dual of maximal).
    
12. If \(a\le b\) and \(b\le a\) then \(a=b\)—which axiom?

CS write-ups

13. Package versions: why “latest” may not be a maximum under constraint order.
    
14. Git commits with merges as a poset—not a total order.
    
15. Critical path = long chain in a task poset.

Glossary card

Term	One-line meaning
Poset	Set + \(\le\) REF+ANTI+TRANS
Hasse	Cover graph drawn upward
Chain	Totally ordered subset
Antichain	Pairwise incomparable subset
Linear extension	Topological total order
Meet/join	glb/lub of two elements

Quick theorems to recite

1. Finite nonempty poset has a maximal element.
   
2. At most one maximum (if it exists).
   
3. Topological order exists for every finite poset (acyclic strict order).
   
4. \((\mathcal{P}(X),\subseteq)\) is a bounded lattice with \(\cap,\cup\).
   
5. \((\mathbb{Z}^+,\mid)\) is a lattice with \(\gcd,\mathrm{lcm}\).
   
6. Product order is a poset; need not be total even if factors are.

Checkpoint recap (poset day)

• Draw one Hasse from a relation list
  
• Exhibit chain and antichain
  
• Distinguish maximal vs maximum
  
• Give two topo sorts of a small DAG
  
• Compute one meet and one join

Synthesis

Partial orders capture dependency without forcing a unique ranking. Hasse diagrams drop transitive edges so the eye sees covers; topological sorts reinsert a total order compatible with the poset—the algorithm side of finite DAGs. Maximal \(\neq\) maximum: local peaks vs global top.

Vocabulary drill

Term	Meaning
Comparable	\(a\le b\) or \(b\le a\)
Chain	totally ordered subset
Antichain	pairwise incomparable
Maximal	nothing strictly above
Maximum	\(\ge\) every element
Cover \(a\prec b\)	\(a<b\) and nothing between
Linear extension	total order refining \(\le\)

More worked examples

Example — Divisibility poset.
On \(\{1,2,3,4,6,12\}\) ordered by \(\mid\): Hasse connects \(1\) to primes/prime powers minimal, up to \(12\). Max element \(12\) (also maximum). Chain \(1\mid 2\mid 4\mid 12\); antichain \(\{2,3\}\).

Example — Subset lattice.
\((\mathcal{P}(\{a,b\}),\subseteq)\): bottom \(\emptyset\), top \(\{a,b\}\), middle antichain \(\{\{a\},\{b\}\}\). Meet \(=\cap\), join \(=\cup\).

Example — Topological orders.
Tasks \(A\to B\), \(A\to C\), \(B\to D\), \(C\to D\). Linear extensions include \(A,B,C,D\) and \(A,C,B,D\). Not \(B,A,\ldots\).

Example — Product order.
On \(\mathbb{N}\times\mathbb{N}\), \((a,b)\le(c,d)\) iff \(a\le c\) and \(b\le d\). \((1,4)\) and \((2,3)\) incomparable. Not a total order.

Example — Finite nonempty poset has a maximal element.
Proof idea: start at any \(x_0\); if not maximal climb; finite height/no infinite strict ascent ⇒ stop. (Or take a maximal chain.)

Extra exercises (synthesis)

31. Draw Hasse for \((\{1,2,3,4,5,6\},\mid)\).
    
32. Find all maximal elements of \(\{2,3,4,5,6\}\) under \(\mid\) (no \(1\)).
    
33. Prove: a poset has at most one maximum.
    
34. Give two different topological sorts of a \(5\)-element poset you invent.
    
35. In \((\mathcal{P}(\{1,2,3\}),\subseteq)\), find a chain of size \(4\) and an antichain of size \(3\).
    
36. Explain why package install order needs a linear extension of the dependency poset—and what cycles mean.

Orders vs equivalences (keep distinct)

	Equivalence	Partial order
SYM	yes	no (ANTI instead)
Picture	partition blocks	Hasse / DAG
CS	cluster, mod \(n\)	build order, types

Next: functions as structure-preserving maps between sets—not order maps yet, but the same \(\in\)-based proof style.

Tomorrow

Day 41 — Injections, surjections, bijections. Definitions; pigeon link; finite size comparisons; counting injections; inverse functions iff bijective.