Partial order

This article aims to provide an introduction to partial orders suitable for programmers. It is not intended to be a comprehensive overview of the mathematical theory. Changes to this should be discussed on the talk page.

A partial order or partial ordering is a structure imposed on a set, which may imply that some elements are smaller, less, or before other elements, in some sense of these words. It generalizes the familiar notion of less than or equal to on numbers and is represented by the symbol ≤.

Definition and properties

Formally, a partial order satisfies the following three properties:

• Reflexivity: $a \leq a$ for any element $a$.
• Antisymmetry: If $a \leq b$ and $b \leq a$, then $a = b$.
• Transitivity: If $a \leq b$ and $b \leq c$, then $a \leq c$.

The first property tells us that an element is always less than or equal to itself. The second tells us that two elements cannot each be strictly less than the other. The third generalizes the familiar property of "chaining together" comparisons (the property that allows us to write $a \leq b \leq c$ and so on).

Two elements $a, b$ are said to be comparable under the partial order $\leq$ if and only if either $a \leq b$ or $b \leq a$. Otherwise they are incomparable. A subset in which every pair of elements is comparable is known as a chain.

A set, taken together with a partial order on that set, is known as a partially ordered set or poset. Any subset of a poset is itself a poset under the same relation ≤.

A strict partial order is similar to a partial order, but instead defines a relation, usually denoted <, which satisfies the following three properties:

• Irreflexivity: $a \nless a$ for any element $a$.
• Antisymmetry: If $a < b$, then $b \nless a$.
• Transitivity: If $a < b$ and $b < c$, then $a < c$.

We can convert a partial order into a strict partial order and vice versa by toggling reflexivity.

Examples of partially ordered sets

The following (and all their subsets) are (non-strict) posets:

• The set of all subsets of a given set, where $a \leq b$ if and only if $a \subseteq b$.
• The set of all subgraphs of a given graph, where $a \leq b$ if and only if $a$ is a subgraph of $b$.
• The set of all strings on a given alphabet, where $a \leq b$ if and only if $a$ is a substring of $b$.
• The real numbers.
• The complex numbers, where $a+bi \leq c+di$ if and only if $a \leq c$ and $b \leq d$.
• The integers, where $a \leq b$ if and only if $a \mid b$. (Note that this is not the familiar sense of "less than or equal to" on integers.)
• The Cartesian product of any number of posets, using the lexicographic ordering.

The following are strictly partially ordered sets:

• The set of human beings, where $a < b$ if and only if $a$ is an ancestor of $b$.
• The set of employees in a corporate hierarchy, where $a < b$ if and only if $a$ supervises $b$
• The set of courses in a university curriculum, where $a < b$ if and only if $a$ is a prerequisite for $b$
• The set of all subsets of a given set, where $a < b$ if and only if $a \subsetneq b$.
• The set of all subgraphs of a given graph, where $a < b$ if and only if $a$ is a proper subgraph of $b$.
• The set of all substrings of a given string, where $a < b$ if and only if $a$ is a proper substring of $b$.
• The real numbers.
• The integers, where $a < b$ if and only if $a$ is a proper divisor of $b$.

(The fact that some examples appear in one list but not the other does not suggest that some sets are non-strictly partially ordered but not strictly partially ordered, or vice versa; it just implies that the conversion is not meaningful.)

The following are not posets.

• The set of human beings, where $a < b$ if and only if $a$ is $b$'s parent. This fails to be transitive.
• The set of human beings, where $a \leq b$ if and only if $a$ and $b$ are siblings. (This is actually an equivalence relation.) This fails to be antisymmetric.
• The complex numbers, where $a \leq b$ if and only if $\|a\| \leq \|b\|$. This fails to be antisymmetric.

Representation as DAG

A cyclic relationship cannot exist among elements of a strict poset: if $a_1 < a_2 < ... < a_n < a_1$, then, by transitivity, we obtain $a_1 < a_1$, which violates irreflexivity. Therefore, if we now let each element of a poset correspond to a vertex in a digraph, with a path existing from $u$ to $v$ only if $a < b$, we obtain a directed acyclic graph (DAG). (The fact that reachability is transitive is really what allows this correspondence to exist.) Note that this does not necessarily specify where the edges are in the DAG. If there are not enough edges, then the DAG will not fully represent the equivalence relation, because some paths might not exist between pairs of nodes even if they correspond to comparable elements. But there also cannot be too many; we must ensure that we do not add edges that cause a path to exist from $a$ to $b$ where $b \leq a$ or $a$ and $b$ are not comparable. Still, there may be many DAGs that correspond to, and uniquely specify, a given partial order; if edges $(a,b)$ and $(b,c)$ already exist, for example, then the edge $(a,c)$ would be redundant by transitivity (i.e, it would not alter the reachability properties of the DAG). Given the family of DAGs corresponding to and uniquely specifying a given partial order, the one with no redundant edges, that is, the least number of edges possible, is called the transitive reduction, and the one with all possible redundant edges, that is, the greatest number of edges possible, is called the transitive closure. A path in a the transitive closure of a DAG corresponds to a chain in the poset.

Total order

A totally ordered set is a partially ordered set in which every pair of elements is comparable, or, equivalently, the entire set is a chain. The structure is known as a total order or total ordering. Examples of totally ordered sets are the following, and subsets thereof:

• The real numbers.
• The complex numbers, where $a+bi \leq c+di$ if and only if either $a < c$ or $a = c$ and $b \leq d$.
• The words in a dictionary, where $a < b$ if and only if $a$ precedes $b$ in the dictionary. (Note that $a$ and $b$ represent words, not the literal strings a and b.)
• The Cartesian product of any number of totally ordered sets, using the lexicographic ordering.
• The people in a queue, where $a < b$ if and only if $a$ is ahead of $b$.

The following are not totally ordered:

• The set of all subsets of a given set, where $a \leq b$ if and only if $a \subseteq b$.
• The set of all subgraphs of a given graph, where $a \leq b$ if and only if $a$ is a subgraph of $b$.
• The set of all strings on a given alphabet, where $a \leq b$ if and only if $a$ is a substring of $b$.
• The complex numbers, using the usual $\leq$ relation — this is not defined on $\mathbb{C}$.
• The integers, where $a \leq b$ if and only if $a \mid b$.
• The set of human beings, where $a < b$ if and only if $a$ is an ancestor of $b$.
• The set of employees in a corporate hierarchy, where $a < b$ if and only if $a$ supervises $b$.
• The set of courses in a university curriculum, where $a < b$ if and only if $a$ is a prerequisite for $b$.

The transitive closure of a DAG corresponding to a total order looks like the complete graph, but with each edge oriented in the appropriate direction. The transitive reduction consists of a single path that contains all vertices.

Wellorder

A wellordered set (sometimes written with an intervening space or hyphen) is a totally ordered set with the property that every nonempty subset has a unique least element. The natural numbers are wellordered, as are the integers in any bounded interval, and the characters of the ASCII character set. We can also construct wellorderings on Cartesian products of wellordered sets using the lexicographic ordering. The reals are not wellordered using the usual relation $\leq$; consider for example the set of positive real numbers, which has no least element. Only elements of wellordered sets may be used to index arrays. (This explains why, for example, Pascal will allow integers, characters, and enumerated types as array indices, but not reals.)