Key Concepts of Hasse Diagrams

Why This Matters

Hasse diagrams are the visual language of lattice theory. They transform abstract order relations into pictures you can actually analyze. When you're working with partially ordered sets, these diagrams let you immediately spot structural features like minimal elements, maximal elements, bounds, chains, and antichains without wading through formal definitions.

The real power of Hasse diagrams lies in what they reveal about lattice structure. Whether you're identifying whether a poset forms a lattice, checking for distributivity, or analyzing Boolean algebras, the diagram tells the story. Don't just memorize how to draw these diagrams. Know what each visual feature represents and how to use it to answer questions about suprema, infima, covering relations, and duality.

---

Foundational Structure: Building the Diagram

These diagrams show only the essential ordering information. Everything else can be inferred from transitivity.

Definition and Basic Properties

• Vertices represent elements of a finite partially ordered set (poset), with edges showing the order relation between them.
• Vertical positioning encodes order. If $a < b$, then $a$ appears lower than $b$ in the diagram.
• Transitive edges are omitted. If $a < b < c$, only edges $a \text{---} b$ and $b \text{---} c$ appear, not $a \text{---} c$. You recover that $a < c$ by following the path through $b$.

Covering Relations

The covering relation is the backbone of every Hasse diagram. Element $b$ covers element $a$ (written $a \lessdot b$) when $a < b$ and no element $c$ exists with $a < c < b$. In other words, $b$ is the immediate successor of $a$ with nothing squeezed in between.

Every line segment in a Hasse diagram corresponds to exactly one covering relation. So reading the diagram means following chains of covers: two elements are comparable if and only if a path of edges connects them vertically.

Representation of Partial Orders

A partial order on a set satisfies three axioms:

1. Reflexive: $a \leq a$ for every element $a$
2. Antisymmetric: if $a \leq b$ and $b \leq a$, then $a = b$
3. Transitive: if $a \leq b$ and $b \leq c$, then $a \leq c$

The diagram simplifies things by omitting reflexive loops (every element is trivially related to itself) and transitive edges (you can deduce them by following paths). Two elements are comparable precisely when one lies above the other along some sequence of edges.

---

Extremal Elements: Finding the Boundaries

Identifying special elements in a poset is one of the most common diagram-reading tasks. The visual structure makes extremal elements immediately apparent: they sit at the edges of the diagram.

Minimal and Maximal Elements

• Minimal elements have no elements below them. They appear at the bottom of the diagram with no downward edges.
• Maximal elements have no elements above them. They sit at the top with no upward edges.
• Multiple extrema are possible. A poset can have several minimal or maximal elements, unlike least/greatest elements, which must be unique if they exist.

Least Upper Bounds (Suprema) and Greatest Lower Bounds (Infima)

The supremum (or join) of a set is the smallest element that is greater than or equal to every element in that set. For two elements, this is written $a \vee b$. The infimum (or meet) is the largest element that is less than or equal to every element in the set, written $a \wedge b$.

Bounds may not exist in a general poset. Two elements might lack a supremum or infimum entirely. This is exactly what distinguishes lattices from arbitrary posets.

To find $a \vee b$ on a diagram, trace upward from both $a$ and $b$ and look for the lowest element that lies above both. For $a \wedge b$, trace downward and find the highest element that lies below both.

---

Substructures: Chains and Antichains

Understanding how elements relate to each other in groups reveals the internal geometry of a poset.

Chains and Antichains

A chain is a totally ordered subset: every pair of elements in the chain is comparable. On the diagram, a chain appears as a vertical path of connected edges.

An antichain is a set of mutually incomparable elements: no two elements in an antichain have a path between them. These tend to appear as elements spread horizontally at similar levels in the diagram.

Dilworth's theorem connects the two: the minimum number of chains needed to partition (cover) a finite poset equals the size of its maximum antichain. This is a deep structural result, not just a counting trick.

The height of a poset is the length of its longest chain (counted as the number of edges, so a chain of $k$ elements has length $k - 1$). The width is the size of its largest antichain.

---

Lattice Properties: When Structure Gets Special

A poset becomes a lattice when every pair of elements has both a supremum and an infimum. Lattices have predictable, well-behaved structure that Hasse diagrams reveal clearly.

Lattices and Their Representation

The defining property: every pair of elements has a unique join and a unique meet. If any pair lacks a supremum or infimum, the poset is not a lattice.

To visually test for lattice structure, pick any two elements. Trace upward to find where their upper bounds first converge to a single least element (that's the join). Trace downward to find where their lower bounds last converge to a single greatest element (that's the meet). If you ever find a pair where this fails, you don't have a lattice.

A bounded lattice has both a greatest element (often written $1$) and a least element (often written $0$) that bound all other elements from above and below, respectively.

Distributive Lattices

Distributivity means join distributes over meet and vice versa:

$a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$

and the dual identity:

$a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)$

There's a clean visual criterion. A finite lattice is distributive if and only if it contains no sublattice isomorphic to $N_5$ (the pentagon lattice) or $M_3$ (the diamond lattice). So when checking distributivity on a diagram, look for these two forbidden configurations. If neither appears as a sublattice, the lattice is distributive.

Distributive lattices model propositional logic, set operations under union and intersection, and divisibility relations on natural numbers.

Boolean Algebras

A Boolean algebra is a complemented distributive lattice. That means it's distributive and every element $a$ has a complement $a'$ satisfying:

$a \vee a' = 1 \quad \text{and} \quad a \wedge a' = 0$

On a Hasse diagram, Boolean algebras on $n$ generators have $2^n$ elements and their diagrams form $n$-dimensional hypercubes. The Boolean algebra on 1 generator is just a two-element chain. On 2 generators, you get a square (the 2-cube). On 3 generators, you get the familiar 3-dimensional cube with 8 elements.

The canonical example is the power set lattice $\mathcal{P}(S)$ ordered by inclusion, where the complement of a subset $A$ is $S \setminus A$.

---

Structural Principles: Duality and Symmetry

The duality principle is one of lattice theory's most powerful tools. It doubles your theorems for free: every statement about a poset has a dual obtained by reversing the order relation.

Duality Principle

To form the dual, flip the diagram upside down. This reverses all order relations, swapping $\leq$ for $\geq$. Concretely:

• Minimal elements become maximal, and vice versa
• Infima become suprema, and vice versa
• Chains remain chains (just reversed in direction)
• Antichains stay antichains (incomparability doesn't depend on direction)

Any theorem you prove about meets automatically gives you a dual theorem about joins. Any result about least elements dualizes to a result about greatest elements.

A poset is self-dual if it's isomorphic to its own dual. Boolean algebras are self-dual, which is one reason their diagrams look so symmetric.

---

Quick Reference Table

---

Self-Check Questions

1. Given a Hasse diagram, how do you determine whether two elements are comparable, and what visual feature tells you one element covers another?

2. What distinguishes a minimal element from a least element, and can a poset have multiple of each?

3. Compare the conditions for a poset to be a lattice versus a distributive lattice. What additional constraint does distributivity impose, and how can you detect its failure visually?

4. If you flip a Hasse diagram upside down, what happens to the supremum of two elements? What about chains and antichains?

5. Explain why every Boolean algebra is a distributive lattice but not every distributive lattice is a Boolean algebra. What structural feature must be present for a distributive lattice to qualify as Boolean?