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))$.
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.