# Is it possible to choose a subsequence countable times in ZF?

Rudin PMA p.157

I'm trying to prove;

"If $\{f_n\}$ is a pointwise bounded sequence of complex functions on a countable set $E$, then $\{f_n\}$ has a subsequence $\{f_{n_k}\}$ such that $\{f_{n_k}\}$ pointwise convergent on $E$"

It's clear that Rudin made dependent choice.

I'm trying to prove this withouc AC and want to know if there is a way to choose a subsequence of a sequence. That is when $\{n\}$ is a given sequence, then i want to choose a subsequence $\{n_k\}$, then again choose a subsequence of $\{n_{k_j}\}$ and again countable times.

Is it possible?

Or if one can prove this with a different argument, Or if it is unprovable, please let me know..

-
In other words: How much choice is needed for Tychonoff's theorem for a countable product of closed and bounded subsets of $\mathbb{C}$? – Nate Eldredge Dec 15 '12 at 15:33
@Nate Yes exactly – Katlus Dec 15 '12 at 15:37
It seems to me the key is: given a bounded sequence $\{a_n\}$ (say in [0,1] for simplicity) can we canonically choose a convergent subsequence? Here's a proposal: the set of subsequential limits of $\{a_n\}$ is closed and bounded, hence has a minimum element $a$. (So we canonically chose a subsequential limit.) Now choose the subsequence: let $n(k)$ be the least $n$ with $|a_n - a| < 1/k$. Then $a_{n(k)} \to a$. – Nate Eldredge Dec 15 '12 at 15:41
Oh wait: "the set of subsequential limits is closed": we have to be a little careful not to use choice in proving this. – Nate Eldredge Dec 15 '12 at 15:45
@TonyK: That is easily repaired, though: The $n$th time you choose a nested subsequence to restrict to, decide always to keep the first $n$ points in the previous sequence unchanged. This will not change the limit of the subsequence you restrict to, and the eventual nest of subsequences is guaranteed to have infinite intersection. – Henning Makholm Dec 15 '12 at 16:42

The answer is yes, here is a proof:

• Every bounded sequence $\{x_n\}$ in $\mathbb{R}$ has a limit point.

Suppose not,let $K$ be a compact set containing the sequence, then $\{x_n\}$ must be infinite;no AC needed to prove this, thus for each $k\in{K}$ define $s(k)$ where $s(k)$ is the least positive integer $n$ such that $(B_{1/n}(k)-\{k\})\cap{\{x_n\}}=\emptyset$, then $\{B_{\frac{1}{s(k)}}(k)\}_{k\in{K}}$ is an open covering of $K$ with no finite subcover, since $\{x_n\}$ is infinite.

• For every bounded sequence $\{x_n\}$ there exists a uniquely determined converging subsequence $\{f(\{x_n\})_m\}_{m\in{\mathbb{N}}}$ of $\{x_n\}$.

Let $E$ be the set of limit points of $\{x_n\}$, then $E$ is a bounded set since our sequence is bounded, let $a=infE$; $a$ exixts since $E$ is nonempty by what it was shown above, then every neighborhood of $a$ intersects the sequence; this is easily seen without using AC, then for each $m>0$ let $k(0)=0$ and for each $n$ let $k(m+1))$ be the least positive integer $r$ greater than all of $k(0),\ldots,k(m)$ and such that $|a-x_r|<\frac{1}{m+1}$. Define $f(\{x_n\})_m=x_{k(m)}$ for all $m\in{\mathbb{N}}$, it is clear that the series $\{f(\{x_n\})_m\}_{m\in{\mathbb{N}}}$ converges to $a$.

Now using the notation on page 157 in Rudin’s PMA define $S_0=\{x_n\}$, and for $m\in{\mathbb{N}}, S_{m+1}=f(S_m)$

-

Let's confine ourselves to Real-valued functions.

That is, let $\{f_n\}$ be a sequence of pointwise bounded functions on $E$ such that $f_n$ maps from $E$ to $\mathbb{R}$.

Let $x_i$ enumerate $E$.

Let $S_1 = \{n_k \subset \mathbb{N} \times \mathbb{N} : f_{n_k}(x_1) \rightarrow \limsup_{n\to\infty} f_n(x_1) \}$

and $g_1:\omega \rightarrow \bigcup_{n_k \in S_1} rng(n_k)$ be the isomorphism.

$S_{i+1} = \{g_{i_{n_k}} \subset \mathbb{N} \times \mathbb{N} : f_{g_{i_{n_k}}}(x_{i+1}) \rightarrow \limsup_{n\to\infty} f_{g_{i_n}}(x_{i+1}) \}$

and $g_{i+1}:\omega \rightarrow \bigcup_{g_{i_{n_k}}\in S_{i+1}} rng(g_{i_{n_k}})$ be the isomorphism.

(Note that $S_i$ is nonempty and well-defined since $f_n$ is pointwise bounded on $E$)

By induction, $\{g_i\}$ is well defined and $g_{i+1}$ is a subsequence of $g_i$.

Define $h(n)=g_n(n)$ for all $n\in \mathbb{N}$

Then for any $i\in\mathbb{N}$, $f_{h(n)}(x_i)$ is convergent. Q.E.D.

This can be extended to $\mathbb{R}^k$.

-