0
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ By comparable it means that in a relation R, aRb and bRa. How does 2*i|2*j related in this situation $\endgroup$ – Jay Sun Oct 21 '17 at 6:40
  • $\begingroup$ You mean either $aRb$ or $bRa$. If you can prove that result, it implies that. $\endgroup$ – Siong Thye Goh Oct 21 '17 at 6:44
  • $\begingroup$ @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. $\endgroup$ – Jay Sun Oct 21 '17 at 7:04
  • $\begingroup$ 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$. $\endgroup$ – Siong Thye Goh Oct 21 '17 at 7:07
  • $\begingroup$ 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! $\endgroup$ – Jay Sun Oct 21 '17 at 7:11
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.