# proving of divide as Total Order Relation

a set $A = \{1,2,4,8,16\}$, the relation is divide '$|$'. How do i prove that it is Total Order Relation for this set.

i know that for a set to be total order relation, it has to be partial order relation and all elements in the sets are comparable.

i can prove that the set is reflexive, anti-symmetric and transitive but however how do prove that this set is comparable. Thank You!

Rewrite $A=\{2^i|i \in \{ 0,1,2,3,4\} \}$

Given two element, $2^i,2^j \in A$, prove that $2^i | 2^j$ if and only if $i \leq j$.

Note taht $2^i | 2^j$ means $2^i R 2^j$.

• By comparable it means that in a relation R, aRb and bRa. How does 2*i|2*j related in this situation – Jay Sun Oct 21 '17 at 6:40
• You mean either $aRb$ or $bRa$. If you can prove that result, it implies that. – Siong Thye Goh Oct 21 '17 at 6:44
• @SiongThyGoh if 2*iR2*j, but i is smaller or equal to j, how does 2*jR2*i since i is smaller or equal to j. Thank you for guiding me in this question. – Jay Sun Oct 21 '17 at 7:04
• It doesn't. if we have $2^i|2^j$, then these two elements can be compared. It doesn't require $2^j|2^i$. – Siong Thye Goh Oct 21 '17 at 7:07
• Does that means that as long as it fulfils either aRb or bRa it would consider as comparable? or it must fulfil both aRb and bRa? Thank You! – Jay Sun Oct 21 '17 at 7:11

At first glance, it is rather easy to see that set $A$ is comparable because of the integers provided. We're given the poset ($A$, $|$). To show that these integers are comparable, all you need to do is prove that each pair of integers within the set are comparable (i.e for (16, 8) you would show $16 | 8$ or $8 | 16$. This would be comparble in the given poset because though $\frac{8}{16}$ is not divisible, $\frac{16}{8}$ is).

To show this in a simplified way, all we would have to do is simplify the set into multiples of two. So, $A=\{2^i|i \in \{ 0,1,2,3,4\} \}$ (as the above answerer does). We then know that every multiple of two is divisible by a smaller than or equal to multiple of two, so we would just show that given some element $2^j \in A$, $2^i | 2^j$ for all $i \leq j$. This would then prove the total ordering.

Alternatively, you could brute force the process and show that every ordered pair is comparable.