Warning 19.2.1.
We previously used the symbol \(\mathord{\subgraph}\) to mean exclusively “is a subgraph of,” but that was in anticipation of the introduction of this symbol to now mean a general partial order.
Section 19.2 Definition and examples
Notice that in each of the examples in Section 19.1, the notion of “is smaller than” is defined via a relation. We will use \(\mathord{\le}\) on \(\N\) as our model for a relation on a set that can be thought of as expressing “is smaller than or equal in size to.”
- Every element in the set should be “smaller than or equal to” itself, so the relation should be reflexive.
- Relative size should never be bidirectional for distinct elements in the set, so the relation should be antisymmetric.
- We should be able to infer size relationships from chains of them, so the relation should be transitive.
Notice that these are the same properties as for an equivalence relation, except that we have flipped symmetric to antisymmetric. Make sure to keep this straight!
- partial order
- a relation that is reflexive, antisymmetric, and transitive
- partially ordered set
- a set equipped with a particular partial order
- \(\mathord{\partorder}\)
- symbol for an abstract partial order
- strictly less/smaller than
- \(a \partorder b\) and \(a \neq b\)
- \(a \partorderstrict b\)
- \(a\) is strictly less/smaller than \(b\)
Example 19.2.2. “Less than or equal to” versus “less than” on sets of numbers.
The usual notion of \(\mathord{\leq}\) is a partial order on \(\N\) (or \(\Z\) or \(\Q\) or \(\R\)), but \(\mathord{\lt}\) is not.
Example 19.2.3. Subset relation.
For every set \(U\text{,}\) the relation \(\mathord{\subseteq}\) is a partial order on \(\powset{U}\text{,}\) but \(\mathord{\subsetneqq}\) is not.
Example 19.2.4. Subgraph relation.
For every graph \(G\text{,}\) the subgraph relation \(\mathord{\subgraph}\) is a partial order on \(\subgraphset{G}\text{,}\) the set of subgraphs of \(G\text{.}\)
Example 19.2.5. Comparing cardinalities.
Suppose \(U\) is a universal set, and consider the collection of finite subsets of \(U\text{.}\) Then we have a natural way to compare sizes of these subsets: write \(A \mathrel{R} B\) to mean \(\card{A} \le \card{B}\text{.}\) However, this relation is not a partial order as it is not antisymmetric. This is because it is possible to have both \(A \mathrel{R} B\) and \(B \mathrel{R} A\) with \(A \neq B\text{,}\) in the case that \(\card{A} = \card{B}\text{.}\) Changing the relation to mean \(\card{A} \lneqq \card{B}\) doesn’t help, since then it wouldn’t be reflexive.
Now suppose the universal set \(U\) is infinite and consider all (hence possibly infinite) subsets of \(U\text{.}\) In this case we have a more general idea of smaller and larger, where \(A\) is smaller than \(B\) if there exists an injection \(A \ifuncto B\) but no bijection \(A \to B\text{.}\) This more general notion of size comparison via cardinality suffers the same flaws as in the finite set case, as it is not reflexive, and if we try to fix that by adding “or same size as” then it will not be antisymmetric.
However, in both finite and (possibly) infinite cases, we can turn cardinality comparison into a partial order using “smaller than or equal to”, where “smaller” must mean strictly smaller in terms of cardinality, but “equal” means equality of sets rather than equality of cardinality.
Example 19.2.6. English alphabetic order.
Let \(\Sigma = \EngAlphabet\text{,}\) and consider alphabetic order on the set of words \(\words{\Sigma}\text{;}\) e.g.
\begin{align*}
\mathrm{gqtiu} \amp \partorder \mathrm{ppb}, \amp
\mathrm{aaay} \amp \partorder \mathrm{aaaz}, \amp
\mathrm{aaa} \amp \partorder \mathrm{aaaa}.
\end{align*}
Alphabetic ordering is a partial order on \(\words{\Sigma}\text{.}\)
Example 19.2.7. Lexicographic order.
We can generalize the previous example: if \(\Sigma\) is a partially ordered alphabet set equipped with partial order \(\mathord{\partorder}\text{,}\) then we may inductively define a partial order \(\mathord{\words{\partorder}}\) on \(\words{\Sigma}\) by:
- \(\emptyword \words{\partorder} w\) for every \(w \in \words{\Sigma}\text{,}\) where \(\emptyword\) is the empty word;
- for \(a,b \in \Sigma\text{,}\) considering these letters as words of length \(1\) in \(\words{\Sigma}\) take \(a \words{\partorder} b\) to mean \(a \partorder b\) in \(\Sigma\text{;}\)
- for letters \(a_1, a_2 \in \Sigma\) and words \(w_1, w_2 \in \words{\Sigma}\text{,}\) take \(a_1 w_1 \words{\partorder} a_2 w_2\) to mean that either
- \(a_1 \ne a_2\) and \(a_1 \partorder a_2\text{,}\) or
- \(a_1 = a_2\) and \(w_1 \words{\partorder} w_2\text{.}\)
This is called lexicographic or dictionary order on \(\words{\Sigma}\text{.}\)
Example 19.2.8. Ordering Cartesian products.
We can employ a similar tactic for Cartesian products. If \(\mathord{\partorder_A}, \mathord{\partorder_B}\) are partial orders on sets \(A,B\text{,}\) respectively, we can define a partial order \(\mathord{\partorder}\) on \(A \cartprod B\) by allowing \((a_1, b_1) \partorder (a_2, b_2)\) to mean that either
- \(a_1 \ne a_2\) and \(a_1 \partorder_A a_2\text{,}\) or
- \(a_1 = a_2\) and \(b_1 \partorder_B b_2\text{.}\)
This is also called lexicographic order.
Example 19.2.9. Larger/greater than is a partial order.
We can flip “smaller/less than or equal to” around to “larger/greater than or equal to.” For example, for elements \(m,n \in \N\text{,}\) write \(m \partorder n\) to mean \(m \ge n\text{.}\) Then \(\mathord{\partorder}\) is a partial order on \(\N\text{.}\)
This is an instance of a more general pattern. Given a partial order \(\mathord{\partorder}\) on a set \(A\text{,}\) the inverse relation \(\mathord{\inv{\partorder}}\text{,}\) where \(a_1 \mathrel{\inv{\partorder}} a_2\) means \(a_2 \partorder a_1\text{,}\) is also a partial order on \(A\text{,}\) called the dual order.
Example 19.2.10. Transferring \(\le\) on \(\N\) to a power set.
Let \(A = \{a,b,c,d\}\text{,}\) and let us “encode” each element of \(\powset{A}\) by the following algorithm.
Given input element \(X \in \powset{A}\) (that is, given input \(X\) that is a subset of \(A\)):
- Initialize encoded value \(r = 0\text{.}\)
- If \(X\) contains \(a\text{,}\) add \(1\) to \(r\text{.}\)
- If \(X\) contains \(b\text{,}\) add \(2\) to \(r\text{.}\)
- If \(X\) contains \(c\text{,}\) add \(4\) to \(r\text{.}\)
- If \(X\) contains \(d\text{,}\) add \(8\) to \(r\text{.}\)
- Set \(\operatorname{encode}(X)\) to be the final value of \(r\text{.}\)
For example,
\begin{align*}
\operatorname{encode}\bbrac{\{b\}} \amp = 2, \amp
\operatorname{encode}(\emptyset) \amp = 0,\\
\operatorname{encode}\bbrac{\{a,c\}} \amp = 1 + 4 = 5, \amp
\operatorname{encode}(A) \amp = 1 + 2 + 4 + 8 = 15.
\end{align*}
This encoding process is one-to-one; that is, no two subsets of \(A\) will output the same encoded value.
Now define \(\mathord{\partorder}\) on \(\powset{A}\) by taking \(X \partorder Y\) to mean \(\operatorname{encode}(X) \le \operatorname{encode}(Y)\text{.}\) For example,
\begin{align*}
\{a,b,c\} \amp \partorder \{d\}, \amp \{a,d\} \amp \partorder \{b,d\},
\end{align*}
and both
\begin{align*}
\emptyset \amp \partorder X, \amp X \amp \partorder A
\end{align*}
are true for every subset \(X \subseteq A\text{.}\)
The facts that \(\mathord{\le}\) is a partial order on \(\N\) and that this encoding process is one-to-one will combine to make \(\mathord{\partorder}\) a partial order.
Example 19.2.11. Pulling a partial order back through an injection.
Generalizing Example 19.2.10, suppose \(\ifuncdef{f}{A}{B}\) is an injection where \(B\) is partially ordered by \(\mathord{\partorder_B}\text{.}\) Then we can “pull back” the partial order on \(B\) to create a partial order on \(A\) as follows: define \(a_1 \preceq_A a_2\) to mean that \(f(a_1) \preceq_B f(a_2)\) is true. Note that the assumption that \(f\) is injective is essential to guarantee that \(\mathord{\partorder_A}\) will be antisymmetric.
