Answer to Question #238819 in Discrete Mathematics for Biswajit

Question

For divisibility relation on the set {1,3,6,9,12,5,25,125}, draw Hasse diagram. Then find minimal, maximal, greatest and least elements. Then give the topological sort using the divisibility relation

Answer 1

The Hasse diagram is a graphical rendering of a partially ordered set displayed via the cover relation of the partially ordered set with an implied upward orientation. A point is drawn for each element of the poset, and line segments are drawn between these points according to the following two rules:

1. If $x<y$  in the poset, then the point corresponding to $x$ appears lower in the drawing than the point corresponding to $y$.

2. The line segment between the points corresponding to any two elements  $x$ and  $y$ of the poset is included in the drawing iff  $x$ covers $y$  or  $y$  covers $x$.

For divisibility relation on the set $A=\{1,3,6,9,12,5,25,125\}$, let us draw Hasse diagram:

It follows that 1 is the minimal element, 9, 12 and 125 are the maximal elements, 1is the least element, and there is no the greatest element. 

Then let us give the topological sort using the divisibility relation. Since 1 is the minimal element, let $a_1=1.$ Taking into account that 3 is the minimal element of $A\setminus\{a_1\},$ let $a_2=3.$ Further, by analogy, let $a_3:=5\in A\setminus\{a_1,a_2\},$ $a_4:=9\in A\setminus\{a_1,a_2,a_3\},$ $a_5:=6\in A\setminus\{a_1,a_2,a_3,a_4\},$ $a_6:=25\in A\setminus\{a_1,a_2,a_3,a_4,a_5\},$ $a_7:=12\in A\setminus\{a_1,a_2,a_3,a_4,a_5,a_6\},$ and $a_8:=125\in A\setminus\{a_1,a_2,a_3,a_4,a_5,a_6,a_7\}.$ Therefore, the topological sort is the following:

$1<3<5<9<6<25<12<125.$