in Set Theory & Algebra retagged by
135 views
1 vote
1 vote
Find a compatible total order for the divisibility relation
on the set {1, 2, 3, 6, 8, 12, 24, 36}.
in Set Theory & Algebra retagged by
by
135 views

2 Answers

1 vote
1 vote

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.

2 Comments

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

Yes @samarpita.You are correct. 

1
1
1 vote
1 vote

Let's start with the hasse diagram.

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$

Related questions