Section 6.11 An Activity Introducing Posets

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 divisibility. 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.

A binary relation \(R\) on a set \(X\) is a subset of the cartesian product \(X\times X = \set{(x,y)\colon x,y\in X}\text{.}\) In discussions of binary relations, the notation \((x,y)\in R\) is sometimes written as \(xRy\text{.}\)

When using the ordered pair notation for binary relations, to indicate that a pair \((x,y)\) is not in the relation, we simply write \((x,y)\notin R\text{.}\) When using the alternate notation, this is usually denoted by using the negation symbol from logic and writing \(\lnot (xRy)\text{.}\)

A partially ordered set or poset \(\bfP\) is a pair \((X,P)\) where \(X\) is a set and \(P\) is a reflexive, antisymmetric, and transitive binary relation on \(X\text{.}\) We call \(X\) the ground set while \(P\) is a partial order on \(X\text{.}\) Elements of the ground set \(X\) are also called points, and the poset \(\bfP\) is finite if its ground set \(X\) is a finite set.

When \(\PXP\) is a poset, it is common to write \(x\le y\) in \(P\) or \(y\ge x\) in \(P\) as substitutes for \((x,y)\in P\text{.}\) Of course, the notations \(x\lt y\) in \(P\) and \(y>x\) in \(P\) mean \(x\le y\) in \(P\) and \(x\ne y\text{.}\) When the poset \(\bfP\) remains fixed throughout a discussion, we will sometimes abbreviate \(x\le y\) in \(P\) by just writing \(x\le y\text{,}\) etc. We say that \(x\) is comparable to \(y\) in \(P\) provided that \(x\leq y\) or \(y\leq x\) in \(P\text{.}\) Otherwise, we say that \(x\) and \(y\) are incomparable.

When \(x\) and \(y\) are distinct points from \(X\text{,}\) we say \(x\) is covered

¹

Reflecting the vagaries of the English language, mathematicians use the phrases: (1) \(x\) is covered by \(y\) in \(P\text{;}\) (2) \(y\) covers \(x\) in \(P\text{;}\) and (3) \((x,y)\) is a cover in \(P\) interchangeably.

by \(y\) in \(P\) when \(x\lt y\) in \(P\text{,}\) and there is no point \(z\in X\) for which \(x\lt z\) and \(z\lt y\) in \(P\text{.}\) For example, in the poset \(\bfP_3=(X,R_3)\) from Example 6.43, \(d\) is covered by \(e\) and \(c\) covers \(b\text{.}\) However, \(a\) is not covered by \(f\text{,}\) since \(a\lt e\lt f\) in \(R_3\text{.}\)

It is convenient to illustrate a poset with a suitably drawn diagram in the Euclidean plane. We choose a standard horizontal/vertical coordinate system in the plane and require that the vertical coordinate of the point corresponding to \(y\) be larger than the vertical coordinate of the point corresponding to \(x\) whenever \(y\) covers \(x\) in \(P\text{.}\) Each cover relation is represented by a straight line segment which contains no point corresponding to any element in the poset other than those associated with its two end points. Such diagrams are called Hasse diagrams

²

Named for German mathematician Helmut Hasse, who was born in 1898. Care is required with things named after mathematicians of that era, since many of them were Nazis. Hasse’s background is a bit complicated, but his doctoral supervisor was Jewish and he collaborated with many prominent Jewish mathematicians, including Emmy Noether. So we shall let the name persist.

(also poset diagrams, order diagrams, or simply diagrams ). The drawing in Figure 6.44 is a diagram of the poset \(\bfP_3\) from Example 6.43.

For posets of moderate size, diagrams are frequently used to define a poset — rather than the explicit binary relation notation illustrated in Example 6.43. In Figure 6.45, we illustrate a poset \(\PXP\) with ground set \(X=[17]=\{1,2,\dots,17\}\text{.}\) It would take several lines of text to write out the binary relation \(P\text{,}\) and somehow the diagram serves to give us a more tactile sense of the properties of the poset.