4.4 Partial Orders and Hasse Diagrams

Equivalence relations use symmetry to group peers. Many systems need a different structure: one task must happen before another, one set is contained in another, or one number divides another.

These connections have direction, but not every pair needs to be comparable. A project can contain two independent tasks. Two sets may each contain an element missing from the other. The correct model is a partial order.

Partial orders combine three familiar properties

A relation $\preceq$ on a set $A$ is a partial order when it is:

1. reflexive: $a\preceq a$ for every $a\in A$;

2. antisymmetric: $a\preceq b$ and $b\preceq a$ imply $a=b$;

3. transitive: $a\preceq b$ and $b\preceq c$ imply $a\preceq c$.

The pair

is called a partially ordered set, often shortened to poset.

The symbol $\preceq$ is a generic order symbol. A specific poset may use $\le$, $\subseteq$, divisibility $\mid$, or a task-dependency relation.

Compare the formulas for equivalence and partial order:

Symmetry allows distinct equivalent elements to point both ways. Antisymmetry says that if an order runs both ways, the two elements must actually be the same.

Three central examples

Numerical order

The usual $\le$ relation on integers is a partial order:

• $a\le a$;

• $a\le b$ and $b\le a$ imply $a=b$;

• $a\le b$ and $b\le c$ imply $a\le c$.

Every two integers are comparable under $\le$, making this a special partial order called a total order.

Set inclusion

On the power set $\mathcal P(S)$, the relation $\subseteq$ is a partial order:

and

Not every pair is comparable. If

then neither $X\subseteq Y$ nor $Y\subseteq X$.

Divisibility

On the positive divisors of a fixed positive integer, define

This relation is reflexive because $a=a\cdot1$, antisymmetric on positive integers, and transitive because

mean $b=ak$ and $c=b\ell$, so

which proves $a\mid c$.

Comparable and incomparable elements

In a poset $(A,\preceq)$, elements $a$ and $b$ are comparable if

They are incomparable when neither statement holds.

Incomparability does not mean that the relation is broken. It is the feature that makes an order partial instead of total.

Imagine software tasks:

• schema must finish before API;

• API must finish before dashboard;

• icons must finish before dashboard.

Transitivity implies schema precedes dashboard. But schema and icons may be incomparable: neither depends on the other, so they can proceed in parallel.

It is useful to distinguish the non-strict order $\preceq$ from its associated strict order $\prec$:

The non-strict relation includes self-relations; the strict relation does not.

Schedule a launch project by wiring prerequisite tasks. The simulator propagates indirect dependencies, flags cycles that violate antisymmetry, and places independent tasks in parallel lanes. You must repair a feasible order rather than merely sort labels.

Why a Hasse diagram is not the full relation graph

A finite poset can be drawn as a directed graph, but that graph contains redundant information:

• reflexivity creates a loop at every vertex;

• transitivity creates an edge for every indirect comparison;

• arrowheads all point in the same upward order direction.

A Hasse diagram removes this redundancy.

For a finite poset $(A,\preceq)$:

1. remove every loop $a\preceq a$;

2. remove every edge implied by a longer transitive path;

3. place smaller elements lower and larger elements higher;

4. omit arrowheads because upward direction carries the meaning.

The edges that remain represent the cover relation. We say $b$ covers $a$ when

and there is no $c$ with

In other words, $b$ is immediately above $a$ with no intermediate poset element between them.

Worked example: divisibility among divisors of $12$

Let

ordered by divisibility.

The full relation includes, among many others,

However, the edge from $1$ to $4$ is transitive because

Likewise, $1$ to $12$, $2$ to $12$, and $3$ to $12$ can be inferred through intermediate divisors.

The cover pairs are

A text layout of the Hasse diagram is:

          12
         /  \
        4    6
        |   / \
        2  /   3
         \/
          1

The drawing is schematic: read each upward line as a cover. A multi-edge upward path records the comparisons removed by transitive reduction.

Least, greatest, minimal, and maximal

These four terms sound similar but make different claims.

An element $\ell$ is a least element when

It is below every element. A least element, if it exists, is unique.

An element $g$ is a greatest element when

It is above every element and is also unique if it exists.

An element $m$ is minimal when no distinct element lies below it:

An element $M$ is maximal when no distinct element lies above it:

A poset can have several minimal or maximal elements because they may be incomparable. It can have at most one least and at most one greatest element.

For divisibility on $D$, $1$ is the least element and $12$ is the greatest element. Therefore they are also the only minimal and maximal elements.

Now consider

Both $\{a\}$ and $\{b\}$ are minimal, but neither is least because neither is a subset of the other. The set $\{a,b\}$ is greatest and maximal.

Use the diagram test carefully:

• minimal means “nothing strictly below this node”;

• least means “this node can reach every other node upward”;

• maximal means “nothing strictly above this node”;

• greatest means “every other node can reach this node upward.”

Sculpt a Hasse diagram from an overloaded divisibility network. Remove loops and transitive edges, preserve every comparison through upward paths, and identify extreme elements. A second subset challenge shows why several minimal elements do not create a least element.

Chapter bridge

Chapter 4 built structures from ordered pairs. Functions enforce one output per input; relations allow general connections; equivalence relations create partitions; partial orders express hierarchy without forcing every pair to be comparable.

Chapter 5 turns from structures to procedures. We will describe algorithms that transform inputs into outputs, prove that their steps are correct, and compare how their resource needs grow.