Let $\alpha > 0$ be an ordinal. Does there exist two non-decreasing sequences $a,b : \alpha \to \alpha$ such that $a$ is a subsequence of $b$ and $b$ is a subsequence of $a$, but they are not the same sequence?
If we consider the same question for strictly increasing sequences (or more generally injective sequences), then they have to be the same sequence:
Let $a$ and $b$ be such sequences. Then, there exist strictly increasing functions $f,g : \alpha \to \alpha$, such that $a = b \circ f$ and $b = a \circ g$. Then, we have, $$b = a \circ g = (b \circ f) \circ g = b \circ (f \circ g)$$ Now, $f \circ g$ needs to be identity since; if $(f \circ g)(\beta) \neq \beta$ , then $b(\beta) = b((f \circ g)(\beta)) \neq b(\beta)$ since $b$ is injective.
Since $f$ and $g$ are strictly increasing, $\forall \gamma \ f(\gamma) \geq \gamma \ \text{and} \ g(\gamma) \geq \gamma$. So, $g(\beta) \neq \beta$ for some $\beta$ would imply, $$\beta = (f \circ g) (\beta) = f(g(\beta)) > f(\beta) \geq \beta$$ Therefore, $b = a \circ g = a$.
However, this argument depends on the injectivity of the sequences, so it cannot be used for non-decreasing sequences.
If $\alpha = \omega$, then we can use the fact that there is at most one element that is repeated infinitely many times and we can conclude that they have to be the same sequence, but I cannot solve it for general $\alpha$. Thank you.
For each ordinal $\gamma\in \alpha$, let $W_{a,\gamma}=a^{-1}(\gamma)$ and let $W_{b,\gamma}=b^{-1}(\gamma)$. Being subsets of $\alpha$, $W_{a,\gamma}$ and $W_{b,\gamma}$ are well-ordered sets. If $a$ is a subsequence of $b$, then there is a strictly increasing map $f_\gamma\colon W_{a,\gamma}\to W_{b,\gamma}$, so the order type of $W_{a,\gamma}$ is $\leq$ the order type of $W_{b,\gamma}$. Similarly, the order type of $W_{b,\gamma}$ is $\leq$ the order type of $W_{a,\gamma}$. So the order types are equal.
Now proceed by induction on $\gamma$ to show that $W_{a,\gamma} =W_{b,\gamma}$ for all $\gamma$ (this is where we use the fact that $a$ and $b$ are weakly increasing), and thus $a=b$.