Information Technology is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Partial orders, Hasse diagrams and lattices

Notes on partial orders, Hasse diagrams and lattices: definitions, laws, how to draw and recognise Hasse diagrams, lattice properties (meet/join), worked examples and typical exam questions.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Partial orders and lattices give a rigorous way to compare items when 'greater' is not numeric: engineers use them in type systems, dependency analysis, task scheduling, design hierarchies, data-flow frameworks and circuit simplification. Hasse diagrams are a compact visual tool to show ordering and to spot bounds, chains, antichains and lattice structure.

Key ideas

Start from first principles and simple definitions.

  • Binary relation: a set R of ordered pairs on a set A, R ⊆ A×A. Use this term before talking about orders.
  • Partial order: a binary relation ≤ on A that is reflexive, antisymmetric and transitive. Formally: for all a,b,c ∈ A,
    • reflexive: a ≤ a;
    • antisymmetric: if a ≤ b and b ≤ a then a = b;
    • transitive: if a ≤ b and b ≤ c then a ≤ c. A set A with a partial order ≤ is called a partially ordered set or poset; write (A, ≤). We write a < b to mean a ≤ b and a ≠ b (the associated strict order).
  • Comparability and incomparability: two elements a,b are comparable if a ≤ b or b ≤ a; otherwise they are incomparable, written a ∥ b.
  • Cover relation: in a poset (A, ≤), we say b covers a (write a ≺ b) when a < b and there is no c with a < c < b. Covers are the edges drawn in a Hasse diagram.
  • Hasse diagram: a drawing of a finite poset using points for elements and upward edges for covers. Draw no loops (omit reflexive edges) and omit edges implied by transitivity (do not draw transitive edges). Place greater elements above smaller ones. Label each vertex with the element.
  • Chain: a subset C ⊆ A such that every two elements of C are comparable. A chain is a totally ordered subset.
  • Antichain: a subset S ⊆ A where no two distinct elements are comparable.
  • Minimal and maximal elements: an element m ∈ A is minimal if there is no x ∈ A with x < m. m is maximal if there is no x ∈ A with m < x. These need not be unique.
  • Least (minimum) and greatest (maximum) elements: l ∈ A is a least element if l ≤ a for all a ∈ A (unique if exists). g ∈ A is greatest if a ≤ g for all a ∈ A (unique if exists).
    • Theorem (uniqueness): A least element (if exists) is unique. Proof: if l and l' are least, then l ≤ l' and l' ≤ l so by antisymmetry l = l'.
  • Upper bound and least upper bound (join / supremum): For S ⊆ A, u ∈ A is an upper bound of S if s ≤ u for all s ∈ S. The least upper bound (if exists) is the smallest of all upper bounds (hence unique) and is called supremum or join when S = {a,b}; denote sup{a,b} = a ∨ b.
  • Lower bound and greatest lower bound (meet / infimum): For S ⊆ A, l ∈ A is a lower bound if l ≤ s for all s ∈ S. The greatest lower bound is the largest lower bound (hence unique); for two elements denote inf{a,b} = a ∧ b.
  • Lattice: a poset (L, ≤) in which every pair of elements a,b ∈ L has both a meet (a ∧ b) and a join (a ∨ b). Equivalently, binary operations ∧ and ∨ on L that satisfy certain laws (below) and are connected to ≤ by: a ≤ b iff a ∨ b = b (or iff a ∧ b = a).

Important algebraic laws for ∧ and ∨ in any lattice (for all a,b,c ∈ L):

  • Commutative: a ∨ b = b ∨ a; a ∧ b = b ∧ a.
  • Associative: (a ∨ b) ∨ c = a ∨ (b ∨ c); (a ∧ b) ∧ c = a ∧ (b ∧ c).
  • Idempotent: a ∨ a = a; a ∧ a = a.
  • Absorption: a ∨ (a ∧ b) = a; a ∧ (a ∨ b) = a.

Special lattices:

  • Distributive lattice: ∧ distributes over ∨ and vice versa: a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) (and dually). Not every lattice is distributive.
  • Modular lattice: weaker than distributive: whenever a ≤ c, a ∨ (b ∧ c) = (a ∨ b) ∧ c.
  • Bounded lattice: has a least element 0 and a greatest element 1.
  • Complemented lattice: bounded lattice where each a has some b with a ∧ b = 0 and a ∨ b = 1. If complemented and distributive, it is a Boolean algebra (see Boolean algebra topic for full treatment).

How to draw a Hasse diagram (exact steps to describe in an exam):

  1. List the elements of the finite poset.
  2. Determine the order and find cover relations (pairs (x,y) with x < y and no z in between).
  3. Place minimal elements at the bottom and maximal at the top; place others between, keeping covers as upward lines.
  4. Draw an unlabeled up-edge between two elements exactly when one covers the other. Label each node with the element value.
  5. Do not draw transitive edges or loops.

Common derivations universities ask for: prove uniqueness of least/greatest, show absorption laws follow from order definitions, or prove that lattice axioms imply order and vice versa for finite lattices (in fact, this equivalence holds for any lattice, not only finite ones).

Formulas

a ≤ a — reflexivity; a is any element of the poset; unit: none; applies in any poset.

(a ≤ b ∧ b ≤ a) ⇒ a = b — antisymmetry; a,b elements; unit: none; applies in any poset.

(a ≤ b ∧ b ≤ c) ⇒ a ≤ c — transitivity; a,b,c elements; unit: none; applies in any poset.

a ∨ b = sup{a,b} — join; a,b ∈ L; unit: none; applies in lattices where sup exists.

a ∧ b = inf{a,b} — meet; a,b ∈ L; unit: none; applies in lattices where inf exists.

a ∨ (a ∧ b) = a — absorption law; a,b ∈ L; unit: none; applies in any lattice.

a ∧ (a ∨ b) = a — absorption law; a,b ∈ L; unit: none; applies in any lattice.

a ∨ b = b ∨ a and a ∧ b = b ∧ a — commutativity; unit: none; applies in any lattice.

a ∨ (b ∨ c) = (a ∨ b) ∨ c and a ∧ (b ∧ c) = (a ∧ b) ∧ c — associativity; unit: none; applies in any lattice.

a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) — distributive law; a,b,c ∈ L; unit: none; applies only in distributive lattices. Dually, a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) — applies only in distributive lattices.

Worked examples

Example 1 — Power set lattice (exam-style answer): Question: Let A = {1,2}. Consider P(A) = {∅, {1}, {2}, {1,2}} ordered by ⊆. Draw the Hasse diagram, and find meet and join of {1} and {2}. Answer steps:

  1. List elements and the order: ∅ ⊆ {1}, ∅ ⊆ {2}, {1} ⊆ {1,2}, {2} ⊆ {1,2}. No other subset relations.
  2. Cover relations: ∅ ≺ {1}, ∅ ≺ {2}, {1} ≺ {1,2}, {2} ≺ {1,2}.
  3. Hasse diagram (describe what to draw): place ∅ at bottom, {1} and {2} on the next level (separate, not joined), and {1,2} at top. Draw upward edges from ∅ to {1} and ∅ to {2}; edges from {1} to {1,2} and {2} to {1,2}. Label nodes accordingly.
  4. Meet (intersection): {1} ∧ {2} = {1} ∩ {2} = ∅. Join (union): {1} ∨ {2} = {1} ∪ {2} = {1,2}. Final: Meet = ∅, Join = {1,2}.

Example 2 — Divisibility poset and checking lattice property: Question: Let S = {1,2,3,6} with order a | b (divides). Draw Hasse diagram, list minimal/maximal elements, and check whether S is a lattice. Answer steps:

  1. Compute divisibility relations: 1 divides all; 2|6 and 3|6; 2 and 3 do not divide each other.
  2. Covers: 1 ≺ 2, 1 ≺ 3, 2 ≺ 6, 3 ≺ 6 (1 ≺ 6 is not a cover because 1<2<6 etc). So Hasse: 1 at bottom, 2 and 3 above it (incomparable), 6 at top with edges from 2 and 3.
  3. Minimal element: 1 (also least element because 1 divides every element). Maximal element: 6 (greatest because every element divides 6). Minimal and least coincide; also maximal and greatest coincide and are unique.
  4. For any pair: meet = gcd, join = lcm restricted to S. Pairs: gcd(2,3)=1 ∈ S, lcm(2,3)=6 ∈ S. So every pair has meet and join in S; hence S is a lattice. Provide one explicit computation: 2 ∧ 3 = 1, 2 ∨ 3 = 6. Final: S is a lattice; Hasse diagram as described.

Example 3 — A poset that is not a lattice (model answer): Question: Let P = {a,b,c} with order a < b and a < c, and b and c incomparable. Does P form a lattice? Answer steps:

  1. Covers: a ≺ b and a ≺ c. Hasse diagram: a at bottom with two upward edges to b and c.
  2. For b and c, upper bounds are elements x with b ≤ x and c ≤ x. The only candidates in P are b and c themselves, but neither b nor c is ≥ the other, so there is no common upper bound in P. So sup{b,c} does not exist. Conclusion: P is not a lattice. Show explicitly: no b ∨ c exists in P.

Common mistakes

  • When drawing Hasse diagrams, drawing transitive edges (e.g., drawing an edge from a to c when a < b < c) — this is wrong for Hasse diagrams.
  • Forgetting antisymmetry: if a ≤ b and b ≤ a then a = b. Some students treat ≤ like a symmetric relation.
  • Incorrectly assuming every finite poset is a lattice. Counterexample: 3-element poset with one bottom and two incomparable elements above.
  • Mixing up meet/join with arithmetic min/max: only when order is numeric.

For your exam

Typical question types:

  • Definitions (define poset, chain, antichain, Hasse diagram, lattice, meet/join).
  • Draw Hasse diagram for a given finite poset; label covers and identify minimal/maximal elements.
  • Prove a short theorem: uniqueness of least element; absorption laws from lattice order; show equivalence between order definition and algebraic operations.
  • Construct examples: give a poset that is not a lattice, or prove a given poset is a lattice and compute meets/joins.
  • Short derivations: show distributive ⇒ modular, or give counterexample to converse.

What full-marks answers include:

  • Precise definitions with bolded names in the answer (poset, lattice etc.).
  • Correct drawing instructions and a clear Hasse diagram (nodes labelled, edges only for covers, minimal at bottom).
  • Step-by-step argument for proofs, stating which property (reflexive/antisymmetric/transitive) is used at each step.
  • For examples, explicit computation of bounds and correct statement whether meet/join exists.

Quick check

  1. Define a Hasse diagram in one line.
  2. In a lattice, what is a ∧ b when the order is set-inclusion on subsets? Give the operation name.
  3. True/False: every finite poset has a least element. Answers: 1. A Hasse diagram is a drawing of a finite poset using points for elements and upward edges only for cover relations, omitting loops and transitive edges. 2. a ∧ b = intersection (meet). 3. False (finite posets may have multiple minimal elements but no single least element).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?