Banach's Fixed Point Theorem

# Banach's Fixed Point Theorem

Theorem 1 (Banach's Fixed Point Theorem): Let $(X, d)$ be a complete metric space and let $T : X \to X$ be a contraction mapping. Then $T$ has a unique fixed point $x^*$ and for any $x \in X$ the sequence $(T^n(x))_{n=1}^{\infty}$ converges to $x^*$. |

*Recall that a metric space $(X, d)$ is said to be complete if every Cauchy sequence in $X$ converges to a point in $X$.*

*A contraction mapping $T$ on $(X, d)$ is a continuous function $T : X \to X$ such that for all $x, y \in X$ we have that $d(T(x), T(y)) \leq qd(x, y)$ where $q \in (0, 1)$. In other words, the distance between $T(x)$ and $T(y)$ is less than $q$ times the distance between $x$ and $y$ for some $q \in (0, 1)$ and for all $x, y \in X$.*

**Proof:**Let $(X, d)$ be a complete metric space and let $T : X \to X$ be a contraction mapping on $X$ such that $d(T(x), T(y)) \leq qd(x, y)$ for $q \in (0, 1)$ and for all $x, y \in X$.

- We first show the existence of a fixed point. Let $x \in X$ be such that $T(x) \neq x$. For each $k \in \mathbb{N}$, by repeatedly applying the triangle inequality for the metric $d$ we have that:

\begin{align} \quad d(T^k(x), x) &\leq d(T^k(x), T^{k-1}(x)) + d(T^{k-1}(x), x) \\ & \leq d(T^k(x), T^{k-1}(x)) + d(T^{k-1}(x), T^{k-2}(x)) + d(T^{k-2}(x), x) \\ & \vdots \\ & \leq \sum_{i=1}^{k} d(T^i(x), T^{i-1}(x)) \quad (*) \end{align}

- From the contraction mapping $T$ we have that for each $i \in \{ 1, 2, ..., k \}$:

\begin{align} \quad d(T^i(x), T^{i-1}(x)) \leq qd(T^{i-1}(x), T^{i-2}(x)) \leq ... \leq q^{i-1} d(T(x), x) \quad (**) \end{align}

- From $(*)$ and $(**)$ and noting that $0 < 1 - q^k < 1$ we have that:

\begin{align} \quad d(T^k(x), x) &\leq \sum_{i=1}^{k} q^{i-1} d(T(x), x) \leq \frac{1 - q^k}{1 - q} d(T(x), x) \leq \frac{d(T(x), x)}{1 - q} \end{align}

- So for any $k > m$ we have that:

\begin{align} \quad d(T^k(x), T^m(x)) \leq q^m d(T^{k-m}(x), x) \leq \frac{q^m d(T(x), x)}{1 - q} \end{align}

- Let $\epsilon > 0$ be given. Then $M \in \mathbb{N}$ can be chosen such that if $k > m \geq M$ then $\displaystyle{\frac{q^m d(T(x), x)}{1 - q} < \epsilon}$. So there exists an $M \in \mathbb{N}$ such that if $k > m \geq M$ then $d(T^k(x), T^m(x)) < \epsilon$. So $(T^n(x))_{n=1}^{\infty}$ is a Cauchy sequence. Since $(X, d)$ is a complete metric space, $(T^n(x))_{n=1}^{\infty}$ converges to some $x^* \in X$ and moreover:

\begin{align} \quad T(x^*) = T(\lim_{n \to \infty} T^n(x)) = \lim_{n \to \infty} T^{n+1}(x) = x^* \end{align}

- So $x^*$ is a fixed point of $X$. Now suppose that $x^*$ and $x^{**}$ are both fixed points of $X$. Then:

\begin{align} \quad d(x^*, x^{**}) = d(T(x^*), T(x^{**})) \leq qd(x^*, x^{**}) \end{align}

- Since $q \in (0, 1)$, the above inequality implies that $d(x^*, x^{**}) = 0$. So $x^* = x^{**}$. Therefore, the fixed point $x^* \in X$ is unique. $\blacksquare$