Sequences and subsequences, Part III

 Recall from Part II

Definition of subsequence

Let $X$ be a non-empty set, and let $(x_n)_{n\in\N}$ be a sequence of elements of $X$. Then a subsequence of $(x_n)$ is a sequence of the form $x_{n_1},x_{n_2},x_{n_3},\dots$, where $(n_k)_{k\in\N}$ is a strictly increasing sequence of natural numbers.

The subsequence can also be written as $(x_{n_k})_{k\in\N}$, always remembering that we require that $n_1<n_2<n_3<\cdots$.

In this setting, as discussed last time, we may apply the definition above to the sequence $(n_k)_{k\in\N}$, and we see that $(n_k)_{k\in\N}$ is a subsequence of the sequence of  $1,2,3,\dots$.

Now let us revisit this in terms of functions from $\N$ to $X$ and functions from $\N$ to $\N$. We can define $f:\N\to X$ by $f(n)=x_n$, and we can define $g:\N\to\N$ by $g(k)=n_k$. Then $g$ is a strictly increasing function from $\N$ to $\N$, and we have 

$x_{n_k}= x_{g(k)}=f(g(k))\;(k\in\N)$.

Thus, if we define $h:\N\to X$ by $h(k)=x_{n_k}$, we have $h=f\circ g$. If we identify all our sequences with functions (as discussed in Part I), then a subsequence is obtained by composing on the right with a strictly increasing function from $\N$ to $\N$.

What about the interpretation from Part II in terms of infinite subsets of $\N$? Well if we set

$A=g(\N)=\{n_1,n_2,n_3,\dots\}\subseteq \N\,,$

then we know that we can freely swap back between the infinite set $A$ and the strictly increasing function $g$. Thus it makes sense to denote the subsequence $x_{n_1},x_{n_2},x_{n_3},\dots$ by $(x_n)_{n\in A}$. Here it is understood that $n$ runs through the elements of the infinite set $A$ in strictly increasing order. I am not quite sure how standard this notation is, but it does fit with several more advanced concepts, so I will work with this notation here.

Now suppose that $(y_k)_{k\in \N}$ and $(z_k)_{k\in \N}$ are both subsequences of $(x_n)_{n\in\N}$. Then these subsequences are equal (as sequences) if and only if, for all $k\in\N$, we have $y_k=z_k$. However, the sequence $(x_n)$ may have repeats in it, and so we do not know whether the indices we used to generate the subsequences were the same.

As a specific example, consider $X=\R$ and $x_n=(-1)^n$. Then we could have $y_k=x_{2k}$ and $z_k=x_{4k}$, which gives $y_k=z_k=1$ for all $k \in \N$. Thus we have two equal subsequences which were "obtained differently". An alternative might be to keep track of how the subsequence was obtained as part of the definition of subsequence, but we do not take this approach. (For those interested in nets, which are an advanced generalisation of sequences indexed by "directed sets", you might wish to think carefully about the definition of subnet.)

We conclude this part by looking at "subsubsequences", which are subsequences of subsequences. We will observe that, in fact, every subsubsequence of a sequence $(x_n)$ is equal (as a sequence) to a subsequence of $(x_n)$. We also note a few other relevant facts along the way.

Let $X$ be a non-empty set and let $(x_n)_{n\in\N}$ be a sequence of elements of $X$. As above, define $f(n)=x_n\;(n\in\N)$, so that $f:\N\to X$ may be identified with the sequence $(x_n)$.

First let us note that $(x_n)$ is a subsequence of itself, because we can take $n_k=k$ for all $k\in\N$ (corresponding to $g$ above being the identity map from $\N$ to $\N$), and then $y_k=x_{n_k}=x_k$ for all $k\in\N$. In terms of functions, we can just observe that $f\circ g = f$ here. In terms of subsets of $\N$, here we can take $A=\N$, and we have

$(x_n)_{n\in\N}=(y_n)_{n\in\N}=(x_n)_{n\in A}\,.$

Note that we do not distinguish between the sequences $(y_n)_{n\in\N}$ and $(y_k)_{k\in\N}$, as they both can be identified with the same function $f=f\circ g$ (here) from $\N$ to $X$.

Now let us look at subsubsequences, which are subsequences of subsequences. We have to be careful with the notation here. 

Let's start again!

Let $X$ be a non-empty set and let $(x_n)_{n\in\N}$ be a sequence of elements of $X$. As above, define $f(n)=x_n\;(n\in\N)$, so that $f:\N\to X$ may be identified with the sequence $(x_n)$.

Now suppose we have a strictly increasing sequence of natural numbers $n_1<n_2<n_3<\cdots$, and consider the subsequence $(y_k)_{k\in\N}$ given by $y_k=x_{n_k}\;(k\in\N)$. Now we wish to take a subsequence of $(y_k)$. One traditional approach is to take a new strictly increasing sequence of natural numbers $k_1<k_2<k_3<\cdots$, and then consider the subsequence of $(y_k)$ given by

$y_{k_1},y_{k_2},y_{k_3},\dots$.

Note that there is no reason to expect any connection between the sequences $n_1,n_2,n_3,\dots$ and $k_1,k_2,k_3,\dots$. So it is important to use different notation for these two sequences.

Now, for each $l\in\N$, set $\displaystyle z_l=y_{k_l}=x_{n_{k_l}}\,.$

Certainly $(z_l)_{l\in\N}$ is a subsequence of $(y_k)_{k\in\N}$ and so  $(z_l)_{l\in\N}$ is a subsubsequence of $(x_n)_{n\in\N}$. (Moreover, every subsubsequence of $(x_n)$ has this form, for suitable choices of the strictly increasing sequences of natural numbers $(n_k)_{k\in\N}$ and $(k_l)_{l\in\N}$.)

The notation becomes a bit unwieldy here: it is already hard to read the notation $x_{n_{k_l}}$, so if we extract further subsequences of our subsubsequences it may get messy. However we can already check at least that $(z_l)_{l\in\N}$ really is a subsequence of the original sequence $(x_n)$.

To see this note that $(z_l)$ is the sequence $x_{n_{k_1}}, x_{n_{k_2}},x_{n_{k_3}},\dots$ and we do have

$n_{k_1}<n_{k_2}<n_{k_3}<\cdots\,$

because $(n_k)$ is strictly increasing, and $k_1<k_2<k_3<\cdots$.

Just to tighten this up, we may set  $m_l=n_{k_l}\;(l\in\N)$, and then we have $m_1<m_2<\cdots$ and $(z_l)$ is the subsequence $x_{m_1},x_{m_2},x_{m_3},\dots$ of $(x_n)$. We also have $z_l=x_{m_l}\;(l\in\N)$ and $(z_l)_{l\in\N} = (x_{m_l})_{l\in\N}.$

There is nothing wrong with that! But let us check this via our other approaches to this situation.

In terms of functions, we set $f(n)=x_n \;(n\in\N)$, $g(k)=n_k\;(k\in\N)$ and $h(l)=k_l\;(l\in\n)$, so that $g$ and $h$ are strictly increasing functions from $\N$ to $\N$, and $f:\N\to X$ is the function that we identify with the original sequence $(x_n)$. Then the sequence $(y_k)$ is identified with the function $f\circ g$, and the sequence $(z_l)$ is identified with the function $(f\circ g) \circ h$. But function composition is associative, so $(f\circ g) \circ h = f\circ (g\circ h)$. Set $G= g\circ h:\N\to\N$. This is the composition of two strictly increasing functions from $\N$ to $\N$, and so $G$ is another such function. Finally, $(z_l)$ is identified with the function $f\circ G:\N\to X$, and this is a subsequence of $(x_n)$ as claimed.

OK, but perhaps the nicest approach is to work with the corresponding infinite subsets of $\N$.

Set $A_0=\N$. Then, following our notation above, we may write $(x_n)=(x_n)_{n\in A_0}$.

Now consider the set $A_1=g(\N)=\{n_1,n_2,n_3,\dots\} \subseteq \N=A_0$. Then we have $(y_k)=(x_n)_{n\in A_1}$.

Set $B_1=\{k_1,k_2,\dots\}=h(\N)\subseteq \N$. Then $(z_l)$ is the subsequence $(y_k)_{k\in B_1}$ of $(y_k)$.

Finally, set $A_2=\{n_{k_1},n_{k_2},n_{k_3},\dots\} = g(h(\N)) = g(B_1) \subseteq g(\N)=A_1$. Then $(z_l)$ is the subsequence $(x_n)_{n\in A_2}$ of $(x_n)$.

We can now see that if we extract further subsequences, we will end up with a nested decreasing chain $A_0\supseteq A_1 \supseteq A_2 \supseteq \cdots$  of infinite subsets of $\N$. We will return to this in Part IV, which will include a look at the more advanced notion of a "diagonal subsequence" obtained from repeatedly taking subsequences of subsequences etc.

One final note here. Because every sequence is a subsequence of itself, the sequence $(y_k)$ is itself a subsubsequence of $(x_n)$. So not only is every subsubsequence of $(x_n)$ a subsequence of $(x_n)$, but also every subsequence of $(x_n)$ is a subsubsequence of $(x_n)$!