4.6 Partial orders

Definition of partial orders

A partial order is a way of arranging elements in a set so that some elements can be ranked relative to each other, but not necessarily all of them. Think of course prerequisites at a university: Calculus I must come before Calculus II, but Calculus I and Introduction to Psychology have no required ordering between them.

More formally, a partial order is a relation $\preceq$ on a set that satisfies three properties. A set paired with a partial order relation is called a partially ordered set (or poset).

Properties of partial orders

Every partial order must satisfy all three of these:

• Reflexivity: Every element relates to itself. For any $a$, we have $a \preceq a$.
• Antisymmetry: If two elements each relate to the other, they must be the same element. If $a \preceq b$ and $b \preceq a$, then $a = b$.
• Transitivity: Relationships chain together. If $a \preceq b$ and $b \preceq c$, then $a \preceq c$.

The symbol used depends on context: $\leq$ for numbers, $\subseteq$ for sets, $\mid$ for divisibility, or a generic $\preceq$.

The key feature that makes a partial order partial is that some pairs of elements may be incomparable, meaning neither $a \preceq b$ nor $b \preceq a$ holds. This is what distinguishes partial orders from total orders.

Examples of partial orders

• Subset relation ($\subseteq$): On the power set of $\{1, 2\}$, we have $\{1\} \subseteq \{1, 2\}$, but $\{1\}$ and $\{2\}$ are incomparable since neither is a subset of the other.
• Divisibility ($\mid$): Among positive integers, $2 \mid 6$ and $3 \mid 6$, but 2 and 3 are incomparable since neither divides the other.
• Course prerequisites: "Intro to Programming must come before Data Structures" defines a partial order on courses, since many courses have no prerequisite relationship at all.
• File directory structures: Folders are partially ordered by containment. A parent folder contains its child, but two sibling folders are incomparable.

Hasse diagrams

A Hasse diagram is a visual representation of a poset that strips away redundant information to show only the essential structure. Instead of drawing every single relationship (including those implied by reflexivity and transitivity), you draw only the "direct" or "covering" relationships.

Construction of Hasse diagrams

To build a Hasse diagram from a partial order:

1. Draw each element as a node.
2. Identify covering relations: $a$ is covered by $b$ (written $a \lessdot b$) if $a \preceq b$, $a \neq b$, and there's no element $c$ strictly between them.
3. Position elements vertically so that if $a \preceq b$, then $a$ appears lower than $b$.
4. Draw edges only for covering relations. Omit edges that can be inferred by transitivity.
5. Omit arrows and self-loops. The upward direction already indicates the ordering, and reflexive loops are understood.

For example, the divisibility poset on $\{1, 2, 3, 6\}$ has edges from 1 to 2, 1 to 3, 2 to 6, and 3 to 6. You would not draw an edge from 1 to 6 because that relationship is already implied by the paths 1→2→6 and 1→3→6.

Interpretation of Hasse diagrams

• Read relationships bottom to top: if you can trace an upward path from $a$ to $b$, then $a \preceq b$.
• Two elements with no connecting upward path between them are incomparable.
• Chains appear as vertical sequences of connected nodes.
• Antichains appear as elements at the same "level" with no edges between them.

Comparability and incomparability

Comparable elements

Two elements $a$ and $b$ in a poset are comparable if either $a \preceq b$ or $b \preceq a$. In the divisibility poset, 3 and 12 are comparable because $3 \mid 12$.

A subset of a poset where every pair of elements is comparable forms a chain (also called a totally ordered subset or linear suborder). For instance, $\{1, 2, 4, 8\}$ under divisibility is a chain because each element divides the next.

Incomparable elements

Elements $a$ and $b$ are incomparable if neither $a \preceq b$ nor $b \preceq a$ holds. In the divisibility poset, 4 and 9 are incomparable since neither divides the other.

A subset where no two elements are comparable forms an antichain. For example, $\{4, 6, 9\}$ under divisibility is an antichain (verify: 4 doesn't divide 6, 6 doesn't divide 9, and 4 doesn't divide 9, and none of the reverses hold either).

The existence of incomparable elements is exactly what makes a partial order "partial" rather than total.

Minimal and maximal elements

Definitions and distinctions

A minimal element is one with nothing below it: there is no element $b$ in the poset with $b \prec a$ (meaning $b \preceq a$ and $b \neq a$). A maximal element is one with nothing above it: no $b$ exists with $a \prec b$.

A poset can have multiple minimal or maximal elements. In the divisibility poset on $\{2, 3, 4, 6, 12\}$, both 2 and 3 are minimal elements.

Don't confuse these with least and greatest elements:

• A least element (or minimum) is an element $a$ such that $a \preceq b$ for every $b$ in the poset. It must be comparable to everything.
• A greatest element (or maximum) is an element $a$ such that $b \preceq a$ for every $b$.

A least element, if it exists, is the unique minimal element. But a poset can have minimal elements without having a least element (as in the example above, where 2 and 3 are both minimal but neither is below the other).

Finding minimal and maximal elements

On a Hasse diagram, minimal elements sit at the bottom with no edges going downward, and maximal elements sit at the top with no edges going upward.

Without a diagram, check each element: if no other element in the set is strictly below it, it's minimal. If no other element is strictly above it, it's maximal.

Least upper bounds

Supremum concept

Given a subset $S$ of a poset, the least upper bound (or supremum, written $\sup(S)$) is an element $u$ such that:

1. $u$ is an upper bound of $S$: for every $s \in S$, $s \preceq u$.
2. $u$ is the least such upper bound: if $v$ is any other upper bound of $S$, then $u \preceq v$.

When it exists, the supremum is unique (antisymmetry guarantees this). The supremum generalizes the idea of a maximum: if $S$ has a maximum element, that element is its supremum. But a supremum can exist even when the maximum doesn't belong to $S$.

Existence of least upper bounds

A supremum is not guaranteed to exist for every subset. It depends on the structure of the poset.

• If every pair of elements has a supremum, the poset is called a join-semilattice.
• If every non-empty subset (and the empty set) has a supremum, the poset is a complete lattice.

Greatest lower bounds

Infimum concept

The greatest lower bound (or infimum, written $\inf(S)$) is the dual concept. For a subset $S$, the infimum $\ell$ satisfies:

1. $\ell$ is a lower bound of $S$: for every $s \in S$, $\ell \preceq s$.
2. $\ell$ is the greatest such lower bound: if $m$ is any other lower bound, then $m \preceq \ell$.

Like the supremum, the infimum is unique when it exists, and it generalizes the concept of minimum.

Existence of greatest lower bounds

• Not guaranteed for all subsets in a general poset.
• If every pair of elements has an infimum, the poset is a meet-semilattice.
• If every non-empty subset has both a supremum and an infimum, you're looking at a complete lattice.

Lattices

Definition of lattices

A lattice is a poset where every pair of elements has both a least upper bound and a greatest lower bound. These two operations get their own names and symbols:

• The join of $a$ and $b$, written $a \vee b$, is their least upper bound (supremum).
• The meet of $a$ and $b$, written $a \wedge b$, is their greatest lower bound (infimum).

These operations satisfy several algebraic properties: they are associative, commutative, and obey the absorption laws ($a \vee (a \wedge b) = a$ and $a \wedge (a \vee b) = a$). Because of this, lattices can be studied either through order theory or through algebra.

Types of lattices

• Complete lattice: Every subset (not just every pair) has a join and a meet. The power set of any set under $\subseteq$ is a complete lattice.
• Bounded lattice: Has a greatest element (called top, $\top$) and a least element (called bottom, $\bot$).
• Distributive lattice: Join distributes over meet and vice versa: $a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$.
• Boolean lattice: A distributive lattice where every element has a complement. The power set lattice under $\subseteq$ is the classic example.
• Modular lattice: Satisfies a weakened version of the distributive law. Every distributive lattice is modular, but not vice versa.

Applications of partial orders

Computer science applications

• Task scheduling: Dependencies between tasks form a partial order. A build system, for example, must compile source files in an order consistent with their dependencies.
• Version control: Git commits form a partial order where branches create incomparable elements that may later be merged.
• Database query optimization: Query execution plans are partially ordered by cost and dependency.
• Partial order reduction: Used in formal verification to reduce the state space when checking concurrent systems.

Mathematics applications

• Set theory: The inclusion relation $\subseteq$ on a collection of sets is one of the most natural partial orders.
• Number theory: Divisibility among integers gives a rich partial order structure studied through lattice theory.
• Topology: Partial orders on open sets help define topological spaces.
• Category theory: Posets are a special case of categories (with at most one morphism between any two objects), so results about posets often generalize.

Partial orders vs total orders

Key differences

Total orders are the special case of partial orders where every pair of elements is comparable. The integers under $\leq$ form a total order. The subsets of $\{1, 2\}$ under $\subseteq$ do not.

Conversion between partial and total orders

A linear extension of a partial order is a total order that is consistent with it: if $a \preceq b$ in the partial order, then $a \leq b$ in the total order as well.

Topological sorting is the algorithmic process of finding a linear extension. Given a directed acyclic graph representing a partial order, topological sort produces a total ordering of the elements.

A single partial order can have multiple valid linear extensions. For the divisibility poset on $\{1, 2, 3, 6\}$, both $1, 2, 3, 6$ and $1, 3, 2, 6$ are valid linear extensions.

Chains and antichains

Definitions and properties

• A chain is a subset of a poset in which every two elements are comparable. It's a totally ordered subset.
• An antichain is a subset in which no two elements are comparable.
• The height of a poset is the size of its longest chain (minus 1, in some conventions).
• The width of a poset is the size of its largest antichain.

These two concepts are dual to each other and together capture how "tall" versus "wide" a poset is.

Dilworth's theorem

Dilworth's theorem states: in any finite poset, the width (size of the largest antichain) equals the minimum number of chains needed to partition the entire set.

This is a powerful result. If the largest antichain has 3 elements, then you need at least 3 chains to cover every element, and Dilworth's theorem guarantees that 3 chains will suffice.

The dual result (Mirsky's theorem) states that the height (length of the longest chain) equals the minimum number of antichains needed to partition the set.

Both theorems have applications in combinatorics, scheduling, and graph coloring.

Order isomorphisms

Definition of order isomorphisms

An order isomorphism between two posets $(A, \preceq_A)$ and $(B, \preceq_B)$ is a bijection $f: A \to B$ that preserves order in both directions:

$x \preceq_A y \iff f(x) \preceq_B f(y)$

If such a function exists, the two posets are order-isomorphic, meaning they have identical structure even if their elements look different. Their Hasse diagrams will have the same shape.

Preservation of order structure

Order isomorphisms preserve every structural property: chains, antichains, minimal and maximal elements, height, width, lattice structure, and the existence of suprema and infima. If you prove a theorem about one poset, it automatically holds for any isomorphic poset.

This makes order isomorphism the right notion of "sameness" for posets, just as graph isomorphism is for graphs or group isomorphism is for groups.