# Does Arzelà-Ascoli require choice?

Inspired by a recent Math.SE question entitled Where do we need the axiom of choice in Riemannian geometry?, I was thinking of the Arzelà--Ascoli theorem. Let's state a very simple version:

Theorem. Let $\{f_n : [a,b] \to [0,1]\}$ be an equicontinuous sequence of functions. Then a subsequence $\{f_{n(i)}\}$ converges uniformly on $[a,b]$.

The proofs I have seen operate as follows: Take a countable dense subset $E$ of $[a,b]$. Use a "diagonalization argument" to find a subsequence converging pointwise on $E$. Use equicontinuity to conclude that this subsequence actually converges uniformly on $[a,b]$.

The "diagonalization" step goes like this: Enumerate $E$ as $x_1, x_2, \dots$. $\{f_n(x_1)\}$ is a sequence in $[0,1]$, hence has a convergent subsequence $\{f_{n_1(i)}(x_1)\}$. $\{f_{n_1(i)}(x_2)\}$ now has a convergent subsequence $\{f_{n_2(i)}(x_2)\}$, and so on. Then $\{f_{n_i(i)}\}$ converges at all points of $E$.

Of course, to do this, at each step $k$ we had to choose one of the (possibly uncountably many) convergent subsequences of $\{f_{n_{k-1}(i)}(x_k)\}$, so some sort of choice is needed here (I guess dependent choice is enough? I am not a set theorist (IANAST)). Indeed, we have proved that $[0,1]^E$ is sequentially compact (it is metrizable so it is also compact).

On the other hand, we have not used (equi)continuity in this step, so perhaps there is a clever way to make use of it to avoid needing a choice axiom.

So the question is this:

Can the Arzelà--Ascoli theorem be proved in ZF? If not, is it equivalent to DC or some similar choice axiom?

-
The above statement is horribly wrong---consider the sequence ${n}$ of constant functions. You need to add a boundedness condition to get a correct formulation. – priel Sep 12 '15 at 16:01
@priel: Note that I wrote $f_n : [a,b] \to [0,1]$, not $[a,b] \to \mathbb{R}$. So they're automatically bounded. – Nate Eldredge Sep 12 '15 at 16:30
Sorry about that. Read it too fast. Wish I could erase my comment. – priel Sep 12 '15 at 17:44
@priel: If you register your account, you can! – Nate Eldredge Sep 12 '15 at 17:52

There is a canonical way of checking the literature for most questions of this kind. Since they come up with some frequency, I think having the reference here may be useful.

First, look at "Consequences of the Axiom of Choice" by Paul Howard and Jean E. Rubin, Mathematical Surveys and Monographs, vol 59, AMS, (1998).

If the question is not there, but has been studied, there is a fair chance that it is in the database of the book that is maintained online, http://consequences.emich.edu/conseq.htm

Typing "Ascola" on the last entry at the page just linked, tells me this is form 94 Q. Note the statement they provide is usually called the classical Ascoli theorem:

For any set $F$ of continuous functions from ${\mathbb R}$ to ${\mathbb R}$, the following conditions are equivalent:
1. Each sequence in $F$ has a subsequence that converges continuously to some continuous function (not necessarily in $F$ ).
2. (a) For each $x \in{\mathbb R}$ the set $F (x) =\{f (x) \mid f \in F \}$ is bounded, and
(b) $F$ is equicontinuous.

To see the other equivalent forms of entry 94, type "94" on the line immediately above.

From there we learn: Form 94 is "Every denumerable family of non-empty sets of reals has a choice function."

There are some other equivalent forms that may be of interest. For example:

• (94 E) Every second countable topological space is Lindelöf.
• (94 G) Every subset of ${\mathbb R}$ is separable.
• (94 R) Weak Determinacy. If $A$ is a subset of ${\mathbb N}^{\mathbb N}$ with the property that $\forall a \in A\forall x \in{\mathbb N}^{\mathbb N}($ if $x(n) = a(n)$ for $n = 0$ and $n$ odd, then $x\in A)$, then in the game $G(A)$ one of the two players has a winning strategy.
• (94 X) Every countable family of dense subsets of ${\mathbb R}$ has a choice function.

Proofs and references are provided by the website and the book. A reference that comes up with some frequency in form 94 is Rhineghost, Y. T. "The naturals are Lindelöf iff Ascoli holds". Categorical perspectives (Kent, OH, 1998), 191–196, Trends Math., Birkhäuser Boston, Boston, MA (2001).

-
By the way, the webpage they provide in the book is out of date, so you really need the link above. – Andrés E. Caicedo Nov 13 '10 at 16:04
That book and site look like fantastic references, especially for someone like me who is not an expert but often curious about AC. I think I know what I want for Christmas! :) – Nate Eldredge Nov 13 '10 at 16:20
The link is dead. Do you know if there is an alternative one? – Emil Jeřábek Jan 20 '15 at 20:36
Hi @François. It's been in my radar but I've been procrastinating about this. I'll look into it more seriously. – Andrés E. Caicedo Sep 13 '15 at 15:47
One can extract some of the data from web.archive.org/web/20061018025223/http://www.math.purdue.edu/… – David Roberts Sep 14 '15 at 1:12

I should mention that the theorem

Theorem. Let $\{f_n:[a,b] \to [0,1]\}$ be an equicontinuous sequence of functions. Then a subsequence $\{f_{n(i)}\}$ converges uniformly on $[a,b]$.

holds without any choice (for $a, b \in \mathbb R$). This is proven by using Heine-Cantor for equicontinuous sets and choosing the subsequence in a clever way (see http://arxiv.org/abs/1509.01078 for a proof with a compact subset of $\mathbb R^d$ instead of $[a, b]$; it's not quite short (7 pages), thus I refer to the paper).

The problematic direction is:

Theorem. Let $F \subset \mathcal C(C)$ be sequentially compact ($C \subset \mathbb R^d$ being a compact set). Then $F$ is bounded and equicontinuous.

That's what is equivalent to countable choice for subsets of the real numbers.

-
Hmm, this is surprising. It seems to me that using your Theorem, I could prove that $[0,1]^\omega$ is sequentially compact, and I was under the impression that this wasn't provable without some form of choice. I have to do some reading, I guess. – Nate Eldredge Sep 12 '15 at 14:49
Could you sketch a proof of "my theorem $\Rightarrow$ $[0, 1]^\omega$ is seq. compact"? – Cloudscape Sep 12 '15 at 14:55
I think you still need choice, because the additional point in "my theorem" is that the points "weigh" differently; in $[0,1]^\omega$ all the coordinates are equal w.r.t. the topology, but in Arzela-Ascoli they become weaker and weaker as the induction proceeds. – Cloudscape Sep 12 '15 at 14:59
I haven't thought out the details, but my idea was to identify $u \in [0,1]^\omega$ with a continuous function that maps $1/n$ to $u(n)/n$, perhaps in a piecewise linear fashion. It is entirely possible that I am missing something, so I should probably think it through before saying any more :-) – Nate Eldredge Sep 12 '15 at 15:01
Seems like a sensible idea! If my stuff is wrong, I want to know! I wouldn't like to spread wrong stuff, so I don't take it personally or something. The piecewise linear function should be Lipschitz continuous with Lipschitz constant $1$; this would give equicontinuity, and boundedness is clear. It remains to prove that convergence in the continuous functions implies convergence in $[0, 1]^\omega$. – Cloudscape Sep 12 '15 at 15:14