Stepan Malkov

Week 5

Contraction Mapping and Connectedness

Before talking about continuity, I wanted to discuss a very important result regarding compactness known as the contraction mapping theorem:
Theorem (Contraction Mapping Theorem):
Let X be a complete metric space, and f: X \to X be a contraction, i.e. d(f(x),f(y)) \leq K d(x,y) for some 0<K<1. Then, f has a unique fixed point y \in X such that f(y) = y.
Proof:
Our goal is to construct a Cauchy sequence. Define x_n = f^{(n)}(x_0). Then, d(x_n,x_{n+1}) \leq K d(x_{n-1},x_n), so iterating yields d(x_n,x_{n+1}) \leq K^n d(x_0,x_1). Moreover, 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 y. But then,

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

so y 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.
Example:
When using a calculator, when you press \cos many times and enter some number in radians, you will always get a value very close to 0.739. Why? Well, suppose one lets X = \mathbb{R}, f(x) = \cos x. Then, by the mean value theorem,

    \[\frac{|\cos(x)-\cos(y)|}{|x-y|} = |\sin(x')| \leq 1,\]

i.e. |\cos(x)-\cos(y)| \leq K |x-y| for K = |\sin x'|. Then only thing left to show is that K=1. We know |\sin x'| =1 only when x' = \frac{\pi}{2}+\pi n, so let’s consider the interval [-1,1]. We can apply the contraction mapping theorem on this interval to guarantee the existence of a unique fixed point y such that y = \cos y. Then, for any x_0 \in \mathbb{R}, \cos x_0 \in [-1,1], which guarantees the convergence of our sequence to the fixed point y.
We now briefly discuss the definition of continuity between metric spaces.
Definition
A map f: X \to Y between two metric spaces is continuous if any of the following equivalent conditions hold:
  1. For any open V \subset Y, f^{-1}(V) \subset X is open.
  2. For every sequence x_n \to x \in X, f(x_n) \to f(x) \in Y.
  3. For every \epsilon > 0, there exists a \delta>0 such that d(f(x),f(y))<\epsilon whenever d(x,y) < \delta.
Similarly, one can define a local notion of continuity at a single point.
Definition:
f: X \to Y is continuous at x \in X if:
  1. For all V neighborhood of f(y) \in Y, there exists a neighborhood U of y such that U \subset f^{-1}(V).
  2. For all \epsilon>0, there exists a \delta>0 such that d(f(y),f(y'))<\epsilon whenever d(y,y')<\delta.
  3. y_n \to y \in X implies f(y_n) \to f(y) \in Y.
Examples:
  1. The function f: \mathbb{R}^2 \to \mathbb{R} defined to be f(x,y) = \frac{x^2 y}{x^3+y^4} for (x,y) \not = (0,0) and f(0,0) = 0 is not continuous at (0,0), since setting (x_n,y_n) = (x_n,x_n) \to 0 implies f(x_n,x_n) = \frac{x_n^3}{x_n^3+x_n^4} \to 1 \not = f(0,0) = 0.
  2. For a discrete metric space (X,d_X) and a subset U \subset X, suppose U is equipped with the discrete metric d_{disc} and X is equipped with an arbitrary metric d_X. Then, the inclusion map i: U \to X is always continuous, since x_n \to x \implies x_n = x for n \geq N \implies f(x_n) = f(x) for n \geq N \implies f(x_n) \to f(x).
    3. We now consider another very important property of sets in metric spaces known as connectedness.
    Definition:
    A set A \subset X is said to be disconnected if there exist non-empty open sets U,V \subset X such that A \subset U \cup V and U \cap V = \varnothing. If a set is not disconnected, it is called connected.
    Definition:
    A set A \subset X is called path-connected if for every x,y \in A, there exists a continuous map f:[0,1] \to X such that f(0) = x and f(1) = y. Such a map is called a path from x to y.
    Examples:
    1. As seen in lecture, a set in \mathbb{R} is connected if and only if it is an interval.
    2. \mathbb{Q} is not connected, since U=(-\infty, \alpha), V=(\alpha,\infty) for some \alpha \in \mathbb{R} \setminus \mathbb{Q} disconnects \mathbb{Q} into two disjoint components.
    Proposition:
    If f: X \to Y is continuous and A \subset X is connected, then f(A) is connected in Y.
    Proof:
    Suppose not. Then, there exist U,V \subset Y open such that f(A) \subset U \cup V, U \cap V = \varnothing. Then, by the topological definition of continuity, f^{-1}(U), f^{-1}(V) are open, f^{-1}(U) \cap f^{-1}(V) = \varnothing, and A \subset f^{-1}(U) \cap f^{-1}(V). But this implies A is disconnected, which is a contradiction.
    Proposition:
    If a set A is path-connected, it is connected.
    Proof:
    For sake of contradiction, suppose A is path-connected but not connected. Then, there exist U,V open such that A \subset U \cup V and U \cap V = \varnothing. Pick u \in A \cap U, v \in A \cap V, and a path f: [0,1] \to A such that f(0)=1,f(1) =v. Since the image of a connected set under a continuous map is connected, f([0,1]) is connected. But f([0,1]) \subset U \cup V, U \cap V = \varnothing, so f([0,1]) is disconnected, which is a contradiction.
    Corollary
    C([0,1]) is connected, since for any f,g \in C([0,1]), \gamma: [0,1] \to C([0,1]) given by \gamma(t) = t f(t) + (1-t) g(t) is a continuous map satisfying \gamma(0) = f(t),\gamma(1) = g(t).