Is my proof that the Sharkovsky Ordering is a total ordering, correct?

Question

The Sharkovsky ordering is an ordering of the natural numbers $\mathbb{N}$, where

$3$ $\prec$ $5 $ $\prec$ $7 $ $\prec$ $9$ $\prec$ ...
$2*3$ $\prec$ $2*5$ $\prec$ $2*7$ $\prec$ $2*9$ $\prec$ ...
...
$2^n*3$ $\prec$ $2^n*5$ $\prec$ $2^n*7$ $\prec$ $2^n*9$ $\prec$ ...
...
... $2^n$ $\prec$ ... $\prec$ $2^3$ $\prec$ $2^2$ $\prec$ $2$ $\prec$ $1$

The ordering starts with all odd numbers, except for one, in increasing order, followed by two times the odds, $2^2$ times the odds, $2^3$ times the odds and so one. Finally the powers of two are listed last in decreasing order.

I know what to prove that this order is a total ordering. Thus, I need to show

1. Antisymmetry: If $a \leq b$ and $b \leq a$ then $a=b$
2. Transitivity: If $a \leq b$ and $b \leq c$ then $a \leq c$
3. Connexity: $a\leq b$ or $b \leq a$

I came up with the following mapping from the Sharkovsky ordering to the natural numbers: \begin{equation}\label{eq1} P = \begin{cases} \mathbb{N}_0 \times \mathbb{N}_0 & \rightarrow \mathbb{N}\\ (r,p) & \rightarrow 2^r \cdot (2p+1) \end{cases} \end{equation}

As this function is bijective, each natural number appears exactly once in the Sharkovsky ordering.

See answer below for attempt at proof.

Answer 1

I would simply define the relation $\prec$ carefully and then use the definition to show that $\preceq$ is a linear order. Specifically,

$$\begin{align*} 2^r(2k+1)\prec 2^s(2\ell+1)\text{ iff }&r<s\text{ and }k\ne 0\ne\ell,\text{ or}\\ &r=s\text{ and }0<k<\ell,\text{ or}\\ &r>s\text{ and }k=\ell=0,\text{ or}\\ &k>0\text{ and }\ell=0\,. \end{align*}$$

Answer 2

Is my proof correct?

1. Antisymmetry

First, $$2^r (2k+1) \preceq 2^s (2l+1) \text{(1)}$$ $\text{ if } r < s \text{ and } k \neq 0 \neq l, \text{or}$
$\text{ if } r = s \text{ and } 0 < k < l, \text{or}$
$\text{ if } r > s \text{ and } k = l = 0, \text{or}$
$\text{ if } k > 0 \text{ and } l = 0,\text{or}$
$\text{ if } r = s \text{ and } k = l,$

Second, $$2^s (2l+1) \preceq 2^r (2k+1) \text{(2)}$$ $\text{ if } s < r \text{ and } l \neq 0 \neq k, \text{or}$
$\text{ if } r = s \text{ and } 0 < l < k, \text{or}$
$\text{ if } s > r \text{ and } l = k = 0, \text{or}$
$\text{ if } l > 0 \text{ and } k = 0,\text{or}$
$\text{ if } r = s \text{ and } k = l,$

Thus, if both (1) and (2) are true, $r = s$ and $k = l$, because all other options lead to contradictions. Hence $2^r (2k+1) = 2^s (2l+1)$, which implys Antisymmetry.

2. Transitivity

First, $$2^r (2k+1) \preceq 2^s (2l+1) \text{(1)}$$ $\text{ if } r < s \text{ and } k \neq 0 \neq l, \text{or}$
$\text{ if } r = s \text{ and } 0 < k < l, \text{or}$
$\text{ if } r > s \text{ and } k = l = 0, \text{or}$
$\text{ if } k > 0 \text{ and } l = 0,\text{or}$
$\text{ if } r = s \text{ and } k = l,$

Second, $$2^s (2l+1) \preceq 2^t (2m+1) \text{(2)}$$ $\text{ if } s < t \text{ and } l \neq 0 \neq m, \text{or}$
$\text{ if } t = s \text{ and } 0 < l < m, \text{or}$
$\text{ if } s > t \text{ and } l = m = 0, \text{or}$
$\text{ if } l > 0 \text{ and } m = 0,\text{or}$
$\text{ if } t = s \text{ and } m = l,$

Than,
$r<s<t$ and $k \neq 0 \neq l \neq 0 \neq m \Rightarrow r<t$ and $k \neq 0 \neq m$
$r = s = t$ and $0 < k < l<m$ $\Rightarrow r = t$ and $0 < k < m$
$r > s > t$ and $k = l = m = 0$ $\Rightarrow r > t$ and $m = 0$
$r = s = t$ and $k = l = m$ $\Rightarrow r = t$ and $k = m$

Hence, $2^r (2k+1) \preceq 2^t (2m+1)$.