# Constructing a convergent subsequence

Let $a_{mn}$ be a double sequence in $[0,1]$. I would like to know whether I can do the following operation.

1. I start with a sequence $a_{m1}$ and construct a convergent subsequence $a_{m'1}$.

2. Then consider a sequence $a_{m'2}$ and construct a convergent subsequence $a_{m''2}$.

3. Continuing this operation for all $n=1,2,...$ and renaming, construct a subsequence ${m^*}$.

4. Then, on this sequence $m^*$, consider a sequence $a_{11},a_{12},...$ and construct a convergent subsequence $a_{1n'}$.

5. Proceeding as in Step 2 and 3, construct a subsequence ${m^*n^*}$.

6. Then the claim is that on ${m^*n^*}$, for each $m=1,...$, ${a_{m1},...}$ is convergent and for each $n$, ${a_{1n},...}$ is convergent.

That is, is it possible to construct a subsequence of a double sequence that is convergent for each index?

-
I meant: if the indices in the first step is 1,3,5,7,..., then, in the second step, choose a convergent subsequence from 1,3,5,7,... Does it make sense? – Wholefoods Nov 26 '11 at 14:44
I meant: for $k=1$, I obtain indices $A(1)$. For $k=2$, I choose indices $A(2)$ from $A(1)$. For $k=3$, I choose indices $A(3)$ from $A(2)$. – Wholefoods Nov 26 '11 at 14:50

NOTE: Brian's answer has been already posted before mine. But I think I'll leave my answer too - for some people viewing the problem as a problem about the topological space $[0,1]^{\mathbb N}$ might be useful. (Second part of my answer is similar to Brian's but I think his answer is more clear.)

I'll consider the following question: Given a double sequence $(a_{m,n})_{m,n\in\mathbb N}$ in $[0,1]$, is it possible to choose $(n_k)_{k\in\mathbb N}$ such that each row $(a_{m,n_k})_{k=1}^\infty$ converges, i.e. there exists limit $L_k=\lim\limits_{k\to\infty} a_{m,n_k}$ for each $m$.

If this is true, it answers your question, since you can use it for rows first and then apply the same result on the chosen sequence for columns. However, I will describe an approach different from the construction suggested in your post.

I'll describe my solution in two possible ways. You may choose whichever is more understandable for you.

First, let us have a look at this problem from the viewpoint of general topology. We can consider the double sequence $(a_{m,n})$ as a sequence $(a^{(n)})$ of elements of $[0,1]^{\mathbb N}$. Note that this space consists of all functions $\mathbb N \to [0,1]$ and we work with the functions $a^{(n)}: \mathbb N \to [0,1]$. $$a^{(n)}(m)=a_{m,n}$$ We consider the usual product topology on this space. Hence it is a compact metrizable space.

Compact metrizable space is sequentially compact, hence there exists a subsequence $a^{(n_k)}$ which is convergent in $[0,1]^{\mathbb N}$ to some $L$. Since convergence in the product topology is precisely the pointwise convergence, this means that for each $m\in\mathbb N$ $$\lim_{k\to\infty} a^{(n_k)}(m) =\lim_{k\to\infty} a_{m,n_k} = L(k).$$ I.e., all rows are convergent.

A more constructive approach (which is basically the same as above, we simply mimic the proof of Bolzano-Weierstrass theorem) would be the following. I will just sketch the construction - I hope you'll be able to fill in the details.

First we divide $[0,1]=[0,1/2]\cup[1/2,1]$. One of the sets $\{n\in\mathbb N; a_{1n}\in [0,1/2]\}$ and $\{n\in\mathbb N; a_{1n}\in [1/2,1]\}$ is infinite. Denote this set by $A_1$, the corresponding interval by $I^{(1)}_1$. For $m>1$ put $I^{(m)}_1=[0,1]$. Choose any $n_1\in A_1$.

In the $k$-th step suppose that we already have $n_1<n_2<\ldots<n_k$ and some intervals $I^{(1)}_k, \dots, I^{(k)}_k$. For any $m>k$ we have $I^{(m)}_k=[0,1]$. We will construct $n_{k+1}$ and $k+1$-th intervals in the following way:

Divide each of the intervals $I^{(1)}_k, \dots, I^{(k+1)}_k$ into two halves. For any choice of half-intervals $J_1,\dots,J_{k+1}$ we get some set $\{n\in\mathbb N; a_{1n}\in J_1, \ldots, a_{k+1,n}\in J_{k+1}\}$. Since we have only finitely many sets (namely $2^{k+1}$), one of them must be infinite. We choose any such set and denote it by $A_{k+1}$. The corresponding half-intervals are chosen for $I^{(1)}_{k+1}, \dots, I^{(k+1)}_{k+1}$. The new index $n_{k+1}$ is chosen as an arbitrary element of $A_{k+1}$ that is larger than $n_k$.

In this way we construct a sequence $n_k$ such that $a_{m,n_k}$ converges for each $m$. (Notice that $a_{m,n_k}\in I^{(m)}_k$ and the length of the nested intervals $I^{(m)}_k$ decreases to 0. Thus $a_{m,n_k}$ converges to the unique point in the intersection of these intervals.)

-
How does this construction generalizes if the sequence comes not form $[0,1]$ but from some compact sets? – Wholefoods Nov 26 '11 at 16:36
If $X$ is compact metrizable then the whole "topological" argument works in the same way for the space $X^{\mathbb N}$ instead of $[0,1]^{\mathbb N}$. Since product of countable many sequentially compact spaces is sequentially compact, the same should work for $X$ being arbitrary sequentially compact space. However, this reasoning is kin of circular, since the usual proof that of this fact is similar to the argument from Brian's post. – Martin Sleziak Nov 26 '11 at 16:43

As Martin pointed out, your construction does not work as described. Here’s a concrete example of the difficulty that he was describing.

Let $a_{m,n}=1$ if $m=2^nk$ for some integer $k$, and otherwise let $a_{m,n}=0$. At step 1 you could choose the subsequence $\langle a_{2,1},a_{4,1},a_{6,1}\dots\rangle$, which converges to $1$. Then you could choose $\langle a_{4,2},a_{8,2},a_{12,2},\dots\rangle$ at step 2; if also converges to $1$. At step 3 you could choose $\langle a_{8k,3}:k\in\mathbb{Z}^+\rangle$, $\langle a_{2^4k,4}:k\in\mathbb{Z}^+\rangle$, and in general $\langle a_{2^nk,n}:k\in\mathbb{Z}^+\rangle$. The original set of first indices is $\{1,2,3,\dots\}$; at the first step this is reduced to $\{2,4,6,\dots\}$, at the second to $\{4,8,12,\dots\}$, then to $\{8,16,24,\dots\}$, then $\{16,32,48,\dots\}$, and so on: after $k$ steps only the multiples of $2^k$ are left. Thus, there is no $m$ that appears in the subsequence at every stage. After all of the subsequences have been taken, there is nothing left to rearrange.

What you can do instead is this. Let $A_1$ be the set of first indices for the first subsequence, $A_2$ for the second, and so on. In the example above, $A_1=\{2,4,6,\dots\}$, $A_2=\{4,8,12,\dots\}$, and so on. Now let $m_1$ be the smallest element of $A_1$. If you’ve already chosen some $m_k$, let $m_{k+1}$ be the smallest element of $A_1\cap A_2\cap\dots\cap A_k\cap A_{k+1}$ that is greater than $m_k$. In this way you construct an increasing sequence $\langle m_1,m_2,m_3,\dots\rangle$ such that for each $n$ and $k$, $m_k\in A_n$ whenever $k\ge n$. In other words, for every $n$, all but finitely many of the $m_k$ belong to $A_n$. This ensures that if $\langle a_{m,n}:m\in A_n\rangle$ converges, so does $\langle a_{m_k,n}:k\in\mathbb{Z}^+\rangle$, and to the same limit. The sequence $\langle m_1,m_2,m_3,\dots\rangle$ is your $m^*$ sequence. (In the example above it would be $\langle 2,4,8,16,\dots\rangle$, the sequence of powers of $2$.)

Now repeat the process on the second index, and you’ll have the subsequence that is convergent in each index separately.

-
Thank you for your answer. – Wholefoods Nov 26 '11 at 16:37

As I read the question, you start with an infinite matrix of real numbers from $[0,1]$. For every row in succession you select an infinite subset of the remaining columns, throwing out the rest, in such a way that the row becomes convergent which is possible by the Bolzano–Weierstrass theorem (and previous rows, which were already convergent, remain so with the same limit). Then after having done all rows (you have deserved a minute break, after all this was quite some work), you continue similarly for the columns, throwing out entire rows (too bad they were made convergent, which is now wasted effort). Your question: is this a valid way to make all rows and columns convergent?

First remark, your procedure is flawed, since there is no guarantee that anything will be left after step 3. Imagine that for every row, you throw out the first remaining column, among possible other ones. Then it is easy to see that every entry of you matrix is cast out at some point, and nothing is left in the end. You can get yourself out of this trap by stating that when coming to row $i$, the first $i$ columns have become untouchable. This does not cause any problem with convergence, since convergence is independent of any finite initial sequence. Then the first $n$ columns are frozen beyond the treatment of row $n$ in the first round, which means that there is a well defined end result of that round.

A similar remark applies to the second round that makes columns convergent while throwing out rows. Since only entire rows are thrown out, the remaining ones will all be convergent, as will be all the columns at the end of the second round. If that was your goal, it can be achieved.

But one final remark, don't be misled into believing that one can say anything about the limits of the rows and the columns (other than that each of them lies in $[0,1]$). For any pair of sequences of values in $[0,1]$ (for instance all $0$'s for the first sequence and all $1$'s for the second), you can find an infinite matrix whose rows converge respectively to the first list of values, and whose columns converge to the second list of values. Just choose the values above the main diagonal equal to the limit for their row, and those below the diagonal to the limit for their column (you can also just make them approach the limit, if you like to keep some suspense). (On the main diagonal you can toss a coin if you like, showing that diagonals need not converge.)

-
How does it relate to Brian's answer? – Wholefoods Nov 26 '11 at 16:38
Basically we say the same thing, although I used fewer indices to say it (in fact none at all). The number $m_k$ is the index of the column that becomes untouchable when row $k$ is considered. In the end every column that survives has become untouchable at some point, in a sense it survives because it has become untouchable. That is why in Brian's answer the sequence $m_1,m_2,m_3,\ldots$ is all that remains of the sequence of sets $(A_i)_{i>0}$. – Marc van Leeuwen Nov 26 '11 at 20:01