Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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 2 at 22:42

1 Answer 1

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.

share|improve this answer
    
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 2 at 22:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.