Skip to main content
\(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Chapter6Partially Ordered Sets

Discussion6.1

Alice was surfing the web and found a site listing top movies, grouped by categories (comedy, drama, family, etc) as well as by the decade in which they were released. Alice was intrigued by the critic's choices and his rankings, especially for the top seven dramas from the 1990's. Alice agreed with the critic's choices as a group but not the specific rankings. She wrote the critic's rankings on the board and just to the right, she gave her own rankings, all the time insisting that she was certainly correct in her opinions.

Movie Critic's Ranking Alice's Ranking
1 Saving Private Ryan Life is Beautiful
2 Life is Beautiful Saving Private Ryan
3 Forrest Gump Good Will Hunting
4 Braveheart Titanic
5 Good Will Hunting Braveheart
6 Titanic Forrest Gump
7 Jurassic Park Jurassic Park

Dave studied the two rankings and listened carefully to Alice's rationale (which he felt was a bit over the top), but eventually, he held up the following diagram and offered it as a statement of those comparisons on which both Alice and the movie critic were in agreement.

<<SVG image is unavailable, or your browser cannot render it>>

Figure6.2Top Movies from the 90's

Do you see how Dave made up this diagram? Add your own rankings of these seven films and then draw the diagram that Dave would produce as a statement about the comparisons on which you, Alice and the movie critic were in agreement.

More generally, when humans are asked to express preferences among a set of options, they often report that establishing a totally ranked list is difficult if not impossible. Instead, they prefer to report a partial order—where comparisons are made between certain pairs of options but not between others. In this chapter, we make these observations more concrete by introducing the concept of a partially ordered set. Elementary examples include (1) a family of sets which is partially ordered by inclusion and (2) a set of positive integers which is partially ordered by division. From an applications standpoint, a complex construction job typically involves a large number of projects for which there is a notion of precedence between some but not all pairs. Also, computer file systems are modeled by trees which become partially ordered sets whenever links are added.