# Banach Fixed-point Theorem

The **Banach fixed-point theorem** (a.k.a. the **contraction mapping theorem** or **contraction mapping principle**) is an important tool in the theory of metric space; it guarantees __the existence and uniqueness of fixed-points__ of certain self-maps of metric spaces, and provides a constructive method to find those fixed-points.

## 1. Statement

**Definition (Contraction Mapping)** Let $(X,d)$ be a metric space. Then a map $T:X\mapsto X$ is called a contraction mapping on $X$ if there exists $q\in [0,)1$ such that
for all $x,y\in X$.

**Theorem (Banach Fixed-point Theorem)** Let $(X,d)$ be a non-empty complete metric space with a contraction mapping $T:X\mapsto X$. Then $T$ admits a unique fixed-point $x^\ast$ in $X$ (i.e. $T(x^\ast)=x^\ast$).

Furthermore, $x^\ast$ can be found as follows: start with an arbitrary element $x_0$ in $X$ and define a sequence ${x_n}$ by $x_n=T(x_{n-1})$, then $x_n\to x^\ast$.

## 2. Proof

Let $x_0\in X$ be arbitrary and define a sequence ${x_n}$ by setting $x_n=T(x_{n-1})$. We first note that for all $n\in \mathbb{N}$, we have given that $T$ is a contraction mapping. Then we can show that ${x_n}$ is a Cauchy sequence. Without loss of generality, let $m,n\in\mathbb{N}$ such that $m>n$. Then for $\forall\varepsilon>0$, we can find a large $N\in\mathbb{N}$ and let $m,n>N$ we have This proves that ${x_n}$ is a Cauchy sequence. By completeness of $(X,d)$, the sequence has a limit $x^\ast\in X$. Furthermore, the $x^\ast$ must be a fixed-point of $T$: (As a contraction mapping, $T$ is continuous, so bringing the limit inside $T$ was justified.)

Lastly, $T$ cannot have more than one fixed point in $(X,d)$, since any pair of distinct fixed points $p_1$ and $p_2$ would contradict the contraction of $T$:

## 3. Applications

It can be used to prove existence and uniqueness of solutions to value iteration, policy iteration, and policy evaluation of reinforcement learning.

## Appendix

### Metric space

A metric space is a tuple $(M,d)$ where $M$ is a set and $d$ is a metric on $M$, i.e., a function such that for any $x, y, z \in M$, the following holds:

Axioms | Names |
---|---|

$d(x,y)=0\Leftrightarrow x=y$ | identity of indiscernibles |

$d(x,y)=d(y,x)$ | symmetry |

$d(x,y)\le d(x,z)+d(y,z)$ | triangle inequality |

Using the above three properties, we can easily induce the forth axiom:

Axioms | Names |
---|---|

$d(x,y)\ge 0$ | non-negativity |

#### Cauchy completion

A metric space $(M,d)$ is called **complete** (or a **Cauchy space**) if every Cauchy sequence of points in $M$ has a limit that is also in $M$.

### Cauchy sequence

Given a metric space $(M,d)$, a sequence $x_1,x_2,\dots$ is **Cauchy**, if for every possible positive real number $\varepsilon>0$ there exists a positive integer $N$ such that for all positive integer $m,n>N$, the distance $d(x_m,x_n)<\varepsilon$.