Skip to main content
Engineering LibreTexts

9.6: Partial Orders

  • Page ID
    48349
    • Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
    • Google and Massachusetts Institute of Technology via MIT OpenCourseWare
    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    After mapping the “direct prerequisite” relation onto a digraph, we were then able to use the tools for understanding computer scientists’ graphs to make deductions about something as mundane as getting dressed. This may or may not have impressed you, but we can do better. In the introduction to this chapter, we mentioned a useful fact that bears repeating: any digraph is formally the same as a binary relation whose domain and codomain are its vertices. This means that any binary relation whose domain is the same as its codomain can be translated into a digraph! Talking about the edges of a binary relation or the image of a set under a digraph may seem odd at first, but doing so will allow us to draw important connections between different types of relations. For instance, we can apply Dilworth’s lemma to the “direct prerequisite” relation for getting dressed, because the graph of that relation was a DAG.

    But how can we tell if a binary relation is a DAG? And once we know that a relation is a DAG, what exactly can we conclude? In this section, we will abstract some of the properties that a binary relation might have, and use those properties to define classes of relations. In particular, we’ll explain this section’s title, partial orders.

    The Properties of the Walk Relation in DAGs

    To begin, let’s talk about some features common to all digraphs. Since merging a walk from \(u\) to \(v\) with a walk from \(v\) to \(w\) gives a walk from u to w, both the walk and positive walk relations have a relational property called transitivity:

    Definition \(\PageIndex{1}\)

    A binary relation, \(R\), on a set, \(A\), is transitive iff

    \[\nonumber (a R b \text{ AND } b R c) \text{ IMPLIES } a R c\]

    for every \(a, b, c \in A\).

    So we have

    Lemma 9.6.2. For any digraph, \(G\), the walk relations \(G^+\) and \(G^*\) are transitive.

    Since there is a length zero walk from any vertex to itself, the walk relation has another relational property called reflexivity:

    Definition \(\PageIndex{3}\)

    A binary relation, \(R\), on a set, \(A\), is reflexive iff \(a R a\) for all \(a \in A\).

    Now we have

    Lemma 9.6.4. For any digraph, \(G\), the walk relation \(G^*\) is reflexive.

    We know that a digraph is a DAG iff it has no positive length closed walks. Since any vertex on a closed walk can serve as the beginning and end of the walk, saying a graph is a DAG is the same as saying that there is no positive length path from any vertex back to itself. This means that the positive walk relation of \(D^+\) of a DAG has a relational property called irreflexivity.

    Definition \(\PageIndex{5}\)

    A binary relation, \(R\), on a set, \(A\), is irreflexive iff

    \[\nonumber \text{NOT}(a R a)\]

    for all \(a \in A.\)

    So we have

    Lemma 9.6.6. R is a DAG iff \(R^+\) is irreflexive.

    Strict Partial Orders

    Here is where we begin to define interesting classes of relations:

    Definition \(\PageIndex{7}\)

    A relation that is transitive and irreflexive is called a strict partial order.

    A simple connection between strict partial orders and DAGs now follows from Lemma 9.6.6:

    Theorem \(\PageIndex{8}\)

    A relation \(R\) is a strict partial order iff \(R\) is the positive walk relation of a DAG.

    Strict partial orders come up in many situations which on the face of it have nothing to do with digraphs. For example, the less-than order, \(<\), on numbers is a strict partial order:

    • if \(x < y\) and \(y < z\) then \(x < z\), so less-than is transitive, and
    • \(\text{NOT}(x < x)\), so less-than is irreflexive.

    The proper containment relation \(\subset\) is also a partial order:

    • if \(A \subset B\) and \(B \subset C\) then \(A \subset C\), so containment is transitive, and
    • \(\text{NOT}(A \subset A)\), so proper containment is irreflexive.

    If there are two vertices that are reachable from each other, then there is a positive length closed walk that starts at one vertex, goes to the other, and then comes back. So DAGs are digraphs in which no two vertices are mutually reachable. This corresponds to a relational property called asymmetry.

    Definition \(\PageIndex{9}\)

    A binary relation, \(R\), on a set, \(A\), is asymmetric iff

    \[\nonumber aRb \text{ IMPLIES NOT}(b R a)\]

    for all \(a, b \in A.\)

    So we can also characterize DAGs in terms of asymmetry:

    Corollary 9.6.10. A digraph \(D\) is a DAG iff \(D^+\) is asymmetric.

    Corollary 9.6.10 and Theorem 9.6.8 combine to give

    Corollary 9.6.11. A binary relation \(R\) on a set \(A\) is a strict partial order iff it is transitive and asymmetric.9

    A strict partial order may be the positive walk relation of different DAGs. This raises the question of finding a DAG with the smallest number of edges that determines a given strict partial order. For finite strict partial orders, the smallest such DAG turns out to be unique and easy to find (see Problem 9.25).

    Weak Partial Orders

    The less-than-or-equal relation, \(\leq\), is at least as familiar as the less-than strict partial order, and the ordinary containment relation, \(\subseteq\), is even more common than the proper containment relation. These are examples of weak partial orders, which are just strict partial orders with the additional condition that every element is related to itself. To state this precisely, we have to relax the asymmetry property so it does not apply when a vertex is compared to itself; this relaxed property is called antisymmetry:

    Definition \(\PageIndex{12}\)

    A binary relation, \(R\), on a set \(A\), is antisymmetric iff, for all \(a \neq b \in A\),

    \[\nonumber a R b \text{ IMPLIES NOT}(b R a)\]

    Now we can give an axiomatic definition of weak partial orders that parallels the definition of strict partial orders.10

    Definition \(\PageIndex{13}\)

    A binary relation on a set is a weak partial order iff it is transitive, reflexive, and antisymmetric.

    The following lemma gives another characterization of weak partial orders that follows directly from this definition.

    Lemma 9.6.14. A relation \(R\) on a set, \(A\), is a weak partial order iff there is a strict partial order, \(S\), on \(A\) such that

    \[\nonumber a R b \textit{ iff } (a S b \text{ OR } a = b),\]

    for all \(a, b \in A\).

    Since a length zero walk goes from a vertex to itself, this lemma combined with Theorem 9.6.8 yields:

    Corollary 9.6.15. A relation is a weak partial order iff it is the walk relation of a DAG.

    For weak partial orders in general, we often write an ordering-style symbol like \(\preceq\) or \(\sqsubseteq\) instead of a letter symbol like \(R\). 11 Likewise, we generally use \(\prec\) or \(\sqsubset\) to indicate a strict partial order.

    Two more examples of partial orders are worth mentioning:

    Example 9.6.16. Let \(A\) be some family of sets and define \(aRb \textit{iff} a \supset b\). Then \(R\) is a strict partial order.

    Example 9.6.17. The divisibility relation is a weak partial order on the nonnegative integers.

    For practice with the definitions, you can check that two more examples are vacuously partial orders on a set \(D\): the identity relation \(Id_D\) is a weak partial order, and the empty relation—the relation with no arrows—is a strict partial order.

    9Some texts use this Corollary to define strict partial orders.

    10Some authors define partial orders to be what we call weak partial orders, but we’ll use the phrase “partial order” to mean either a weak or strict one.

    11General relations are usually denoted by a letter like \(R\) instead of a cryptic squiggly symbol, so \(\preceq\) is kind of like the musical performer/composer Prince, who redefined the spelling of his name to be his own squiggly symbol. A few years ago he gave up and went back to the spelling “Prince.”


    This page titled 9.6: Partial Orders is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer (MIT OpenCourseWare) .