# Rudin's proof theorem 7.23

I'm totally lost on that proof. Recall, the theorem is the following:

If $(f_n)_{n \in \mathbb{N}}$ is a pointwise bounded sequence of complex functions on a countable set $E$, then $(f_n)_{n \in \mathbb{N}}$ has a subsequence $(f_{n_k})_{k \in \mathbb{N}}$ such that $(f_{n_k}(x))_{k \in \mathbb{N}}$ converges for each $x \in E$.

I understand the beginning of the proof, i.e. defining $f_{1, k}$ a subsequence of functions s.t. $\lim_{k \rightarrow + \infty}f_{1, k}(x_1)$ exists. But once he defines his matrix of functions, I can't understand the reasons of the properties he mentioned.

Recall:

\begin{matrix} S_1: & f_{1, 1} & f_{1, 2} & \ldots \\ S_2: & f_{2, 1} & f_{2, 2} & \ldots \\ \vdots \\ S_n: & f_{n, 1} & f_{n, 2} & \ldots \\ \end{matrix}

Why $S_n$ should be a subsequence of $S_{n-1}$? I can't get the point...

Thanks,

• Are you asking why we demand that $S_n$ be a subsequence of $S_{n-1}$? We want a subsequence that converges at all $x_k$. Choosing $S_n$ as a subsequence of $S_{n-1}$ ensures that this sequence converges at all $x_k$ for $k \leqslant n$, so it is (in some sense) an approximation to our goal. A better approximation than $S_{n-1}$. And that allows us to finally reach our goal by taking the diagonal sequence. Sep 18, 2015 at 13:55
• Oh, maybe I didn't understand. I guess that "by construction" he sets that $S_n \subset S_{n-1}$. Thus, a legitimate question is: is it possible to create such sequences? Sep 18, 2015 at 14:00
• Yes, it's possible. You repeatedly use the Bolzano-Weierstraß theorem to extract a subsequence $S_n$ from $S_{n-1}$ such that $f_{n,k}(x_n)$ converges. Sep 18, 2015 at 14:18
• @DanielFischer Assuming I have not misunderstood your comment, I found it extraordinarily helpful! I posted an answer based on your suggestion. Dec 22, 2019 at 20:51

It is entirely possible to create such sequences. As to the reason, here it is.

Consider the sequence

$f_{1,1}(x_2),f_{1,2}(x_2),\ldots$

This is a bounded sequence since the functions are pointwise bounded.

Thus, it contains a convergent subsequence, $f_{1,n_i}(x_2)$

This subsequence of functions, we denote by $f_{2,i}$.

You can go through such a process repeatedly to get $S_n\subset S_{n-1}$ with the required properties.

• We cannot consider the sequence like $f_{1,1}(x_2),f_{1,2}(x_2),\ldots$ for it would go off the approach given in the proof. In the proof, the author only consider the sequence like $\{f_{1,k}(x)\}=\{f_{1,1}(x_1),f_{1,2}(x_1),\ldots\}$ which converges at $x_1$ as $k\to\infty$. Sep 6, 2022 at 11:29

I see this is an old post. But if I am still looking at it, then probably someone else is, too. I'm not a fan of Rudin's notation in this one. I think it adds confusion, not clarity. However, I really like Daniel Fischer's comment. The proof is as follows.

# Proof

Let $$A$$ be a countably infinite set. Let $$(f_n)$$ be a sequence of mappings $$A\to\mathbb{C}.$$ Thus, by definition of countably infinite, consider an enumeration $$a_1,a_2,\ldots$$ of $$A$$. Assume that $$(f_n)$$ is point-wise bounded (i.e., the sequence $$f_1(a_n), f_2(a_n),\ldots$$ in $$\mathbb{C}$$ is bounded for each given $$n\in\mathbb{Z}^+$$). In particular, the sequence of complex numbers $$(f_n(a_1))$$ is bounded. Hence, by the Bolzano-Weierstrass theorem, there exists a convergent sub-sequence. $$(f_{n_k}(a_1))$$. Consider this sub-sequence. Now, we have a sequence of functions $$(f_{n_k})$$ which is convergent when "evaluated at" $$a_1$$. However, it may still be evaluated at other points. In particular, it is reasonably clear that a sub-sequence of a point-wise bounded sequence of functions is, itself, a point-wise bounded sequence of functions. Thus, the sequence of complex numbers $$(f_{n_k}(a_2))$$ is bounded, so that there again exists a convergent sub-sequence $$(f_{n_{k_m}}(a_2))$$. Consider this sub-sequence.

The crucial logical step is that not only does the sequence of complex numbers $$(f_{n_{k_m}}(a_2))$$ converge, but also the sequence $$(f_{n_{k_m}}(a_1))$$ converges since it is a sub-sequence of the convergent sequence $$(f_{n_k}(a_1))$$! So, at this point in our informal construction, we have already identified a sub-sequence $$(f_{n_{k_m}})$$ of $$(f_n)$$ which converges evaluated at, not one, but two points $$a_1,a_2 \in A$$. The idea is, thus, to (implicitly, I think, use the axiom of choice to) extend this iterative construction ad infinitum.

The technical details of infinite recursive constructions are a subject in their own right. However, we (following Rudin) are typically not shy about taking for granted that these constructions are non-problematic. So, let us simply "continue in this way" without end, and take the sub-sequence $$f_{ n_{ \scriptstyle{k}_{ \scriptstyle{\ell}_{ ._{._{._{.}}} } } } }$$ which results from this construction as evidence of the asserted existence statement.

Since $$E$$ is countable, we can rearrange $$E = \{x_i\}_{i=1}^{\infty}$$. Fix $$x_1$$. Then $$\{f_n(x_1)\}$$ is a bounded sequence, since $$\{f_n\}$$ is pointwise bounded. Thus, it has a subsequence $$\{f_{n_k}(x_1)\}$$ that is convergent. In addition, consider the sequence of functions $$\{f_{n_k}\}$$. Itself is also a pointwise bounded sequence. Thus, if we evaluate $$\{f_{n_k}\}$$ at another point say $$x_2\in E$$. Then $$\{f_{n_k}(x_2)\}$$ is also a bounded sequence, so that it has another convergent subsequence $$\{f_{n_{k_\ell}}(x_2) \}$$ of the subsequence $$\{f_{n_k}(x_2)\}$$. Therefore, $$\{f_{n_{k_\ell}}\}$$ is not only convergent sequence when evaluating at $$x_2$$ but also a subsequence of $$\{f_{n_k}\}$$. Note that since $$\{f_{n_k}(x_1)\}$$ is convergent, then every subsequence of $$\{f_{n_k}(x_1)\}$$ is convergent. Therefore, $$\{f_{n_{k_\ell}}(x_1)\}$$ is also convergent. Let $$S_1 = \{f_{n_k}(x_1)\}$$ and $$S_2 = \{f_{n_{k_\ell}}(x_2)\}$$ and so on.

Imagine you sit beside a table with a stack of plates $\{f_n\}$. You look at $x_1$ then look at your stack of plates and throw away those plates that do not fit well with $x_1$.

You label this stack $f_{1,k}$. Index 1 means it is for $x_1$.

Then you look at point $x_2$. You take the stack you have from step 1, which is $f_{1,k}$. These are plates that remained after you threw away redundant ones. Again, you look at $x_2$ and at your stack, and throw away the plates that do not fit with $x_2$. And name this stack $\{f_{2,k}\}$

The points $x_1, x_2 \dots$ are countable, i.e. you may move from one to the next in discrete steps, one by one. Initial stack of plates, i.e. functions, is infinite, so you may enjoy your process for as long as you like.

One last bit.

The last paragraph of the proof says that the sequence $S$ is a subsequence of $S_n$ except for, possibly, its first $n-1$ terms.

What it means is that, on the one hand, ultimately we have constructed sequence $S$. On the other hand, we have rows of array pictures below the second paragraph. As going down to the next lower row we may drop some functions, some functions (or plates) may be missing in subsequences placed in lower rows.

In other words, there may be some functions in previous rows $n-1$ that we dropped while arriving at row $S_n$.

Yes, analogy from a totally different field. This process resembles "feeding" the values you get from a generator function (e.g. in Python programming language) for $x_1$ into a generator function $x_2$ etc. You feed one pipe of results into the next pipe and so on.

In considering the sequences $$S_1,S_2,S_3, \dots$$, the following three properties are assumed.

(a) $$S_n$$ is a subsequence of $$S_{n-1}$$, for $$n=2,3,4,\dots\$$.

(b) $$\{f_{n,k}(x_n)\}$$ converges as $$k\to\infty$$ (the boundedness of $$\{f_n(x_n)\}$$ makes it possible to choose $$S_n$$ in this way);

(c) The order in which the functions appear is the same in each sequence; i.e., if one function precedes another in $$S_1$$, they are in the same relation in every $$S_n$$ , until one or the other is deleted. Hence, when going from one row in the above array to the next below, functions may move to the left but never to the right.

By (a), we know that every sequence $$S_n, n\ge 2$$ is a subsequence of $$S_1$$ and

By (b), we know that $$S_n$$ guarantees that $$\{f_{n,k}(x_n)\}$$ converges as $$k\to\infty$$ for $$n=1,2,3,\dots\$$.

According to (a), the array of $$f_{i,j}, i,j=1,2,3,\dots$$ can be ordered and the property (c) gives the method of how to order the entries.

To order the entries $$f_{i,j}$$, according to (c), we starts from $$f_{1,1}$$ and go down to the left and continue until we reach the left most entry, then we go back to the first row, starts from $$f_{1,2}$$ and go down to the left and continue until we reach the left most entry, then we go back to the first row, starts from $$f_{1,3}$$ and go down to the left and continue until we reach the left most entry and repeat our procedure for the remaining entries as shown in the following diagram.

In this way, we have ordered the entries as follows. $$f_{1,1}\preccurlyeq f_{1,2}\preccurlyeq f_{2,1}\preccurlyeq f_{1,3}\preccurlyeq f_{2,2}\preccurlyeq f_{3,1}\preccurlyeq f_{1,4}\preccurlyeq f_{2,3}\preccurlyeq f_{3,2}\preccurlyeq f_{4,1}\preccurlyeq f_{1,5}\preccurlyeq f_{2,4}\preccurlyeq f_{3,3}\dots .$$ We now go down the diagonal of the array; i.e., we consider the sequence $$S:f_{1,1}\;f_{2,2}\;f_{3,3}\;f_{4,4}\;f_{5,5}\dots\ .$$ By (c), we know that

(i) $$f_{1,1}\;f_{2,2}\;f_{3,3}\;f_{4,4}\;f_{5,5}\dots$$ is a subsequence of $$S_1$$ so (b) implies that $$f_{n,n}(x_1)\to\infty$$ as $$n\to\infty$$,

(ii) $$f_{2,2}\;f_{3,3}\;f_{4,4}\;f_{5,5}\dots$$ is a subsequence of $$S_2$$ so (b) implies that $$f_{n,n}(x_2)\to\infty$$ as $$n\to\infty$$,

(iii) $$f_{3,3}\;f_{4,4}\;f_{5,5}\dots$$ is a subsequence of $$S_3$$ so (b) implies that $$f_{n,n}(x_3)\to\infty$$ as $$n\to\infty$$, and so on.

Thus, we can say that the sequence $$S$$ (except possibly its first $$n-1$$ terms) is a subsequence of $$S_n$$, for $$n = 1, 2, 3, \dots\$$ so that $$f_{n,n}(x_n)\to\infty$$ as $$n\to\infty$$.

Hence, we conclude that $$\{f_{n,n}(x_i)\}$$ converges, as $$n\to\infty$$, for every $$x_i\in E$$.