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 [itex]X\times X[/itex] to the real numbers such that:
1) [itex]d(x,y)\ge 0[/itex].
(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) [itex]d(x,y)\le d(x,z)+ d(y,z)[/itex]
(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: [itex]d(p_n, p_m)[/itex] 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 [itex]d(f(x), f(y))\le cd(x,y)[/itex]- 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, [itex]f^2(S)[/itex] 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: [itex]d(x_n, x_{n+1})\le c^n d(x_0, x_1)[/itex]
Proof by induction:
If n= 0, this says [itex]d(x_0,x_1)\le d(x_0,x_1)[/itex] which is certainly true.
Suppose [itex]d(x_n, x_{n+1})\le c^n d(x_0, x_1)[/itex]. Then [itex]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)[/itex] so we are done.
Of course, since c< 1, cn goes to 0 as n goes to infinity so we have proved that [itex]d(x_n,x_{n+1})[/itex] 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 [itex]a_n= \sum_{i=1}^n 1/i[/itex], 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 [itex]d(x_n,x_m)[/itex] 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", [itex]d(x_n,x_m)\le d(x_n, x_{n+1}+ d(x_{n+1},x_m)[/itex]. By the "triangle inequality" again, [itex]d(x_{n+1},x_m)\le d(x_{n+1},x_{n+1}+ d(x_{n+2},x_m)[/itex] so that [itex]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)[/itex]. Repeating that m-n times, we have
[tex]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 [itex]d(x_i,x_{i+1})\le c^id(x_0,x_1)[/itex]:<br />
[tex]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)[/tex]<br />
[tex]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> 0, adding higher higher power terms to that last sum can only make it larger so we also have<br />
[tex]d(x_n,x_m)\le c^n d(x_0,x_1)(\sum_{i=0}^\infty c^i)[/tex]<br />
<br />
But now that sum is a geometric series. Since c< 1, it converges and its sum is [itex]\frac{1}{1- c}[/itex]. So for any n, m, we have<br />
[tex]d(x_n,x_m)\le \frac{d(x_0,x_1)}{1- c} c^n[/itex]<br />
Notice that m has disappeared from the formula. But since m> n, as n goes to infinity, so must m. This is a constant times c<sup>n</sup>. As m and n go to infinity, the distance between x<sub>n</sub> and x<sub>m</sub> goes to 0. This <b>is</b> a Cauchy sequence and, because our space is complete, it converges.<br />
<br />
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<sub>n</sub>)= lim f(x<sub>n</sub>)= lim x<sub>n+1</sub>. But that is the same sequence as before- its limit is x. f(x)= x. <br />
<br />
That proves that f has a fixed point but not that it is unique. Had we started with some other point a x<sub>0</sub>, 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.<br />
<br />
Suppose f(x)= x and f(y)= y. Then [itex]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 [itex]d(x,y)\le cd(x,y)[itex]or [itex](1- c)d(x,y)= 0[/itex]. Since c is not 1 and d(x,y) is never negative, we have d(x,y)= 0 and so x= y.<br />
<br />
End of proof.[/itex][/itex][/itex][/tex][/tex][/tex]