Stepan Malkov

Week 2-3 Problem Set

Easy:

  1. Show that a sequence (x_n)_{n=1}^\infty has a convergent subsequence if and only if the set \{x_n\}_{n=1}^\infty has an adherent point.
    2. Solution: Suppose L \in X is an adherent point of (x_n)_{n=1}^\infty. Then, for every \epsilon>0, there exists an N such that d(x_N,L) < \epsilon, meaning one can construct a subsequence (x_{n_j})_{j=1}^\infty with n_{j+1}>n_j such that d(x_{n_j},L)<\epsilon = \frac{1}{j} (as otherwise, there would exist an r>0 such that d(x_n,L)>r for all n, contradicting the fact that L is an adherent point. By definition of a convergent subsequence, this implies \lim_{j \to \infty} x_{n_j} = L, i.e. (x_n)_{n=1}^\infty has a convergent subsequence. Conversely, if (x_{n_j})_{j=1}^\infty is a convergent subsequence converging to L, note that for any \epsilon>0 and N>0 there exists an n_j \geq N such that d(x_{n_j},L) < \epsilon, implying that L is an adherent point of the sequence (x_n)_{n=1}^\infty.
  2. Show that a closed subset A \subset K of a compact metric space X in is compact.
    3. Solution: Let x_n be a sequence in A. Then, it has a convergent subsequence x_{n_j} \to x in K. But since A is closed, x \in A, so every sequence is A has a convergent subsequence in A. Thus, A is sequentially compact, i.e. it is compact.
  3. Let K_1 \supset K_2 \supset ... be a sequence of compact subsets of a metric space. Show \bigcap_{n=1}^\infty K_n is non-empty.
    4. Solution: Form a sequence (x_n) such that x_n \in K_n. Then, this sequence has a convergent subsequence x_{n_j} \to x. Since x_{n_j} \in K_n for n_j \geq n, and K_{n} is compact and therefore closed, it follows that x \in K_n for all n. Thus, x \in \bigcap_{n=1}^\infty K_n, i.e. the intersection is nonempty.
  4. Show that every Cauchy sequence is bounded.
    5. Solution: Let \epsilon =1. Then, by the definition of a Cauchy sequence, for some N, d(x_n,x_m) < 1 for n,m \geq N, so B(x_N, \max(1,2\sup_{1 \leq i \leq n-1}d(x_i,x_N))) contains all elements of the sequence, i.e. the sequence is bounded.

Medium:

  1. Consider C([0,1]) with the metric of uniform convergence. Let (f_n)_{n=1}^\infty \subset C([0,1]) be a sequence defined by f_n(x) = x^n. Show that the set \{f_n\}_{n=1}^\infty \cup \{0\} is not compact in C([0,1]).
    2. Solution: Note that since f_n(x) \to 0 pointwise, any convergent sequence of distinct elements would have a further convergent subsequence (f_{n_k}) that converges to 0 in C([0,1]). But d(f_n,0) = 1 for all n, so there any such sequence has no convergent subsequence, i.e. it is not compact in C([a,b]).
  2. A metric space (X,d) is called totally bounded if for every \epsilon >0, there exist finitely many points x_1,...,x_n such that X \subseteq \bigcup_{i=1}^n B(x_i,\epsilon). Show that a metric space is compact if and only if it is complete and totally bounded.
    3. Solution: Suppose X is compact. Then, let (x_n) be a Cauchy sequence, and x_{n_k} \to x be a convergent subsequence. Since

        \[d(x_n,x) \leq d(x_n,x_{n_k}) + d(x_{n_k},x) < \frac{\epsilon}{2}+\frac{\epsilon}{2} = \epsilon\]

    for sufficiently large n,n_k, one gets that x_n \to x, i.e. a Cauchy sequence converges. Thus X is complete.
    Now, for any \epsilon>0, let \bigcup_{x \in X} B(x,\epsilon) be an open cover of X, which by compactness must have a finite subcover B(x_1,\epsilon),...,B(x_n,\epsilon). Thus, there exist finitely many balls that cover X, i.e. X is totally bounded.
    Conversely, suppose X is complete and totally bounded, and let (x_n) be a sequence. Cover X by balls of radius 1, and note that at least one of the balls B_1 must have infinitely many elements of (x_n). Pick one such element x_{n_1}, and cover X by balls of radius \frac{1}{2}. Note that there must exist a ball B_2 such that B_1 \cap B_2 has infinitely many elements of (x_n). Pick one such element x_2, and proceed in this fashion by covering X with balls of radius \frac{1}{n} to construct a subsequence x_{n_j}. By construction, x_{n_j},x_{n_k} \in B(y,\frac{1}{j} for j \leq k, so d(x_{n_j},x_{n_k}) \leq \frac{2}{j} for j \leq k, i.e. the sequence is Cauchy. By completeness, it converges to some x \in X. Thus, any sequence x_n has a convergent subsequence x_{n_j} \to x, showing that X is compact. This shows that X is compact if and only if it is complete and totally bounded.
  3. Show l^\infty is complete.
    4. Solution: Let x^{(n)} = (x^{(n)}_j)_{j=1}^\infty \in l^\infty be a Cauchy sequence. Then, (x^{(n)}_j) is a Cauchy sequence in \mathbb{R} for each fixed j, and thus converges to some y_j \in \mathbb{R}. I claim that \lim_{n \to \infty} x^{(n)} = (y_j)_{j=1}^\infty. Indeed, if one picks an N such that d_{l^\infty}(x^{(n)},x^{(m)})<\frac{\epsilon}{2} for n \geq N, taking the limit in m shows that

        \[\lim_{m \to \infty} |x_j^{(n)}-x_j^{(m)}| = |x_j^{(n)}-y_j| \leq \frac{\epsilon}{2},\]

    so

        \[d(x^{(n)},y) = \sup_{j} |x_j^{(n)}-y_j| \leq \frac{\epsilon}{2} < \epsilon,\]

    i.e. x^{(n)} \to y in l^\infty. Thus, a Cauchy sequence in l^\infty converges, showing that l^\infty is complete.

Challenging

  1. Let \mathcal{B} = \{f \in C([0,1]): |f(x)|\leq 1, x \in [0,1]\}. Determine whether \mathcal{B} is complete, bounded, totally bounded, and compact.
    2. Solution: Note that \mathbcal{B} \subset B(0,2), so it is bounded. It is complete since if \sup_{x \in [0,1]} |f_n(x)-f_m(x)| < \epsilon for n,m \geq N for some N>0, (f_n(x)) is a Cauchy sequence for each x, so it converges to some f(x) \in \mathbb{R}. Now, by the same argument as in the proof of Problem 7,

        \[\lim_{m \to \infty} |f_n(x) - f_m(x)| \leq \frac{\epsilon}{2}<\epsilon\]

    for n,m \geq N such that d(f_n,f_m) < \frac{\epsilon}{2}, so

        \[\sup_{x \in [0,1]} |f_n(x)-f(x)| \leq \frac{\epsilon}{2} < \epsilon,\]

    i.e. f_n \to f in C([0,1]). We now claim that \mathcal{B} is not compact. Let f_n(x) = x^n \in \mathcal{B}. Then, by Problem 5, this sequence has no convergent subsequence in C([0,1]), so it has no convergent subsequence in \mathcal{B}, showing that \mathcal{B} is not compact. Finally, since \mathcal{B} is complete but not compact, and a set is compact if and only if it is complete and totally bounded, we conclude that \mathcal{B} is not totally bounded.
  2. The following outlines the proof of an important theorem known as the Contraction Mapping Principle. The Contraction Mapping Principle states that if (X,d) is a complete metric space and f: X \to X is a contraction on X, that is, d(f(x),f(y)) \leq K d(x,y) for some 0<K<1, then the map f has a unique fixed point, i.e. a point x \in X such that f(x) = x.
    1. Pick a point x_0 \in X, and define x_{n+1} = f(x_n). Show that d(x_n, x_{n+1}) \leq K^n d(x_0,x_1).
      2. Solution: Iterating the contraction equation n times yields

          \[d(x_n,x_{n+1}) \leq K d(x_{n-1},x_n) \leq ... \leq K^n d(x_0,x_1).\]

    2. Use part i), the triangle inequality, and the geometric series formula to show that d(x_n,x_m) \leq \frac{K^n}{1-K} d(x_0,x_1). Conclude that (x_n)_{n=1}^\infty is Cauchy, and therefore converges to some x \in X.
      3. Solution: By the triangle inequality and the geometric series formula, one obtains

          \[d(x_n,x_m) \leq (K^n + K^{n+1}+... + K^{m-1}) d(x_0,x_1) = K^n(1 + K + ... +K^{m-1}) d(x_0,x_1) \leq \frac{K^n}{1-K} d(x_0,x_1) \to 0\]

      as n \to \infty. Thus, the sequence is Cauchy, so it has a limit x.
    3. Show that x is a fixed point of f, and use proof by contradiction to show that the fixed point must be unique.
      4. Solution:

          \[f(x) = f(\lim_{n \to \infty} x_n) = \lim_{n \to \infty} f(x_n) = \lim_{n \to \infty} x_{n+1} = x,\]

      so x is a fixed point of f. If there were two fixed points x,y \in X then d(f(x),f(y)) = d(x,y) \leq K d(x,y), which is a contradicton, so uniqueness follows.