9.7: Representing Partial Orders by Set Containment

Last updated
Save as PDF

Page ID: 48350

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}}\)

Axioms can be a great way to abstract and reason about important properties of objects, but it helps to have a clear picture of the things that satisfy the axioms. DAGs provide one way to picture partial orders, but it also can help to picture them in terms of other familiar mathematical objects. In this section, we’ll show that every partial order can be pictured as a collection of sets related by containment. That is, every partial order has the “same shape” as such a collection. The technical word for “same shape” is “isomorphic.”

Definition \(\PageIndex{1}\)

A binary relation, \(R\), on a set, \(A\), is isomorphic to a relation, \(S\), on a set \(B\) iff there is a relation-preserving bijection from \(A\) to \(B\); that is, there is a bijection \(f : A \rightarrow B\) such that for all \(a, a' \in A\),

\[\nonumber a R a' \textit{ iff } f(a) S f(a').\]

To picture a partial order, \(\preceq\), on a set, \(A\), as a collection of sets, we simply represent each element \(A\) by the set of elements that are \(\preceq\) to that element, that is,

\[\nonumber a \longleftrightarrow \{b \in A \mid b \preceq a\}.\]

For example, if \(\preceq\) is the divisibility relation on the set of integers, \(\{1,3,4,6,8,12\}\), then we represent each of these integers by the set of integers in \(A\) that divides it. So

\(\begin{aligned}1 &\longleftrightarrow \{1\} \\ 3 &\longleftrightarrow \{1, 3\} \\ 4 &\longleftrightarrow \{1, 4\} \\ 6 &\longleftrightarrow \{1, 3, 6\} \\ 8 &\longleftrightarrow \{1, 4, 8\} \\ 12 &\longleftrightarrow \{1, 3, 4, 6, 12\} \end{aligned}\)

So, the fact that \(3 | 12\) corresponds to the fact that \(\{1, 3\} \subseteq \{1,3,4,6,12\}.\)

In this way we have completely captured the weak partial order \(\preceq\) by the subset relation on the corresponding sets. Formally, we have

Lemma 9.7.2. Let \(\preceq\) be a weak partial order on a set, \(A\). Then \(\preceq\) is isomorphic to the subset relation, \(\subseteq\), on the collection of inverse images under the \(\preceq\) relation of elements \(a \in A\).

We leave the proof to Problem 9.29. Essentially the same construction shows that strict partial orders can be represented by sets under the proper subset relation, \(\subset\) (Problem 9.30). To summarize:

Theorem \(\PageIndex{3}\)

Every weak partial order, \(\preceq\), is isomorphic to the subset relation, \(\subseteq\), on a collection of sets.

Every strict partial order, \(\prec\), is isomorphic to the proper subset relation, \(\subset\), on a collection of sets.