Recursive definition of a sequence with shifted base The following is taken from Foundations of Modern Analysis (Dieudonné) p.22:

Suppose $x:\mathbf{N}\rightarrow\mathbf{R}$ is a bijection. We define
a subsequence $p:\mathbf{N}\rightarrow\mathbf{N}$ of integers by
induction in the following way: $p(0)=0$ and $p(1)$ is the smallest
value of $n$ such that $x_0<x_n$. Suppose $p(n)$ has been defined for
$n\leq 2m-1$, and that $x_{p(2m-2)}<x_{p(2m-1)}$; then the set
$]x_{p(2m-2)},x_{p(2m-1)}[$ is infinite and we define $p(2m)$ to be
the smallest integer $k>p(2m-1)$ such that
$x_{p(2m-2)}<x_k<x_{p(2m-1)}$; then we define $p(2m+1)$ as the
smallest integer $k>p(2m)$ such that $x_{p(2m)}<x_k<x_{p(2m-1)}$. It
is immediate that the sequence $(p(n))_{n\in\mathbf{N}}$ is strictly
increasing, hence $p(n)\geq n$ for all $n\in\mathbf{N}.$

I am having difficulty understanding the recursion process with which $p$ is defined. Normally, given $p(n)$ has been defined, we define $p(n+1)$. But here the author assumes that $p(n)$ has been defined for $n\leq 2m-1$ and that $x_{p(2m-2)}<x_{p(2m-1)}$, for some $m\in\mathbf{N}_{\geq 2}$, before defining $p(2m)$ and $p(2m+1)$. What is the justification here? (e.g. why can he assume "$x_{p(2m-2)}<x_{p(2m-1)}$"?)
Can someone please translate this definition of $p$ into a standard recursive definition?
Edit:
Essentially, the process defines the following for $m\in\mathbf{N}_{\geq2}$:

*

*$p(2m):=\min\{k\in\mathbf{N}\ |\ p(2m-1)<k\land x_{p(2m-2)}<x_k<x_{p(2m-1)}\}$;

*$p(2m+1):=\min\{k\in\mathbf{N}\ |\ p(2m)<k\land x_{p(2m)}<x_k<x_{p(2m-1)}\}$.

So I guess one would have to show that the following set are nonempty for $m\in\mathbf{N}_{\geq2}$, correct?
Edit 2:
I would really appreciate if someone could put this recursion in the form prescribed by the Recursion Theorem in set theory:

Given a set $X$, an element $a\in X$ and a function $f:X\rightarrow
 X$, there exists a function $F:\mathbf{N}\rightarrow X$ such that
$F(0)=a$ and $F(n+1)=f(F(n))$.

 A: It is a standard recursive definition; it just happens in this case to be necessary to define two items at each stage. We want to construct $p$ so that
$$p(0)<p(2)<p(4)<\ldots<p(5)<p(3)<p(1)\;,\tag{1}$$
so that
$$\big(p(0),p(1)\big)\supsetneqq\big(p(2),p(3)\big)\subsetneqq\big(p(4),p(5)\big)\supsetneqq\ldots\supsetneqq\big(p(2n),p(2n+1)\big)\supsetneqq\ldots\;.$$
We do this be constructing two values of $p$ at each stage. At stage $m$ we assume that we’ve constructed $p(0),p(1),\ldots,p(2m-1)$ so that
$$p(0)<p(2)<\ldots<p(2m-2)<p(2m-1)<\ldots p(3)<p(1)\;,\tag{2}$$
i.e., so that $(1)$ is true as far as we’ve gone at that point. Then $\big(p(2m-2),p(2m-1)\big)$ is a non-empty open interval, so we can choose $p(2m)$ inside it and have $$p(2m-2)<p(2m)<p(2m-1)\;.$$ Then we similarly define $p(2m+1)\in\big(p(2m),p(2m-1)\big)$, so that
$$p(2m)<p(2m+1)<p(2m-1)\;,$$
and we can now replace our induction hypothesis $(2)$ with
$$p(0)<p(2)<\ldots<p(2m)<p(2m+1)<\ldots p(3)<p(1)\;.$$
However, the last sentence in the block quote in the question is false: the sequence $\langle p(n):n\in\Bbb N\rangle$ is not strictly increasing. The sequence $\langle p(2n):n\in\Bbb N\rangle$ is strictly increasing, and the sequence $\langle p(2n+1):n\in Bbb N\rangle$ is strictly decreasing.
