Partial orders, Hasse diagrams, and lattices (intro)

Problem 1 (CONCEPTUAL)

Explain why the relation "is a proper subset of" (⊂) on a set 𝒫(S) is not a partial order, while "is a subset of" (⊆) is. Which axiom fails, and why does it matter for Hasse diagram construction?

Answer: The relation ⊂ (proper subset) fails reflexivity because A ⊄ A for any set A. A partial order requires a ≤ a for all elements. In contrast, ⊆ satisfies reflexivity (A ⊆ A), antisymmetry (A ⊆ B and B ⊆ A implies A = B), and transitivity (A ⊆ B and B ⊆ C implies A ⊆ C). This matters because Hasse diagrams are defined specifically for partial orders; the covering relation used to draw edges depends on the underlying ≤ being reflexive. However, ⊂ is a strict partial order (irreflexive, asymmetric, transitive), and it gives rise to the same Hasse diagram as ⊆ since the diagrams omit self-loops anyway. The distinction is technically important even though the visual output is identical.

---

Problem 2 (BASIC CALCULATION)

Consider the poset ({1, 2, 4, 8}, |) where | denotes divisibility. List all covering relations and determine whether this poset is a lattice. If so, compute 2 ∨ 4 and 4 ∧ 8.

Answer: The covering relations are: 1 ≺ 2, 2 ≺ 4, 4 ≺ 8. This forms a simple chain (total order), so it is trivially a lattice—in fact, every total order is a lattice. The join of any two elements is their maximum, and the meet is their minimum. Therefore, 2 ∨ 4 = max(2, 4) = 4 (equivalently, lcm(2, 4) = 4), and 4 ∧ 8 = min(4, 8) = 4 (equivalently, gcd(4, 8) = 4). Since every pair is comparable, the Hasse diagram is a vertical chain: 1 — 2 — 4 — 8.

---

Problem 3 (INTERMEDIATE)

Draw the Hasse diagram for the poset (𝒫({1, 2}), ⊆) and verify the lattice property by computing the join and meet for every pair of elements. Identify the top and bottom elements.

Answer: The set 𝒫({1, 2}) = {∅, {1}, {2}, {1, 2}} has four elements. The covering relations are: ∅ ≺ {1}, ∅ ≺ {2}, {1} ≺ {1,2}, {2} ≺ {1,2}. The Hasse diagram forms a diamond shape with ∅ at the bottom and {1,2} at the top. There are C(4,2) = 6 pairs to check. The critical pair is ({1}, {2}): their join is {1} ∪ {2} = {1,2}, and their meet is {1} ∩ {2} = ∅. All other pairs involve comparable elements, so their join is the larger and their meet is the smaller. Since every pair has both a join and a meet, this is a lattice. The bottom element is ⊥ = ∅ and the top element is ⊤ = {1, 2}. This is also a Boolean algebra B₂ since every element has a complement ({1} and {2} are complements of each other).

---

Problem 4 (APPLIED)

In a software build system, source files have dependencies: file A depends on file B means B must be compiled before A. Suppose we have files {main, util, io, config, logger} with dependencies: main depends on util and io; util depends on config; io depends on config and logger. Model this as a poset under the "must be compiled before" relation. Draw the Hasse diagram and identify which files can be compiled in parallel.

Answer: Define a ≤ b to mean "a must be compiled before b" (or a = b). The covering relations are: config ≺ util, config ≺ io, logger ≺ io, util ≺ main, io ≺ main. The Hasse diagram has three levels: level 0 contains {config, logger} (no dependencies), level 1 contains {util, io}, and level 2 contains {main}. Files that can be compiled in parallel are those that are incomparable in the poset. At level 0, config and logger are incomparable and can compile in parallel. At level 1, util and io are incomparable (util does not depend on io, nor vice versa), so after their dependencies are resolved, they too can compile in parallel. This poset is not a lattice: config and logger have two minimal upper bounds (util and io) but no unique least upper bound, since neither util ≤ io nor io ≤ util. The poset has no single top element other than main, but the pair {config, logger} lacks a unique join.

---

Problem 5 (CRITICAL THINKING)

Prove or disprove: every finite lattice with n elements has a unique maximum and a unique minimum element. Then determine whether the converse holds: does every finite poset with a unique maximum and a unique minimum necessarily form a lattice?

Answer: The first claim is true. Let (L, ≤) be a finite lattice with elements a₁, a₂, …, aₙ. Consider the join a₁ ∨ a₂ ∨ ⋯ ∨ aₙ, computed by associativity of the binary join (which exists by the lattice property). This iterated join is an upper bound of every element and is the least such, so it is the unique maximum ⊤. Dually, the iterated meet a₁ ∧ a₂ ∧ ⋯ ∧ aₙ is the unique minimum ⊥. The converse, however, is false. Consider the poset with elements {0, a, b, c, 1} where 0 ≤ a, 0 ≤ b, 0 ≤ c, a ≤ 1, b ≤ 1, c ≤ 1, a ≤ c, b ≤ c, and no other non-trivial relations. This poset has unique minimum 0 and unique maximum 1. However, a ∨ b = c (since c is the least upper bound of a and b), and this works. But if instead we modify the example to have 0 ≤ a, 0 ≤ b, a ≤ c, a ≤ d, b ≤ c, b ≤ d, c ≤ 1, d ≤ 1, then a ∨ b does not exist because c and d are both minimal upper bounds of {a, b} yet are incomparable. The poset has ⊥ = 0 and ⊤ = 1, but it fails the lattice property.