Check if the following defines a (total) order ($x\leq_p y$ iff the largest prime factor of $x$ is $\leq$ the largest prime factor of $y$)

Question

Let $(\mathbb{N}\setminus\{1\}, \leq_p)$ with $x\leq_p y$ iff the largest prime factor of $x$ is $\leq$ the largest prime factor of $y$. Check if this defines a (total) order by checking the four order axioms.

---

To verify that this is a valid order I must verify the four axioms of order relations:

O1. Reflexivity: $x \leq x$.

O2. Anti-symmetry: $x \leq y \land y \leq x \Rightarrow x=y$.

O3. Transivitity: $x \leq y \land y \leq z \Rightarrow x \leq z$.

O4. Total order: $\forall x,y\in X: x\leq y \lor y \leq x$.

---

I really have no idea how to show this. I assume this wouldn't be enough for the first three axioms, right?

Let the largest prime factor of $x := p(x)$.

O1. $p(x) = p(x)$ and as such the axiom is fulfilled.

O2. If $p(x) \leq p(y) \land p(y) \leq p(x) \Rightarrow p(x)=p(y)$.

O3. ?

With O4 being shown through induction.

Answer 1

No, that's not quite the right approach. Here is what you need just for O1 and O2:

O1. We need to show $x \le_p x$ for any $x$ in the domain. Well, since $p(x) \le p(x)$ we have that $x \le_p x$, and as such the axiom is fulfilled.

O2. We need to show that if $x \le_p y$ and $y \le_p x$, then $x=y$ for any $x$ and $y$ in the domain. Well, if $x \le_p y$ and $y \le_p x$, then $p(x) \leq p(y)$ and $p(y) \leq p(x)$. This indeed means $p(x)=p(y)$ ... but does that mean $x=y$?

HINT

Take $x=2$ and $y=4$. They both have $2$ as the greatest prime factor, and so we have $x \le_p y$ and $y \le_p x$, but we don't have $x=y$. So, it is not anti-symmetric