Proof of A Subsequence of a Subsequence is a Subsequence

That $(n_k)_{k\in\mathbb{N}}$ is strictly increasing means $n_k<n_{k+1}$ for every $k\in\mathbb{N}$, and similarly for $(k_j)_{j\in\mathbb{N}}$. We use the arithmetic of addition on $\mathbb{N}$ recorded in Arithmetic of Addition on the Natural Numbers and the properties of the order recorded in Properties of the Order on the Natural Numbers.

Step 1 (a shifted comparison). Let

$$A=\{p\in\mathbb{N}\ :\ n_a<n_{a+p}\ \text{for every}\ a\in\mathbb{N}\}.$$

First, $1\in A$: for every $a\in\mathbb{N}$ we have $n_a<n_{a+1}$, because $(n_k)_{k\in\mathbb{N}}$ is strictly increasing.

Next, let $p\in A$ and let $a\in\mathbb{N}$. By associativity of addition, claim 3 of Arithmetic of Addition on the Natural Numbers,

$$a+(p+1)=(a+p)+1,$$

so strict increase applied at the index $a+p$ gives $n_{a+p}<n_{a+(p+1)}$. Since $p\in A$ gives $n_a<n_{a+p}$, transitivity of $<$, claim 1 of Properties of the Order on the Natural Numbers, yields $n_a<n_{a+(p+1)}$. As $a\in\mathbb{N}$ was arbitrary, $p+1\in A$.

By claim 1 of Arithmetic of Addition on the Natural Numbers we have $p+1=S(p)$, where $S$ is the successor map of Natural Numbers, so $S(p)\in A$ for every $p\in A$. Therefore Principle of Induction for the Natural Numbers gives $A=\mathbb{N}$, that is,

$$n_a<n_{a+p}\qquad\text{for all }a,p\in\mathbb{N}.$$

Step 2 (claim 1). Let $a,b\in\mathbb{N}$ with $a<b$. By claim 7 of Properties of the Order on the Natural Numbers there is $p\in\mathbb{N}$ with $b=a+p$. By Step 1, $n_a<n_{a+p}=n_b$.

Step 3 (claim 2). Let $j\in\mathbb{N}$. Since $(k_j)_{j\in\mathbb{N}}$ is strictly increasing, $k_j<k_{j+1}$. Applying claim 1, proved in Step 2, with $a=k_j$ and $b=k_{j+1}$ gives

$$n_{k_j}<n_{k_{j+1}}.$$

As $j\in\mathbb{N}$ was arbitrary, the sequence $(n_{k_j})_{j\in\mathbb{N}}$ in $\mathbb{N}$ is strictly increasing.

Step 4 (claim 3). By claim 2 the sequence $(n_{k_j})_{j\in\mathbb{N}}$ is a strictly increasing sequence in $\mathbb{N}$, so by Subsequence of a Sequence in a Set the sequence $(x_{n_{k_j}})_{j\in\mathbb{N}}$ is a subsequence of $(x_m)_{m\in\mathbb{N}}$.

Write $(y_k)_{k\in\mathbb{N}}$ for the sequence in $X$ with $y_k=x_{n_k}$, that is, the subsequence of $(x_m)_{m\in\mathbb{N}}$ determined by $(n_k)_{k\in\mathbb{N}}$. Since $(k_j)_{j\in\mathbb{N}}$ is strictly increasing, $(y_{k_j})_{j\in\mathbb{N}}$ is by Subsequence of a Sequence in a Set a subsequence of $(y_k)_{k\in\mathbb{N}}$, and its value at $j$ is $y_{k_j}=x_{n_{k_j}}$. Hence the two sequences agree termwise, which is claim 3.