Why is $x \mid y$ over $\Bbb N$ a partial order but not total order?

Question

I understand why $x \mid y$ is an example of a partial order relation over $\Bbb N$. But can someone explain why its not a total order relation?

By definition a total order relation on a set $A$ is a relation $R$ that is a partial order relation and such that for all elements $a,b \in A$, $aRb$ or $bRa$ or $a=b$.

2 and 3 are coprime, i.e. neither 2 divides 3 nor 3 divides 2. Hence with the relation given the two numbers are not comparable; therefore the relation can only be a partial order and not a total order, since the necessary condition for a total order does not hold for all possible natural numbers. — Chill2Macht, Apr 16 '16 at 14:53

score 0 · Accepted Answer · answered Apr 16 '16 at 18:57

2 and 3 are coprime, i.e. neither 2 divides 3 nor 3 divides 2. Hence with the relation given (x | y) the two numbers are not comparable; therefore the relation can only be a partial order and not a total order, since the necessary condition for a total order does not hold for all possible natural numbers.

Note: this answer is an explanation of @almagest's comment.

Why is $x \mid y$ over $\Bbb N$ a partial order but not total order?

1 Answers1