Proving that this relation is an order relation on $\Bbb N$?

Question

$S := \{(x, y) \in \Bbb N / \{1\} \times \Bbb N\ / \{1\}$ $x$ and $y$ have the same number of prime factors and $|x - {100\over{3}}| \leq |y - {100\over{3}}|$$ \}$

Is $S$ an order relation on $\Bbb N$? I am not sure how I would approach this problem.

It should be reflexive, it is not symmetric because $(3, 5) \in S$ but $(5, 3) \not \in S $.

$(3, 5) \in S$ and $(5, 7) \in S $ then $(3, 7) \in S$ so it seems to be transitive, at least for prime numbers.

I am not sure how I would proof this more formal.

Answer 1

$S$ is an order relation if and only if:

• $S$ is reflexive, so $(a,a) \in S$
• $S$ is anti-symmetric. This is not the same as not symmetric! Rather, you need to prove that if both $(a,b) \in S$ and $(b,a) \in S$ then $a=b$.
• $S$ is transitive, so if $(a,b) \in S$ and $(b,c) \in S$, then $(a,c) \in S$.

Since $a$ and $a$ have the same number of prime factors and $\left| a - \frac{100}{3} \right| = \left| a - \frac{100}{3} \right|$, $S$ is reflexive.

$(a,b) \in S$ and $(b,a) \in S$ imply $\left| b - \frac{100}{3} \right| \leq \left| a - \frac{100}{3} \right|$ and $\left| a - \frac{100}{3} \right| \leq \left| b - \frac{100}{3} \right|$, so $\left| a - \frac{100}{3} \right| = \left| b - \frac{100}{3} \right|$, so $a - \frac{100}{3} = b - \frac{100}{3}$ or $a - \frac{100}{3} = \frac{100}{3}-b$. This means $a=b$ or $a=\frac{200}{3}-b$, but the latter can't be satisfied by positive integers $a,b$, so $a=b$. Therefore $S$ is anti-symmetric.

If $a$ and $b$ have the same number of prime factors and $b$ and $c$ have the same number of prime factors, clearly $a$ and $c$ also have the same number of prime factors. Also $\left| a - \frac{100}{3} \right| \leq \left| b - \frac{100}{3} \right|$ and $\left| b - \frac{100}{3} \right| \leq \left| c - \frac{100}{3} \right|$, so $\left| a - \frac{100}{3} \right| \leq \left| c - \frac{100}{3} \right|$. Hence $S$ is transitive.

Answer 2

"$x$ and $y$ have the same number of prime factors" is easily seen to be transitive (in fact, it's an equivalence relation). "$|x - {100\over{3}}| \leq |y - {100\over{3}}|$" is clearly transitive since $\leq$ is transitive. Thus the intersection of these two relations is also transitive.