Fiexed point theorem for contractions

[Epsilon36819]

I apologize in advance for starting yet another thread, but I would really like to have some feedback on this one.

I have a "proof" of the theorem, which surely is wrong because it relaxes one of the conditions. Start with the "official" statement:

Let X be a compact metric space, f:X->X, and d(f(x),f(y)) < d(x,y) (or alternatively, d(f(x),f(y)) < a*d(x,y), 0<a<1) when x /= y. Then there exists a (unique) point x in X such that x=f(x).

Pf (of existence): Define x_n+1 = f(x_n). Since X is compact, the sequence {x_n} contains a convergent subsequence, say {x_n_k} with x_n_k --> x and x is in X. This implies that f(x) is also in X. d(f(x),f(y)) < d(x,y) implies that f is (uniformly) continuous, so x_n_k+1 = f(x_n_k) --> f(x). The limit point thus has the desired property.

Surely, this is wrong as the only condition I need is continuity of f. But somehow, I cannot figure out which step(s) is wrong.

Any help greatly appreciated.

 

[Epsilon36819]

Aggrh... x_n_k+1 /= f(x_n_k). Actually, x_n_k+1 = f(x_p) with p the previous integer. This prevents me from equating both limits.

 

[HallsofIvy]

Roughly speaking, the proof of this fixed point theorem uses the fact that on every repeat of f, the (compact) set is mapped into a smaller set. Repeating that infinitely causes the entire set to converge to a single point, the fixed point. If you only have |f(x)- f(y)|< |x- y|, rather than |f(x)- f(y)|<= c|x-y| with c< 1, there is the possibility that the sequence, starting at different initial points converge to different limits: the entire set converges to the boundary of some non-trivial subset.

 

[gel]

If you only have |f(x)- f(y)|< |x- y|, rather than |f(x)- f(y)|<= c|x-y| with c< 1, there is the possibility that the sequence, starting at different initial points converge to different limits: the entire set converges to the boundary of some non-trivial subset.

That doesn't look right. If X is compact there should be a unique fixed point.

First, as f is continuous there is a non-empty closed subset C with f(C) = C (*).

Let x,y in C maximize d(x,y). Then there are x', y' in C with f(x')=x, f(y')=y and if x' != y' this implies d(x,y)=d(f(x'),f(y'))<d(x',y') isn't maximal. So the only possibility is x'=y', and x=y. So C contains only one point, which will be the unique fixed point of f.

(*) Is the existence of C obvious? I was going to say take the intersection of the sequence
$$X\supseteq f(X)\supseteq f^2(X)\supseteq f^3(X)\supseteq\cdots$$
but that doesn't work. Can still find C using transfinite induction, but that seems rather complicated for such a simple question.

 

[Epsilon36819]

We can get rid of the need for C by letting g(x)= d(f(x),x). Then g(x) <= d(f(x),f(y)) + g(y) + d(x,y) so that g(x) - g(y) < 2*d(x,y). By letting x --> y, we obtain |g(x) - g(y)| < 2*d(x,y). Since g is continuous, if X is compact, g will attain a minimum, say g(p). If g(p)>0, then g(f(p)) = d(f(f(p)),f(p) < d(f(p),p) = g(p), a contradiction.

 

[Epsilon36819]

Come to think of it, the existence of C isn't obvious, at least to me. The proof you gave proves unicity, but not existence.

 

[gel]

Sorry, I read HallsofIvy's post as saying the result was only true for |f(x)-f(y)| <= c|x-y|, c< 1, not in the more general case with |f(x)-f(y)|<1. Looks like I just misread it, and actually agree with what he said (I think).

 

[gel]

Come to think of it, the existence of C isn't obvious, at least to me. The proof you gave proves unicity, but not existence.

The proof of existence of C that occurs to me is the following:

for every ordinal $\alpha$ (finite or infinite) define $f^\alpha(X)$ inductively by
$$\begin{align*} &f^0(X)=X,\\ &f^{\alpha+1}(X)=f(f^\alpha(X)),\\ &f^\alpha(X)=\bigcap_{\beta<\alpha}f^ \beta(X)\ \ \textrm{if \alpha is a limit ordinal} \end{align*}$$
Transfinite induction says that this is well defined, and $f^\alpha(X)$ will eventually be constant, equal to some set C (otherwise you would have a 1-1 map from the proper class of ordinals into a set).
Then, $C=f^\alpha(X)=f^{\alpha+1}(X)=f(C)$.

Also, by induction and the compactness of X, every $f^\alpha(X)$ will be closed and nonempty.

We can get rid of the need for C by letting g(x)= d(f(x),x). Then g(x) <= d(f(x),f(y)) + g(y) + d(x,y) so that g(x) - g(y) < 2*d(x,y). By letting x --> y, we obtain |g(x) - g(y)| < 2*d(x,y). Since g is continuous, if X is compact, g will attain a minimum, say g(p). If g(p)>0, then g(f(p)) = d(f(f(p)),f(p) < d(f(p),p) = g(p), a contradiction.

Ah, that's a much simpler proof of the original theorem. The existence of C is something much more general, but not needed here.

 

[Epsilon36819]

Transfinite induction says that this is well defined, and $f^\alpha(X)$ will eventually be constant, equal to some set C (otherwise you would have a 1-1 map from the proper class of ordinals into a set).

Mind you, I am absolutely not familiar with ordinals and transfinite induction, but with what I know, I am not sure why you say that $f^\alpha(X)$ will eventually be constant.

$f^\alpha(X)$ could be any subset of X with cardinality equal or less to $f^{\alpha-1}(X)$. Intuitively, if the cardinality of X is finite, then the cardinality of $f^\alpha(X)$ must become constant, but why should the set be constant? I could picture subsets A and B of X s.t. f^{\2k}(X)=A and f^{\2k+1}(X)=B, in the case that alpha is a natural number.

Again, sorry if I'm just not getting it. I guess I'll have to go surf wikipedia on ordinals now...

 

[gel]

Mind you, I am absolutely not familiar with ordinals and transfinite induction, but with what I know, I am not sure why you say that $f^\alpha(X)$ will eventually be constant.

If you're familiar with Zorn's Lemma, you could also use that, applied to the non-empty closed subsets of X satisfying $f(S)\subseteq S$, to show that there is a minimal such subset. Which will give you the set C. The transfinite induction approach just avoids the axiom of choice and constructs C in a unique way.

The reason $f^\alpha(X)$ is eventually constant is the same as the reason why this http://en.wikipedia.org/wiki/Zorn's...orn.27s_lemma_.28from_the_axiom_of_choice.29" works.
Note that the class of all ordinals is a proper class, not a set. If it was a set, then this set would itself be an ordinal bigger than (and hence not equal to) any of its elements - a contradiction. It follows that no mapping from the class of ordinals to a set can be 1 to 1. And, any order preserving map into a (partially) ordered set must eventually be constant.

 

[Epsilon36819]

Mmm... that's all a little over my head right now. I'll meditate on it.

 

[konthelion]

Pf (of existence): Define x_n+1 = f(x_n). Since X is compact, the sequence {x_n} contains a convergent subsequence, say {x_n_k} with x_n_k --> x and x is in X. This implies that f(x) is also in X. d(f(x),f(y)) < d(x,y) implies that f is (uniformly) continuous, so x_n_k+1 = f(x_n_k) --> f(x). The limit point thus has the desired property.

Since X is compact, then there for a sequence $${x_{n}$$ converges to x in X; but
$$d(f(x_{n}),f(x)) \leq c d(x_{n},x)$$ such that $${f(x_{n} \rightarrow f(x)$$.

But, $$f(x_{n})= x_{n+1}$$, then the sequence $${ f(x_n) }$$is a subsequence of the sequence $${x_{n}$$ such that $$f(x)=x$$ which guarantees at least one fixed point.

For x,y in X, then $$0 \leq d(x,y) = d(f(x),f(y)) \leq cd(x, y)$$

Then $$d(x,y)=0$$ if and only if x =y by definition of a metric space. Hence, there exists a (unique) point x in X such that x=f(x).

 

[Epsilon36819]

Since X is compact, then there for a sequence $${x_{n}$$ converges to x in X; but
$$d(f(x_{n}),f(x)) \leq c d(x_{n},x)$$ such that $${f(x_{n} \rightarrow f(x)$$.

But, $$f(x_{n})= x_{n+1}$$, then the sequence $${ f(x_n) }$$is a subsequence of the sequence $${x_{n}$$ such that $$f(x)=x$$ which guarantees at least one fixed point.

Since X is compact, every sequence has a convergent subsequence. But nothing tells us that any particular convergent subsequence satisfies $$f(x_{n})= x_{n+1}$$.

 

[gel]

I think Epsilon36819 was proving the Banach fixed point theorem, which has c<1. If you just have d(f(x),f(y))<d(x,y) then the proof given in post 5 seems to work fine.

 

[Epsilon36819]

The (wrong) "proof" I initially gave was for the case d(f(x),f(y))<d(x,y). But it doesn't hold for the reason I gave in post 2 (and 13). For the case c<1, HallsofIvy's outline does it.

 

[gel]

I mean, minimize d(x,f(x)), then note that if it is non-zero, d(f(x),f(f(x)))<d(x,f(x)), which would be a contradiction. so d(x,f(x))=0. That's what you said in post 5, and it seems to be a very simple and correct proof. I thought HallsofIvy was simply pointing out why the method you tried in post 1 doesn't work. If you want to try to approach it by iterating f, it does seem that you end up with something like I was saying, which uses transfinite induction.

 

[Epsilon36819]

Right. I knew how to prove the cases d(f(x),f(y))<d(x,y) (as in post 5) as well as d(f(x),f(y))<= c*d(x,y) (as in the first part of HallsofIvy's post), but I was looking for other proofs. Actually, I'll keep in mind your method and I'll get back to it once I have the proper math background.

 

[gel]

ok, here's another method that just occurred to me.
Let S1, S2 be any two nonempty closed subsets with f(S1) <= S1, f(S2) <= S2.
If x in S1 and y in S2 minimize d(x,y) then, if x != y, d(f(x),f(y))<d(x,y) which is a contradiction. So the intersection of S1 and S2 is nonempty.
By induction, the intersection of any finite set of closed sets Si with f(Si)<=Si is nonempty.
So, by compactness, the intersection of all closed nonempty subsets S with f(S)<=S is nonempty. If this intersection is C, then f(C) = C. My previous argument then shows that C contains a single point.

 

[Epsilon36819]

If this intersection is C, then f(C) = C.

It's not obvious to me why this needs to be so.

 

[gel]

because by construction, C is the smallest non-empty closed set satisfying f(C)<=C. If f(C) != C then you could replace C by f(C), which is smaller.

 

[Epsilon36819]

Ah! Yes, of course. Good one!