Question

Find a compatible total order for the divisibility relation on the set \(\{ 1,2,3,6,8,12,24,36\} \)

Short answer

The compatible total order for the divisibility relation is \(1 < 2 < 3 < 6 < 8 < 12 < 24 < 36\).

Step-by-step solution

Given data

The set is \(\{ 1,2,3,6,8,12,24,36\} \).

Concept used of minimal element rule

A minimal element of a subset\(S\)of some preordered set is defined dually as an element of\(S\)that is not greater than any other element in\(S\).

Find the compatible total order

Now, we consider the poset \(\{ 1,2,3,6,8,12,24,36\} \). The objective is to check

The divisibility compatibility on this poset. First, choose a minimal element; this must be 1 because it is the only minimal element. Next, select a minimal element of \((\{ 1,2,3,6,8,12,24,36\} ,\mid )\). There are two minimal elements in this poset, namely 2 and 3 . Select 2 .The left elements are \(\{ 3,6,8,12,24,36\} \). The only minimal element at this stage is 3 . Next, 6 is chosen because it is the only minimal element of \(\{ 6,8,12,24,36\} \) and 3 divides 6 . Now, the left elements in the set are \(\{ 8,12,24,36\} \). Here, 8 is the minimal element and 2 divides 8 . Next, 12 is chosen because it is the only minimal element of \(\{ 12,24,36\} \) and 6 divides 12 . Because both 24 and 36 are minimal elements of \(\{ 24,36\} \), either can be chosen next. So, select 36 which leaves 24 as the last element left and 12 divides 36 . This produces the total ordering where the before element divides the after one as; \(1 < 2 < 3 < 6 < 8 < 12 < 24 < 36\).