The Contraction Mapping Theorem

Prerequisite knowledge and definitions

A metric space is any set of points with some notion of distance between them. Some examples are the real numbers, the integers, or the unit sphere. The distance between these points is given by the metric of the space, hence the name metric space. We will denote the distance between any two points x and y under some metric as d(x,y).

The triangle inequality states that for any three points x y and z in a metric space, d(x,z)≤ d(x,y)+d(y,z).

A cauchy sequence is any sequence of points an where ,for any number ε > 0, there exists a natural number N such that for any natural numbers s and t such that s>N and t>N, d(as,at)<ε. Essentially, what this means is that the terms of the sequence get arbitrarily close together such that at a point an, the entire rest of the sequence stays within a distance of εn from that point, where εn is itself a decreasing sequence of positive numbers that converges to 0.

A complete metric space is a metric space such that every cauchy sequence that it contains converges to some point within that metric space. An example is the real numbers.

A contraction mapping is a function f from a metric space to itself such that for some k < 1, for all points x and y in our metric space, d(f(x),f(y)) ≤ k * d(x,y).

A fixed point of a function f is a point x in a metrix space such that f(x)=x.

Statement of the theorem

Now that we have had some time to learn the basic terminology, we can understand the final statement of the Banach Contraction Principle: if a contraction f exists on a nonempty complete metric space M, then f must have a fixed point.

Proof of the statement

Since M is nonempty, we can start by taking a singular point x in M. Now, we can create a sequence xn where the nth term of the sequence is f(f(f(......f(x))..) where f is being applied to x n-1 times. So, our first term will be x, second term f(x), third term f(f(x)), and so on and so forth.

We can use the fact that f is a contraction to gather information on our sequence. We know that each term in our sequence is a part of our metric space M, and thus by picking any two consecutive terms in the sequence, we can establish that d(xn+1,xn+2) ≤ k * d(xn,xn+1). This means that each time we iterate our sequence, the movement between points gets smaller by at most a factor of k. So, since k is less than 1, these distances get arbitrarily small.

For any ε > 0, let us define a number j = ε * (1-k). We know that there exist two points in our sequence xh and xh+1 such that d(xh,xh+1) < j/2. We can now make a geometric sequence that provides an upper bound on the sum of distances between all point in our series beyond xh . Since each subsequent distance must be at most k times as large as the previous one, we can think of this as a geometric series with a factor of k and a first term of j/2. According to the formula for calculating the sum of geometric series, we can see that this sum is equal to

j/(2*(1-k)), which is conveniently equivalent to ε/2 which is strictly less than ε.

Now, imagine any two natural numbers p and q greater than h, then, all the distances between the points connecting xp and xq are included in our previous sum, and so we know that those distances sum to less than ε/2. Since we can travel from xp to xq along a path that is less than ε/2, then clearly the distance between them must be at most ε/2, which is less than ε.

So, now we have established that, for any ε > 0, there exists a natural number h such that for any natural numbers y and z greater than h, the distance between xy and xz is less than ε. In other words, our sequence xn is cauchy!

Since xn is a cauchy sequence in M, it must converge to some point in M. Let us call that point p. Assume that p is not a fixed point of f, and so d(p,f(p))=w for some w>0. Now, since our cauchy sequence converges to p, we know that there exists a natural number g such that d(xg,p) <w/4 and d(xg,xg+1)< w/4. Because of the triangle inequality, we know that d(xg+1,p)<w/2, which once again by the triangle inequality implies that d(xg+1,f(p))>w/2. Since xg+1 =f(xg), d(f(xg),f(p)) > d(xg,p). However, since f is a contraction, this is impossible, and so our assumption must have been incorrect and p must be a fixed point of f.

Q.E.D

Cool Consequences

So, what does this mean for us in the real world? Well, the banach contraction theorem leads to some pretty cool facts when we consider some real life contraction maps.

Think of where you are right now. What if you were to print out a map of your country of residence and place it on the floor. It does not have to be a perfect map, just good enough such that the general shapes of things are preserved. You can now think of the map as a smaller version of the country itself fitted onto a small part of that country. Clearly, distance between any two points decreases substantially on the map as opposed to in the real world. So, you have made a real life contraction mapping.

What this means is that the mapping you have created has a fixed point, and that at least one point on your map lies directly on top of the real life point it represents! No matter how you rotate or translate the map along the ground, as long as it stays within the country it depicts one of its points will be exactly where it should be.