Question

Find all compatible total orderings for the poset with the Hasse diagram in Exercise 27.

Short answer

The all compatible total ordering for the poset is \(a < b < c < g < d < e < f\) and \(b < a < c < g \prec f < e \prec d\).

Step-by-step solution

Given data

Given figure is a hasse diagram.

Concept used of greatest lower bound and least upper bound

A "least upper bound" for a set is then an upper bound that is as small as possible.

An element\(b\)in\(A\)is called a greatest lower bound (or infimum) for\(X\)if\(b\)is a lower bound for\(X\)and there is no other lower bound\(b\)for\(X\)that is greater than\(b\).

Find the compatible total order

We have to find to find all the compatible total orderings for the poset with the hasse diagram. Now, an ordering of seven tasks can be obtained by performing a topological sort. The seven tasks here are a, b, c, d, e, f and \(g\). It is clear that \(g\) must go in the middle with any of the six permutations of \(\{ a,b,c\} \) before \(g\) and any of the six permutations of \(\{ d,e,f\} \) that follows \(g\). Thus, there are 36 compatible total orderings for this poset such as \(a < b < c < g < d < e < f\) and \(b < a < c < g < f < e < d\)