Sequences in metric spaces

[under construction]
Convergence of sequences
Sequences. A sequence in a metric space $X$ is a function $x:\N\to X$. In the usual notation for functions the value of the function $x$ at the integer $n$ is written $x(n)$, but whe we discuss sequences we will always write $x_n$ instead of $x(n)$.

For any sequence $x_n$ we can consider the set of values it attains, namely \[ \{x_n \mid n\in\N\} = \{y \mid y=x_n\text{ for some }n\in\N\}. \] It is important to distinguish this set from the sequence itself. For example, if $X=\R$, and $x_n=1$ for all $n\in\N$, then the sequence $x_n$ is $1, 1, 1, \dots$, i.e. an infinite sequence of ones. The set of values of this sequence is $\{1\}$, which is a subset of $\R$ with only one element.

Subsequences. A subsequence of a given sequence $x_n$ is any other sequence $y_k$ that is of the form $y_k = x_{n_k}$ where $n_k$ is an increasing sequence of natural numbers, i.e. \[ n_1 \lt n_2 \lt n_3 \lt \cdots\,. \] For instance, if $x_n = (-1)^n$, so $x_n$ is the sequence $-1, 1, -1, 1, \dots$ , then $y_k = x_{2k}$ is the subsequence that selects all even numbered entries in the sequence $x_n$. Thus $y_k$ is the constant sequence $1, 1, 1, 1, \dots$.

It will often be useful to realize that in an increasing sequence of natural numbers $n_k$ one always has $n_k\geq k$. This holds because the set $\{n_1, n_2, \dots, n_{k-1}, n_k\}$ consists of $k$ different natural numbers, all of which are less than or equal to $n_k$. This can only happen if $n_k\geq k$.

Definition of limit. A sequence of points $x_n$ in a metric space $X$ converges to a point $a\in X$ if for every $\varepsilon\gt0$ there is an $N_\varepsilon\in\N$ such that for all $n\ge N_\varepsilon$ one has $x_n \in B_\varepsilon(a)$.

We write $\lim_{n\to\infty} x_n =a$, or $x_n\to a$.

Examples in $\R^n$. Let $\bigl(x_i\bigr)_{i\in\N}$ be a sequence of points in $\R^n$. For each $i\in \N$ we will denote the coordinates of the point $x_i\in\R^n$ by $(x_{i1}, \dots, x_{in})$. The sequence of points $x_i\in\R^n$ ($i\in\N$) converges to $p\in\R^n$ if and only if each of the coordinates converges, i.e. if \[ \lim_{i\to\infty} x_{i1} = p_1, \quad \lim_{i\to\infty} x_{i2} = p_2, \quad \dots ,\quad \lim_{i\to\infty} x_{in} = p_n. \]

Proof. ////

For instance, consider the sequence of points $x_n = \bigl(\frac1n, \frac1{n^2}\bigr)$ in the plane. It follows from \[ \frac1n \to 0, \qquad \frac1{n^2}\to0, \] that $x_n\to (0,0)$ in $\R^2$.

Theorem on closed sets and limits of sequences. If $E\subset X$ is a closed subset of a metric space $X$, and if $x_i\in E$ is a sequence of points in $E$ which converges to $p\in X$, then $p\in E$.
Suppose $p\not\in E$. Since $E$ is closed, $X\setminus E$ is open and there is therefore an $\epsilon\gt0$ such that $B_\epsilon(p) \subset X\setminus E$. We also know that the sequence $x_i$ converges to $p$, so there is an $N_\epsilon\in\N$ for which $x_i\in B_\epsilon(p)$ holds for all $i\geq N_\epsilon$. This is a contradiction because $x_i\in E$ on one hand, and $x_i\in B_\epsilon(p)\subset X\setminus E$ on the other.
Theorem about subsequences. If $\{x_n\}_{n\in\N}$ is a sequence in a metric space $X$ with $x_n\to p$, and if $x_{n_k}$ is any subsequence, then $\lim_{k\to\infty} x_{n_k} = p$.

In other words, any subsequence of a convergent sequence also converges and has the same limit.

Proof. Let $\epsilon\gt0$ be given. Since $x_n\to p$ there exists an $N_\epsilon\in\N$ such that $x_n\in B_\epsilon(p)$ for all $n\geq N_\epsilon$. If $k\geq N_\epsilon$ then $n_k\geq k$, so that $n_k\geq N_\epsilon$, and thus $x_{n_k} \in B_\epsilon(p)$. This implies, by definition, that $x_{n_k}\to p$ as $k\to\infty$. ////

Example—proving a sequence does not converge by looking at its subsequences. The sequence $x_n=(-1)^n$ does not converge. To show this directly from the definition of convergence (i.e. to prove that for every $\ell\in\R$ it is not true that $x_n\to \ell$) is a bit awkward. Instead one can use the theorem above.

If the sequence $x_n$ converged to a limit, say $x_n\to\ell$, then every subsequence of $x_n$ would also converge to $\ell$. The sequence $x_n$ has the following subsequences \[ y_k = x_{2k}, \qquad z_k = x_{2k-1}. \] The sequence $y_{k}$ consists of all even entries, and, since $y_k=1$ for all $k\in\N$, we have $y_k\to 1$. If the sequence $x_n$ converges to some number $\ell$, then this number must be $\ell = +1$. On the other hand the subsequence $z_k = x_{2k-1} = -1$ converges to $-1$, so any limit of the sequence $x_n$ must be $\ell = -1$. The limit cannot be both $+1$ and $-1$ at the same time.

Theorem about monotone sequences. Let $x_n\in\R$ be a sequence of real numbers which is bounded and monotone. Then $\lim_{n\to\infty} x_n$ exists.

By definition, a sequence $x_n$ is called monotone if either $x_n\leq x_{n+1}$ holds for all $n\in\N$, in which case the sequence is called nondecreasing, or if $x_n\geq x_{n+1}$ for all $n\in\N$, in which case the sequence is said to be nonincreasing.

Assume that the sequence is nondecreasing, i.e. $x_1\leq x_2\leq x_3 \leq \cdots$ (the case of a nonincreasing sequence can be treated in the same way). Since the sequence is bounded, there is an $M\in\R$ such that $x_k\leq M$ for all $k\in\N$. Therefore the sequence has a least upper bound, i.e. \[ \alpha = \sup \{ x_n \mid n\in\N\} \] exists. We claim that $x_n\to\alpha$. To show this let $\epsilon \gt 0$ be given. Since $\alpha-\epsilon$ is not an upper bound for the $x_n$, there is an $N_\epsilon\in\N$ such that $x_{N_\epsilon} \gt \alpha-\epsilon$. The sequence is nondecreasing, so for all $n\ge N_\epsilon$ we also have $x_n\gt \alpha-\epsilon$. On the other hand $\alpha$ is an upper bound, so we have $x_n\leq \alpha$ for all $n\in\N$. It follows that for all $n\ge N_\epsilon$ we have $\alpha-\epsilon \lt x_n \le \alpha$, and thus $d(x_n, \alpha) \lt \epsilon$. This shows that $x_n\to\alpha$.
Compact subsets of a metric space
The Bolzano–Weierstrass theorem. Any bounded sequence of real numbers has a convergent subsequence. Any bounded sequence of points in $\R^n$ has a convergent subsequence.
Proof.  Let $(x_n)_{n\in\N}$ be a sequence of real numbers with $|x_n|\leq M$ for all $n\in\N$. Using induction we will construct a sequence of intervals $[a_k,b_k]\subset [-M, M]$ and a subsequence $\bigl(x_{n_k}\bigr)_{k\in\N}$.
The first step. For $n=1$ we set $a_1=-M$, $b_1=+M$, so that our first interval is $[a_1,b_1] = [-M, M]$. We choose $n_1 = 1$, so $x_{n_1} = x_1 \in [a_1, b_1]$. Moreover, there are infinitely many $n\in\N$ for which $x_n \in [a_1, b_1]$.
The induction step. Assume that we have already found $[a_k, b_k]$ such that $x_n\in[a_k, b_k]$ for infinitely many $n\in\N$. Now split the interval $[a_k, b_k]$ in two equal parts, $[a_k, c_k]$ and $[c_k, b_k]$, where $c_k= \frac12 (a_k+b_k)$. The sequence $(x_n)_{n\in\N}$ must visit at least one of these two intervals infinitely often. We define $[a_{k+1}, b_{k+1}]$ to be $[a_k, c_k]$ if $x_n\in[a_k, c_k]$ for infinitely many $n\in\N$; if $x_n\in[a_k, c_k]$ only holds for finitely many $n$, then $x_n$ must lie in $[c_k, b_k]$ for infinitely many $n\in\N$, and in this case we define $[a_{k+1}, b_{k+1}] = [c_k, b_k]$.
Picking a subsequence. We have a sequence of nested intervals \[ [-M, M] = [a_1, b_1] \supset [a_2, b_2] \supset [a_3, b_3] \supset \cdots \] where each interval is half as long as the previous interval, and such that the sequence $(x_n)_{n\in\N}$ visits each interval $[a_k, b_k]$ infinitely often. We can now define the convergent subsequence $x_{n_i}$: choose $n_1=1$. Then, since the sequence visits $[a_2, b_2]$ infinitely often, there is an $n_2\gt n_1$ such that $x_{n_2}\in [a_2, b_2]$. The sequence must also visit the next interval $[a_3, b_3]$ infinitely often, so there is an $n_3\gt n_2$ with $x_{n_3}\in[a_3, b_3]$. We now proceed by induction: having found $n_k$, we note that the sequence $x_n$ visits the interval $[a_{k+1}, b_{k+1}]$ infinitely often, and therefore there must be an $n_{k+1}\gt n_k$ for which $x_{n_{k+1}}\in[a_{k+1}, b_{k+1}]$.
Finding the limit. To complete the proof we show that $x_{n_k}$ converges after first identifying the limit of the $x_{n_k}$. The sequence $a_k$ is bounded from above by $b_1$, and therefore $\alpha = \sup \{a_k \mid k\in\N\}$ exists. We will show that $x_{n_k}\to\alpha$.
To prove this, let $\epsilon\gt0$ be given. We know that \[ b_k-a_k = \tfrac12 (b_{k-1}-a_{k-1}) = \cdots = \left(\tfrac12\right)^{k-1} (b_1-a_1) \] The Archimedean property implies that there is a $K_\epsilon\in\N$ such that $\left(\tfrac12\right)^{k-1} (b_1-a_1) \lt \epsilon $ for $k\geq K_\epsilon$, and thus $b_k-a_k\leq \epsilon$ for $k\geq K_\epsilon$. Since $a_k\leq \alpha \leq b_k$ it follows from $b_k-a_k\lt \epsilon$ that \[ \alpha-\epsilon \lt a_k \lt b_k \lt \alpha+\epsilon. \] Finally, it follows from $x_{n_k} \in [a_k, b_k]$ that \[ \alpha - \epsilon \lt x_{n_k} \lt \alpha+\epsilon \] for all $k\geq K_\epsilon$. Thus $x_{n_k} \to \alpha$.    ////
Definition: compact subsets of a metric space. A subset $E\subset X$ is compact if every sequence of points $\{x_i\}_{i\in\N}\subset E$ has a convergent subsequence whose limit belongs to $E$.
The notion of compactness in this definition is often called “sequential compactness” in order to distinguish it from a more general definition of “compactness” which appears in pointset topology. For metric spaces it can be shown that both notions are equivalent, and in this course we will restrict ourselves to the sequential compactness definition given above.
Theorem. Closed and bounded subsets of $\R^n$ are compact.
Theorem. A compact subset $E\subset X$ of any metric space $X$ is closed and bounded.
Proof. 
Theorem. Let $E\subset X$ be a compact subset of a metric space. A closed subset $F\subset E$ is also compact.
Further examples of compact and non compact sets.
Consider the metric space $X = \R\setminus\{0\}$, and let $E = (0,1]$. Then $E$ is a bounded subset of $X$ because it is contained in $B_1(1)$. The set $E$ is also closed in $X$ (one way to prove this is to show that the complement $X\setminus E = (-\infty,0)\cup(1, \infty)$ is open in $X$.) However, the set $E$ is not compact because the sequence $x_n =1/n$ in $E$ does not have any subsequence that converges in $E$.
Closed and bounded subsets of $C([0,1])$ are not always compact (Arzela–Ascoli).
Theorem. If $E_1\supset E_2 \supset E_3 \supset \cdots$ is a nested sequence of nonempty compact subsets of a metric space $X$, then their intersection $\cap_{i=1}^\infty E_i$ is a nonempty compact subset of $X$.
Proof.   ////
Examples: Nesting intervals. Nesting rectangles. Cantor set. Invariant set in $[0,1]$ of $f(x) = ax(1-x)$ where $a\gt 4$.
The Heine–Borel theorem. If $E\subset X$ is a compact subset of a metric space $X$, and if $\{O_i\}_{i\in\cA}$ is an open covering of $E$, then there is a finite subset $\{i_1, \dots, i_n\}\subset\cA$ such that $E \subset O_{i_1}\cup \cdots \cup O_{i_n}$.
Here a family of subsets $\{O_i\}_{i\in \cA}$ of a metric space is called a covering of a set $E\subset X$ if $E\subset\cup_{i\in\cA}O_i$.
Complete metric spaces
Definition of Cauchy sequences. A sequence $\{x_i\}_{i\in\N}\subset E$ is a Cauchy sequence if for every $\varepsilon \gt 0$ there exists an $N_\varepsilon\in\N$ such that for all $i, j\geq N_\varepsilon$ one has $d(x_i, x_j) \lt \varepsilon$.
Interpretation : $\lim_{i, j\to\infty} d(x_i, x_j) = 0$.
Theorem (convergent sequences are Cauchy sequences). If the sequence $\{x_i\}_{i\in\N}$ converges in $X$ then $\{x_i\}$ is a Cauchy sequence.
An example: not every Cauchy sequence converges. E.g. consider $X=\R\setminus\{0\}$, $x_i = 1/i$.
Definition (completeness). A metric space $X$ is complete if every Cauchy sequence in $X$ converges in $X$.
Theorem. Euclidean space $\R^n$ is complete.
Theorem. Every compact metric space is complete.