Partial order or strict order

Question

Question: The domain is the set of all positive integers. $a$ is related to $b$ if $b = a⋅ 3n$, for some positive integer $n$.

Because of the equal sign, isn't this relation symmetric, transitive, and reflexive?

Answer 1

A partial order, $\leq$, satisfies the following properties for all $a,b,c$:

• Reflexivity: $a\leq a$
• Anti-symmetry: If $a\leq b$ and $b\leq a$ then $a = b$
• Transitivity: If $a\leq b$ and $b\leq c$ then $a\leq c$

A partial order however does not have to have defined comparisons between all elements.

A total order must satisfy all of the same properties but must also have the condition that:

• Totality: $a\leq b$ or $b\leq a$

Your relation as defined above fails to be a partial order (and thus fails to be a total order) for one reason:

It is not reflexive: Note that $a\nsim a$ since $a\neq a\cdot 3n$ for any integer $n$. (the only number that would have worked was $n=\frac{1}{3}$)

It is in fact vacuously anti-symmetric, since such a pair of $a$ and $b$ do not exist. Supposing that $a\sim b$, that means that $a = b\cdot 3n$ with $n$ a positive integer. Now, note that if you also have that $b\sim a$ that would imply that $b = a\cdot 3m$ for $m$ a positive integer. As $a=b\cdot 3n$ however, that implies that $b = b\cdot 3n\cdot 3m$ and that $1 = 9\cdot n\cdot m$, a contradiction.

It is also transitive. If $a\sim b$ and $b\sim c$, you have $a = b\cdot 3n$ and $b = c\cdot 3m$ with $m$ and $n$ positive integers. As a result, $a = c\cdot 3m \cdot 3n = c\cdot 3\cdot (3mn)$. Noting that $3mn$ is also a positive integer, it follows that $a\sim c$.

---

A strict order, $<$, satisfies the following properties for all $a,b,c$:

• Irreflexive: $a\not < a$
• Anti-symmetric: If $a<b$ then $b\not < a$
• Transitivity: If $a<b$ and $b<c$ then $a<c$

A strict total order must also satisfy

• Totality: $a<b$ or $b<a$

The work above shows that $\sim$ as defined in the problem statement is in fact a strict order.

We ask the question now if it is a total order. Consider $2$ and $3$.

$2\nsim 3$ since $2=3\cdot 3n$ would only hold for $n=\frac{2}{9}\notin \mathbb{Z}^+$

$3\nsim 2$ since $3=2\cdot 3n$ would only hold for $n=\frac{1}{2}\notin \mathbb{Z}^+$

Thus, by counterexample, not every pair can be compared and the order is not total.

---

Final conclusion: $\sim$ as defined above is a strict order on the positive integers.