Question

Find a compatible total order for the poset with the Hasse diagram shown in Exercise 32.

Short answer

One such total order compatible with the given partial order is given by

\(a{ < _t}b{ < _t}d{ < _t}e{ < _t}c{ < _t}f{ < _t}g{ < _t}h{ < _t}i{ < _t}j{ < _t}k{ < _t}m{ < _t}l.\)

Step-by-step solution

Given data

\({\rm{R}}\) is the partial order on the set \(V = \{ a,b,c, \ldots ,m\} \) corresponding to the Hasse diagram shown below,

Concept used of maximal element rule

A maximal element of a subset S of some preordered set is an element of S that is not smaller than any other element in S.

Find the compatible total order

We need to peel elements off the bottom of the Hasse diagram. We can begin with a,b or \(c\). Suppose we decide to start with a. Next we may choose any minimal element of what remains after we have removed a; only b and \(c\) meet this requirement. Suppose we choose b next. Then c, d, and e are minimal elements in what remains, so any of those can come next. We continue in this manner until we have listed and removed all the elements. One possible order, then, is\(a{ < _t}b{ < _t}d{ < _t}e{ < _t}c{ < _t}f{ < _t}g{ < _t}h{ < _t}i{ < _t}j{ < _t}k{ < _t}m{ < _t}l.\)