Exercises: Partial Orders, Lattices, and Boolean Algebra

DataField.Dev

Exercises: Partial Orders, Lattices, and Boolean Algebra

These run from mechanical warm-ups to full proofs, code, modeling, and a flawed proof to repair. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the starred-with-a-dagger (†) and odd-numbered problems are in the appendix answers-to-selected.md — attempt them before you peek. For every poset, state the domain: divisibility is a partial order only on $\mathbb{Z}^{+}$.

Part A — Warm-ups (⭐)

13.1 † For each relation, state whether it is a partial order on the given set, and if not, name the first property (reflexive, antisymmetric, transitive) that fails: (a) $\le$ on $\mathbb{Z}$; (b) $<$ on $\mathbb{Z}$; (c) $\mid$ on $\mathbb{Z}^{+}$; (d) $\mid$ on $\mathbb{Z}$; (e) "$a$ and $b$ have the same parity" on $\mathbb{Z}$.

13.2 Draw the Hasse diagram of $(\mathcal{P}(\{a,b\}), \subseteq)$. Label every element, and mark the least and greatest elements.

13.3 † In the divisors-of-12 poset $(\{1,2,3,4,6,12\}, \mid)$ from §13.1: list (a) all elements comparable to 4; (b) all elements incomparable to 4; (c) every maximal element; (d) the greatest element, if one exists.

13.4 Define "$a$ covers $b$" in your own words, then list all covering pairs of $(\{1,2,3,6\}, \mid)$. Which covering pairs would the digraph of the full relation $\mid$ include that the Hasse diagram omits?

13.5 † For the poset $(\{1,2,4,8\}, \mid)$: is it a total order? Give the longest chain and the largest antichain.

13.6 Using the lattice dictionary from §13.4, compute in $(\mathbb{Z}^{+}, \mid)$: (a) $6 \vee 10$; (b) $6 \wedge 10$; (c) $7 \vee 21$; (d) $7 \wedge 21$.

Part B — Prove it (⭐⭐)

13.7 † (Scaffolded — fill in the missing steps.) Prove that $(\mathbb{Z}^{+}, \mid)$ is a partial order. Recall (Chapter 4) that $a \mid b$ means there is an integer $k$ with $b = ak$.

Reflexive: for any $a \in \mathbb{Z}^{+}$, $a = a \cdot \underline{\hphantom{xx}}$, so $a \mid a$.
Antisymmetric: suppose $a \mid b$ and $b \mid a$, so $b = ak$ and $a = b\ell$ for positive integers $k, \ell$. Substituting, $a = (ak)\ell = a(k\ell)$, hence $k\ell = \underline{\hphantom{xx}}$. Since $k, \ell$ are positive integers, this forces $k = \ell = \underline{\hphantom{xx}}$, so $b = a \cdot \underline{\hphantom{xx}} = a$.
Transitive: suppose $a \mid b$ and $b \mid c$, so $b = ak$ and $c = bm$. Then $c = \underline{\hphantom{xxxx}}$, which shows $a \mid c$.

13.8 Prove that in any poset, a greatest element, if it exists, is unique. (Mirror the uniqueness-of-join proof from §13.4: assume two greatest elements and use antisymmetry.)

13.9 † Prove that in any poset, every greatest element is maximal. Then give a poset with a maximal element that is not greatest, and explain which step of "maximal $\Rightarrow$ greatest" fails for it.

13.10 Prove that the meet $a \wedge b$, when it exists, is unique. State precisely where antisymmetry is used.

13.11 † Prove by the laws of Boolean algebra (not a truth table) that $a \wedge (a \vee b) = a$ (the dual absorption law). Then state which law of §13.5 lets you assert the $\vee$-form $a \vee (a \wedge b) = a$ for free, without a second proof.

13.12 Prove that in a total order, the join of any two elements is $\max(a,b)$ and the meet is $\min(a,b)$ — hence every total order is a lattice. (Use the definition: show $\max(a,b)$ satisfies the three lub conditions.)

13.13 † (Deep Dive, from §13.4's prompt.) Prove that the divisibility poset $(\{1, 2, \dots, n\}, \mid)$ on the first $n$ positive integers has a meet for every pair, equal to $\gcd(a,b)$. (Why is the join not guaranteed to stay inside this set? Give a smallest counterexample.)

Part C — Implement it (⭐⭐)

Write Python for each. Do not run it on the grader's machine — hand-trace and include an # Expected output: comment, matching the book's convention. Represent a partial order either as a set of (a, b) pairs meaning $a \preceq b$, or as a DAG {node: [successors]}, as the problem requires.

13.14 † Write is_partial_order(pairs, elements) that returns True exactly when the relation given by pairs (a set of (a, b) meaning $a \preceq b$) is reflexive, antisymmetric, and transitive on elements. Test it on the divisibility relation for $\{1,2,3,6\}$ (should be True) and on $\{(1,2),(2,1)\}$ over $\{1,2\}$ (should be False — why?).

13.15 Write is_chain(subset, pairs) that returns True when every two elements of subset are comparable under the order pairs. Use it to confirm $\{1,2,4,12\}$ is a chain in the divisors-of-12 poset and $\{4,6\}$ is not.

13.16 † Write maximal_elements(pairs, elements) returning the set of elements with nothing strictly above them. Run it (by hand) on the divisors-of-12 poset; then on the "X" poset $\{(a,c),(a,d),(b,c),(b,d)\}$ over $\{a,b,c,d\}$, and report both maximal and minimal elements.

13.17 Write is_lattice(pairs, elements) that returns True when every pair of elements has a unique least upper bound and a unique greatest lower bound. (Compute, for each pair, the set of upper bounds, then check whether that set has a least element.) Confirm it returns False on the "X" poset.

Part D — Find the error (⭐⭐)

13.18 † A student claims: "Every poset has a greatest element, because it certainly has a maximal element, and a maximal element is one that nothing is above — which is exactly what 'greatest' means." The conclusion is false. Identify the precise confusion, and give the smallest poset that refutes the claim.

13.19 Claim: "$(\mathbb{Z}, \mid)$ is a poset." "Proof": "Divisibility is reflexive ($a \mid a$), transitive (if $a \mid b$ and $b \mid c$ then $a \mid c$), and antisymmetric (if $a \mid b$ and $b \mid a$ then $a = b$). All three hold, so it's a partial order. ∎" Find the flaw, give an explicit counterexample, and state the corrected domain.

13.20 † (Find the error in a topological-sort argument.) A student writes: "Topological sort works on any finite relation that is transitive: repeatedly output a minimal element and delete it. Since the relation is transitive, a minimal element always exists, so the process never gets stuck." Exhibit a transitive relation on a finite set for which no minimal element exists, and name the missing hypothesis that the chapter's Lemma actually requires.

13.21 Claim (absorption "proof"): "$a \vee (a \wedge b) = a \vee a \wedge b = a \wedge b$ (because $a \vee a = a$ by idempotence)." Both the reasoning and the result are wrong. Diagnose the error (think about what idempotence actually says and about operator grouping), then write the correct derivation from §13.5.

Part E — Model it (⭐⭐⭐)

13.22 † (Model it.) A small build has these constraints: config.h must be processed before db.o and before net.o; db.o and net.o must both precede server; log.o must precede server; log.o has no other constraints. (a) Model this as a poset by listing the covering pairs and sketching the Hasse diagram. (b) Identify the minimal and maximal elements. (c) Give two distinct topological sorts. (d) What is the longest chain (the critical path), and what does its length mean for a build with unlimited parallel workers?

13.23 (Model it — type lattices.) A toy language has types ordered by the subtype relation $\preceq$ ("is a subtype of"), with Never $\preceq$ everything and everything $\preceq$ Any. Suppose int $\preceq$ number, float $\preceq$ number, and number $\preceq$ Any, with int and float incomparable. (a) Draw the Hasse diagram. (b) The compiler types cond ? x : y (an int x and a float y) as the join of their types. What type does it infer, and why is the join the right operation? (c) Is this poset a lattice? Justify by checking that every pair has a join and a meet.

13.24 † (Model it — access control.) Security clearances form the chain Public $\prec$ Confidential $\prec$ Secret $\prec$ TopSecret, and a document tagged with a set of compartments (say subsets of $\{\text{NUCLEAR}, \text{CRYPTO}\}$). A subject may read a document iff the subject's clearance $\succeq$ the document's level and the subject's compartment set $\supseteq$ the document's compartments. (a) Explain why the pair (level, compartment-set) is ordered by a product of two posets, and state that product order precisely. (b) Is the result a lattice? What are the join and meet of two (level, compartments) labels? (This is the Bell–LaPadula model in lattice form.)

Part F — Conjecture and test (⭐⭐⭐)

13.25 † (Conjecture and test, then prove.) For the "Boolean cube" poset $(\mathcal{P}(\{1,\dots,n\}), \subseteq)$: write code that, for $n = 1, 2, 3, 4$, computes the size of the largest antichain (a set of subsets, none containing another). Tabulate your four numbers and conjecture a closed form. You do not have to prove it in general (it is Sperner's theorem), but state precisely what you conjectured. (Hint: count the subsets of one "middle" size; the answer for each $n$ turns out to be a single binomial coefficient — the counting tool you will formalize in Chapter 16.)

13.26 (Conjecture and test.) Write code to count the number of distinct topological sorts (linear extensions) of a poset given as a DAG, by brute force over permutations. Run it (by hand-trace or by reasoning) on (a) a 3-element chain, (b) a 3-element antichain, (c) the divisors-of-12 poset. Conjecture: for which posets is the count exactly 1? Prove your conjecture in one or two sentences (connect to §13.3's "a topological sort is unique iff …").

13.27 † (Conjecture and test.) In $(\mathbb{Z}^{+}, \mid)$, define $f(a,b) = (a \vee b) \wedge (a \wedge b)$ using $\operatorname{lcm}$ and $\gcd$. Compute $f(a,b)$ for ten pairs of your choice, conjecture a simple formula for $f(a,b)$ in terms of $a$ and $b$ alone, and prove it from the identity $\gcd(a,b)\cdot\operatorname{lcm}(a,b) = ab$ (which you will meet again in Chapter 22).

Part G — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp.

13.28 † (Ch. 12 + 13.) The relation "$\subseteq$" is a partial order, and "has the same cardinality as" is an equivalence relation. For each of reflexive, symmetric, antisymmetric, transitive, say which of the two relations has it. In one sentence, state the single property whose presence or absence separates "partial order" from "equivalence relation."

13.29 (Ch. 1 + 13.) In Chapter 1 you verified De Morgan's law with a truth table. Restate $\neg(p \land q) \equiv \neg p \lor \neg q$ in the Boolean-algebra notation of §13.5, then explain in two sentences what the truth table did and what the algebraic law lets you do that the table does not.

13.30 † (Ch. 8 + 13.) Prove that for any finite set $S$, the Boolean algebra $(\mathcal{P}(S), \subseteq)$ has $2^{\lvert S\rvert}$ elements, and identify its bottom $0$, top $1$, and the complement operation $\overline{A}$. (You may cite the subset-count result from Chapter 8.)

13.31 (Ch. 11 + 13.) The longest_chain code in §13.2 fills a table and reuses subresults. If computing each of $n$ entries scans up to $n$ predecessors, write the total work as a summation, give its closed form, and state the Big-O. (This previews the asymptotic language of Chapter 14.)

13.32 † (Ch. 7 + 13, Deep Dive.) The chapter's Lemma ("every finite nonempty poset has a minimal element") was proved by ruling out an infinite descending chain. Restate the underlying principle as a property of $\mathbb{N}$ from Chapter 7, and explain in two sentences why "no infinite descending chain" is exactly what makes the topo_sort while loop terminate.

13.33 (Deep Dive — from the chapter's §13.5 prompt.) Prove that every finite Boolean algebra has size a power of two. You may use the fact (provable, but you may assume it) that every finite Boolean algebra is isomorphic to $(\mathcal{P}(S), \subseteq)$ for some finite set $S$ of "atoms." Combine this with Exercise 13.30.

13.34 (Deep Dive — duality.) State the principle of duality for Boolean algebra precisely (what transformation, and what it guarantees). Then use it to write down, with no separate proof, the dual of each of: the domination law $a \vee 1 = 1$; the absorption law $a \vee (a \wedge b) = a$; and the complement law $a \vee \overline{a} = 1$.

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each proof, the rubric rewards: a clearly stated claim and domain, explicit use of the right property (antisymmetry for uniqueness; minimal-element existence for topological sort), correct use of a named Boolean law per step, and a clean conclusion. For each "implement it," the rubric rewards a correct # Expected output: derived by hand and code whose structure mirrors the definition it computes.