3

So I was assigned this problem for homework and I was able to all of them except for part D I would really appreciate any help or hintsenter image description here I have no clue where to start I looked through my book and everything anything would be appreciated

Will Jamieson
  • 301
  • 1
    AG has given a good way to construct a compatible total order, but in fact this poset is small and simple enough that you can explicitly construct all the compatible total orders. Note that, in any compatible total order, $a$ has to be at the top, and $fdb$ must occur in that order. So all that remains is to figure out where you can insert $e$ and $c$ into the chain $fdba$ (with $e$ below $c$ of course). Unless I've mis-counted, there are just 8 possibilities. – Andreas Blass Jan 02 '15 at 22:42

1 Answers1

2

We need to obtain a total ordering such that whenever $a < b$ in the partial ordering, we also have $a<b$ in this total ordering. Looking at the Hasse diagram, just pick out the minimal elements one by one. If there is more than one minimal element, pick any one arbitrarily. For example, first pick $e$ say, then $f, c,d,b,a$. This ordering $e<f<c<d<b<a$ is a total ordering compatible with the given partial ordering. Another order is $f,e,d,c,b,a$. In all cases, $e$ would be before $b$ and before $c$, $f$ would be before $c$ and before $d$, and $a$ would be last. This algorithm of removing minimal elements one by one is called topological sort.

AG.
  • 2,027
  • Maybe mention that, in the description of the algorithm, "minimal" means "minimal among the elements not yet chosen". It does not mean, for example, that you need to take all the minimal elements of the original set before proceeding to higher ones. For example, you could do $fdebca$. – Andreas Blass Jan 02 '15 at 22:38