Banach fixed point theorem: If X is a complete metric space, S is a non-empty subset of X, and f(x) is a contraction map of S into itself, then f has a unique fixed point.
Some preleminary definitions:
A metric on a set, X, is a "distance" function: a function, d, from X\times X to the real numbers such that:
1) d(x,y)\ge 0.
(The distance between two points is never negative)
2) d(x, y)= 0 if and only if x= y.
(The distance between a point and itself is 0 but the distance between two distinct points is non-zero)
3) d(x,y)= d(y, x)
(The distance from x to y is the same as the distance from y to x)
4) d(x,y)\le d(x,z)+ d(y,z)
(The "triangle inequality": going around a two sides of a triangle, from x to z and then to y, is not less than going directly from x to y: the shortest distance between two points is a straight line.
A "metric space" is a set of points with a metric assigned.
A "Cauchy sequence" is a sequence of points such that distances between the points goes to 0 as you go out along the sequence: d(p_n, p_m) goes to 0 as n and m go to infinity independently.
A complete space is one in which all Cauchy sequences converge. For example, the set of real numbers is complete, the set of rational numbers is not. That is, in a sense, the "defining" difference between them.
A function f(x) is a "contraction" map if and only if there is a number 0< c< 1 such that d(f(x), f(y))\le cd(x,y)- it "contracts" in the sense that f(x) and f(y) are closer together than x and y were. Notice this is NOT just "d(f(x),f(y))< d(x,y)". It turns out that is not enough for this theorem. It's not difficult to prove that any contraction map is continuous.
A "fixed point" of a function, f, is a point x, such that f(x)= x.
Basic idea of the proof. Suppose S is some set of points, f is a contraction map that maps S to itself. If we apply f to every point of S, the result, f(S) is smaller than S and, since f maps S into itself, is a subset of S. If we do it again, f^2(S) is a yet smaller subset of both S and f(S). If we continue doing this, in the limit the set contracts to a single point, x which was in all the sets in the sequence. Applying f to x is the same, now, as applying f to "the entire set" and must "inside" the single point itself: f(x)= x.
How do we know that S contracts to a single point? For example, let S be the disk of radius 2R. Isn't it possible that f(S) is the disk of radius (3/2)R, f(f(S)) is the disk of radius (5/4)R, and, in general, f applied to S gives the disk or radius ((n+1)/n)R? That contracts to the disk of radius R, not a single point! That would be a map that satisfies d(f(x),f(y))< d(x,y)- the "c" we had before is not constant but goes to 1 as we repeat f. That's why we need 'c< 1'.
Finally: the proof
With S a non-empty subset of the complete metric space X, f a contraction map that maps S to itself, let x0 be any point of S. Let x1= f(x0), x2= f(x1, and, in general, xn= f(xn-1). We will prove that {xn} is a Cauchy sequence and so converges.
Lemma: d(x_n, x_{n+1})\le c^n d(x_0, x_1)
Proof by induction:
If n= 0, this says d(x_0,x_1)\le d(x_0,x_1) which is certainly true.
Suppose d(x_n, x_{n+1})\le c^n d(x_0, x_1). Then d(x_{n+1},x_{n+2})= d(f(x_n),f(x_{n+1})\le cd(x_n, x_{n+1})= c(c^n d(x_0,x_1))= c^{n+1}d(x_0,x_1) so we are done.
Of course, since c< 1, cn goes to 0 as n goes to infinity so we have proved that d(x_n,x_{n+1}) goes to 0 as n goes to infinity.
But proving that the distance between consecutive terms goes to 0 is not enough. For example, if a_n= \sum_{i=1}^n 1/i, then the distance between an and an+1 is 1/n(n+1) which goes to 0, but {an is the "harmonic sequence" which does not converge. To show that {xn} is a Cauchy sequence we must show that d(x_n,x_m) goes to 0 as n and m go to infinity independently- that is, without any relation such as m= n+1.
Because the metric is symmetric (d(x,y)= d(y,x), we can, without loss of generality, assume m> n. For any such n, m, by the "triangle inequality", d(x_n,x_m)\le d(x_n, x_{n+1}+ d(x_{n+1},x_m). By the "triangle inequality" again, d(x_{n+1},x_m)\le d(x_{n+1},x_{n+1}+ d(x_{n+2},x_m) so that d(x_n,x_m)\le d(x_n,x_{n+1})+ d(x_{n+1},x_{n+2})+ d(x_{n+2},x_m). Repeating that m-n times, we have
d(x_n,x_m)\le d(x_n,x_{n+1})+ d(x_{n+1},x_{n+2})+ \cdot\cdot\cdot+ d(x_{m-1},x_m)[/itex]<br />
<br />
Now these <b>are</b> all consecutive points so we can apply d(x_i,x_{i+1})\le c^id(x_0,x_1):<br />
d(x_n,x_m)\le c^nd(x_0,x_1)+ c^{n+1}d(x_1,x_0)+ \cdot\cdot\cdot+ c^{m-1}d(x_1,x_0)<br />
d(x_n,x_m)\le c^n d(x_0,x_1)(1+ c+ \cdot\cdot\cdot+ c^{m-n-1})[/itex]<br />
Since c&gt; 0, adding higher higher power terms to that last sum can only make it larger so we also have<br />
d(x_n,x_m)\le c^n d(x_0,x_1)(\sum_{i=0}^\infty c^i)<br />
<br />
But now that sum is a geometric series. Since c&lt; 1, it converges and its sum is \frac{1}{1- c}. So for any n, m, we have<br />
d(x_n,x_m)\le \frac{d(x_0,x_1)}{1- c} c^n[/itex]&lt;br /&gt;
Notice that m has disappeared from the formula. But since m&amp;gt; n, as n goes to infinity, so must m. This is a constant times c&lt;sup&gt;n&lt;/sup&gt;. As m and n go to infinity, the distance between x&lt;sub&gt;n&lt;/sub&gt; and x&lt;sub&gt;m&lt;/sub&gt; goes to 0. This &lt;b&gt;is&lt;/b&gt; a Cauchy sequence and, because our space is complete, it converges.&lt;br /&gt;
&lt;br /&gt;
Now, let x be the limit of the sequence. Since f is a contraction map on S it is continuous on S and f(x)= f(lim x&lt;sub&gt;n&lt;/sub&gt;)= lim f(x&lt;sub&gt;n&lt;/sub&gt;)= lim x&lt;sub&gt;n+1&lt;/sub&gt;. But that is the same sequence as before- its limit is x. f(x)= x. &lt;br /&gt;
&lt;br /&gt;
That proves that f has a fixed point but not that it is unique. Had we started with some other point a x&lt;sub&gt;0&lt;/sub&gt;, we would get a different sequence and possibly a different limit. However, it is easy to prove that contraction map cannot have two distinct fixed points.&lt;br /&gt;
&lt;br /&gt;
Suppose f(x)= x and f(y)= y. Then d(f(x), f(y))\le d(x,y) But we also have d(f(x),f(y))= c d(x,y) so we must have d(x,y)\le cd(x,y)or (1- c)d(x,y)= 0. Since c is not 1 and d(x,y) is never negative, we have d(x,y)= 0 and so x= y.&amp;amp;amp;lt;br /&amp;amp;amp;gt;
&amp;amp;amp;lt;br /&amp;amp;amp;gt;
End of proof.