141 views
Find a compatible total order for the divisibility relation
on the set {1, 2, 3, 6, 8, 12, 24, 36}.

There can be many compatible total orderings. One of them :-

Final Order : $1<2<3<8<6<12<36<24$.

Other possible total orders : $1<3<2<6<8<12<24<36$ or $1<2<3<6<8<12<24<36$, etc.

Basically after the Hasse Diagram of the divisibility relation, we have to do Topological sort.

Yes @samarpita.You are correct.

The Hasse diagram has only one minimum element, which is the number at the bottom. In the suitable total sequence, we'll start with this number: $1$

Remove the Hasse diagram's associated vertex:

The remaining Hasse diagram has just two basic elements: $2$ and $3$. Either of the two components is available to us. Let us start with $3$ : $1$ $\prec$ $3$

Note that you may use any of the two values, thus the answer isn't unique. Remove the vertex that corresponds to it:

In the Hasse diagram, there is just one minimum element: $2$. Add this amount to the whole order:  $1$ $\prec$ $3$ $\prec$ $2$

Remove the vertex that corresponds to it:

The remaining Hasse diagram has just two basic elements: $8$ and $6$

Either of the two components is available to us. I'll start with number six: $1$ $\prec$ $3$ $\prec$ $2$ $\prec$$6 Remove the vertex that corresponds to it: The remaining Hasse diagram has just two basic elements: 8 and 12 Either of the two components is available to us. I'll start with number eight: 1 \prec 3 \prec 2 \prec$$6$$\prec$$8$

Remove the vertex that corresponds to it:

In the Hasse diagram, there is just one minimum element: $12$

To the entire order, add this value: $1$ $\prec$ $3$ $\prec$ $2$ $\prec$$6$$\prec$$8$$\prec$$12 Remove the vertex that corresponds to it: In the remaining Hasse diagram, there are two minimum elements: 24 and 36 Either of the two components is available to us. I'll start with the number 24 1 \prec 3 \prec 2 \prec$$6$$\prec$$8$$\prec$$12$$\prec$$24$

Remove the vertex that corresponds to it:

Only $36$ item remains; add this value to the total order: The following is an example of a possible compatible total ordering:

$1$ $\prec$ $3$ $\prec$ $2$ $\prec$$6$$\prec$$8$$\prec$$12$$\prec$$24$$\prec$$36$