# Understanding Arzelà–Ascoli theorem

I am going through AA theorem and its proof as per wikipedia : http://en.wikipedia.org/wiki/Arzel%C3%A0%E2%80%93Ascoli_theorem, I am not able to understand clearly the formation of diagonal subsequence which converges to rational point . Anyone interested in making it less elusive ?

-
I assume you want to say "...less elusive.". –  Matt N. Apr 26 '12 at 14:59
Do you mean "in making it less elusive"? –  Giuseppe Tortorella Apr 26 '12 at 15:00
yes, I have edited ! –  Theorem Apr 26 '12 at 15:02
You could start help yourself by trying to say us what do you understand and where are you stuck. Try! –  Giuseppe Tortorella Apr 26 '12 at 15:03
How do you form a chain of subsequence, as stated in the proof . I can't understand why every former subsequence should contain the subsequent subsequences ? Oh god i have to learn latex. –  Theorem Apr 26 '12 at 15:11
show 1 more comment

Let be given $(x_n)_{n\in\mathbb{N}}$ and $(y_n)_{n\in\mathbb{N}}$ sequences of natural numbers.
By definition we say that the second sequence is a subsequence of the second one when there exists $(k_n)_{n\in\mathbb{N}},$ a strictly increasing sequence of natural numbers such that $x_{k_n}=y_n$ for any $n.$
When the two sequences are both strictly increasing, the previously condition is verified if and only if $\{x_n|n\in\mathbb{N}\}\supseteq\{y_n|n\in\mathbb{N}\}.$

And this is exactly our situation.
Infact the final sequence $(k_n)_{n\in\mathbb{N}}$, the one constructed applying the diagonal process to the sequence of sequences $(k_n^{(i)})_{n\in\mathbb{N}}$ (each one extracted by the previous one), has its $n$-th element coming from the $n$-th sequence (precisely $k_n=k_n^{(n)}.$)
So $(x_n)_{n\ge i}$ is a subsequence of $(x^{(i)}_n)_{n\in\mathbb{N}}.$

-

I think your main doubts have already been clarified in the comments and previous answer, but I still would like to add something which helped me grasp one of the subtler details of the proof when I came across this theorem for the first time.

The single extractions of subsequences are easily justifyable using Bolzano - Weierstrass, and using induction you would be able to justify extracting an arbitrarily large but finite number of subsequences of functions. This however isn't good enough, because your diagonal subsequence would only contain a finite number of terms, and not be much of a sequence at all. You need to iterate an infinite number of extractions of subsequances, and induction is no longer useful here. You need something to justify this construction.

It turns out that what is used here (and this is often ommitted in proofs, although the proof on Wikipedia mentions it) is a weaker version of the Axiom of Choice: the Axiom of Dependent Choice. Usually the full Axiom of Choice is allowed in Real Analysis, so using it, or weaker forms of it is fine, but you do need to mention it in the proof, since there is nothing obvious guaranteeing the existence of the diagonal subsequence.
What the Axiom of DC states is that, given a set $X$ (in our case $X$ can be taken to be the set of all possible subsequences of $f_n$) and a binary relation $\mathfrak{R}$ on $X$ such that for each element of $u \in X$ there exists $v \in X : u \mathfrak{R} v$ , there exists an sequence of elements $u_n \in X$ such that $u_n \mathfrak{R} u_{n+1}$ for all $n \in \mathbb{N}$. Now, let $f_n ^a$ and $f_n^b$ be subsequences of $f_n$, and if $f_n ^a (x_i)$ doesn't converge for all the rationals $x_i$ define $k = \max \{ i : f_n ^a(x_i) \ \text{converges} \ \forall j \leq i \}$. Take $f_n ^a \mathfrak{R} f_n ^b$ iff $f_n ^a (x_i)$ converges $\forall i \in \mathbb{N}$ and $f_n ^a = f_n ^b$, OR if $f_n ^a (x_i)$ doesn't converge for every $i$ (and therefore $k \in \mathbb{N}$ is well defined) and if $f_n ^b$ is a subsequence of $f_n ^a$ and $f_n^b(x_{k+1})$ converges. You can see that, by Bolzano-Weierstrass, the only condition that we require for $\mathfrak{R}$ is satisfied, and thus the Axiom of DC guarantees that all the iterated subsequences $f_n ^k, k \in \mathbb{N}$ exist - not just the first trillion or so!

Now that the existence of the diagonal subsequence has been established, its property that is used in the rest of the proof is that it is definitively a subsequence of each of the iterated subsequences $f_n ^k$ (for $n \geq k$) and therefore it converges for all the rationals $x_i$.

This answer came out a bit longer than I had planned for it to be... I thought I would write this because Analysis textbooks and lecturers often skip details about the AC which have to be mentioned to make everything rigorous. I hope I got it right and that it helps.

-