Proving existence of unique fixed point on a compact space

[mahler1]

Homework Statement .

Let $(M,d)$ be a metric space and let $f:M \to M$ be a continuous function such that $d(f(x),f(y))>d(x,y)$ for every $x, y \in M$ with $x≠y$. Prove that $f$ has a unique fixed point

The attempt at a solution.

The easy part is always to prove unicity. Suppose there exist $x,y$, $x≠y$ : $x$ and $y$ are both fixed points. Then $d(x,y)=d(f(x),f(y)>d(x,y)$, which is absurd. Then, $x$ must be unique.

Now I have to prove existence and here I had problems:

First I've tried to prove it trying to repeat the standard proof of the fixed point theorem on a complete m.e. with $f$ being a contraction, I mean:

Let $x$ be an arbitrary element in M, I've defined a sequence $\{x_n\}_{n \in \mathbb N} : x_1=x, x_2=f(x_1)=f(x), x_3=f(x_2)=f^2(x_1)$ and, in general, $x_n=f(x_{n-1})=f^{n-1}(x)$.

As $M$ is compact, there exists $\{x_{n_k}\}_{k \in \mathbb N}$ a convergent subsequence of $\{x_n\}_{n \in \mathbb N}$. Then, $x_{n_k} \to z$. I would love to apply $f$ and say $z=lim_{k \to \infty} x_{n_{k+1}}=f(lim_{k \to \infty} x_{k_n})=f(z)$ (using that $f$ is continuous), but then I've realized this is completely wrong as $f(x_{n_k})=x_{n_k+1}≠x_{n_{k+1}}$.

 

[brmath]

I found you a theorem. If you can prove it, I think you have your result.

Theorem (Intermediate value theorem for metric spaces): given $(S_{1}, d_{1}), (S_{2}, d_{2}), f:E_{1} \rightarrow E_{2}, f$
is continuous,$E \subseteq S_{1}$ is connected, then$f(E) \subseteq S_{2}$is connected.

On further research I find there are a lot of "fixed point" theorems around. Check out the contraction mapping theorem here: http://www.math.tifr.res.in/~publ/ln/tifr26.pdf

 

[mahler1]

I found you a theorem. If you can prove it, I think you have your result.

Theorem (Intermediate value theorem for metric spaces): given $(S_{1}, d_{1}), (S_{2}, d_{2}), f:E_{1} \rightarrow E_{2}, f$
is continuous,$E \subseteq S_{1}$ is connected, then$f(E) \subseteq S_{2}$is connected.

On further research I find there are a lot of "fixed point" theorems around. Check out the contraction mapping theorem here: http://www.math.tifr.res.in/~publ/ln/tifr26.pdf

I'll try to solve it using that theorem, if I can arrive to a solution, I'll post it. Thanks!

 

[brmath]

I'll try to solve it using that theorem, if I can arrive to a solution, I'll post it. Thanks!

That's good. I have a feeling this is a standard result, and probably quite useful.

 

[pasmith]

Homework Statement .

Let $(M,d)$ be a metric space and let $f:M \to M$ be a continuous function such that $d(f(x),f(y))>d(x,y)$ for every $x, y \in M$ with $x≠y$. Prove that $f$ has a unique fixed point

The attempt at a solution.

The easy part is always to prove unicity. Suppose there exist $x,y$, $x≠y$ : $x$ and $y$ are both fixed points. Then $d(x,y)=d(f(x),f(y)>d(x,y)$, which is absurd. Then, $x$ must be unique.

Now I have to prove existence and here I had problems:

First I've tried to prove it trying to repeat the standard proof of the fixed point theorem on a complete m.e. with $f$ being a contraction, I mean:

Let $x$ be an arbitrary element in M, I've defined a sequence $\{x_n\}_{n \in \mathbb N} : x_1=x, x_2=f(x_1)=f(x), x_3=f(x_2)=f^2(x_1)$ and, in general, $x_n=f(x_{n-1})=f^{n-1}(x)$.

As $M$ is compact, there exists $\{x_{n_k}\}_{k \in \mathbb N}$ a convergent subsequence of $\{x_n\}_{n \in \mathbb N}$. Then, $x_{n_k} \to z$. I would love to apply $f$ and say $z=lim_{k \to \infty} x_{n_{k+1}}=f(lim_{k \to \infty} x_{k_n})=f(z)$ (using that $f$ is continuous), but then I've realized this is completely wrong as $f(x_{n_k})=x_{n_k+1}≠x_{n_{k+1}}$.

My instinct is to prove that $f$ is invertible, and apply the contraction mapping theorem to $f^{-1}$. However it's not that straightforward.
Certainly $f$ is injective: if $x \neq y$ then we have $d(f(x),f(y)) > d(x,y) > 0$ so that necessarily $f(x) \neq f(y)$.

Unfortunately we are not given that $f$ is surjective (although maybe compactness combined with the condition on $f$ requires that; I haven't been able to show that myself). It is however sufficient to find a subset $U \subset M$ such that $f(U) = U$. The function $f_{U}: U \to U : x \mapsto f(x)$ will then be invertible.

How to find such a $U$? We have a sequence of nested non-empty closed subsets
$$M = f^0(M) \supseteq f(M) \supseteq \dots \supseteq f^n(M) \supseteq \dots$$
and one thing to try is to consider the intersection
$$I = \bigcap_{n=0}^{\infty} f^n(M)$$
which is non-empty by Cantor's intersection theorem. Certainly any fixed point of $f$ must be in this intersection. If we can show that $f(I) = I$ then we will be done.

 

[mahler1]

My instinct is to prove that $f$ is invertible, and apply the contraction mapping theorem to $f^{-1}$. However it's not that straightforward.
Certainly $f$ is injective: if $x \neq y$ then we have $d(f(x),f(y)) > d(x,y) > 0$ so that necessarily $f(x) \neq f(y)$.

Unfortunately we are not given that $f$ is surjective (although maybe compactness combined with the condition on $f$ requires that; I haven't been able to show that myself). It is however sufficient to find a subset $U \subset M$ such that $f(U) = U$. The function $f_{U}: U \to U : x \mapsto f(x)$ will then be invertible.

How to find such a $U$? We have a sequence of nested non-empty closed subsets
$$M = f^0(M) \supseteq f(M) \supseteq \dots \supseteq f^n(M) \supseteq \dots$$
and one thing to try is to consider the intersection
$$I = \bigcap_{n=0}^{\infty} f^n(M)$$
which is non-empty by Cantor's intersection theorem. Certainly any fixed point of $f$ must be in this intersection. If we can show that $f(I) = I$ then we will be done.

Hmm, I don't know how to prove that $I=\bigcap_{n=0}^{\infty} f^n(M)$ satisfies $I=f(I)$. Suppose I could prove $I=f(I)$, is it true that $I$ is compact?, because if not, all I am going to write is absolutely wrong:
Lets prove that $I$ consists of only one point. Suppose there is more than one element. Define $f:I \times I \to \mathbb R$ as $f(x,y)=d(x,y)$,$f$ is a continuous function on a compact metric space (cartesian product of compact sets is compact), then attains a maximum. Then, there exist $x_1,x_2$ such that $diam(I)=d(x_1,x_2)$. By hypothesis, there are $y_1, y_2 \in I: f(x_1)=y_1, f(x_2)=y_2$, but $d(x_1,x_2)<d(f(x_1),f(x_2))$, which is absurd by definition of diameter.

As $I$ consists of only one point, then we have $\{x\}=I=f(I)=\{f(x)\}$.

So, we've proved existence by defining that nested sequence of sets. In my first post I've proved unicity. Now there are two things left to prove: how can I show that $I=f(I)$? and, is it true that $I$ is compact?

Your previous answer was very helpful, pasmith. Thanks!

 

[Dick]

Hmm, I don't know how to prove that $I=\bigcap_{n=0}^{\infty} f^n(M)$ satisfies $I=f(I)$. Suppose I could prove $I=f(I)$, is it true that $I$ is compact?, because if not, all I am going to write is absolutely wrong:
Lets prove that $I$ consists of only one point. Suppose there is more than one element. Define $f:I \times I \to \mathbb R$ as $f(x,y)=d(x,y)$,$f$ is a continuous function on a compact metric space (cartesian product of compact sets is compact), then attains a maximum. Then, there exist $x_1,x_2$ such that $diam(I)=d(x_1,x_2)$. By hypothesis, there are $y_1, y_2 \in I: f(x_1)=y_1, f(x_2)=y_2$, but $d(x_1,x_2)<d(f(x_1),f(x_2))$, which is absurd by definition of diameter.

As $I$ consists of only one point, then we have $\{x\}=I=f(I)=\{f(x)\}$.

So, we've proved existence by defining that nested sequence of sets. In my first post I've proved unicity. Now there are two things left to prove: how can I show that $I=f(I)$? and, is it true that $I$ is compact?

Your previous answer was very helpful, pasmith. Thanks!

You just put your finger on the problem. If M is compact then d:MxM->R attains a maximum. So M must consist of a single point for the reasons you just indicated. So it obviously has a trivial fixed point. I notice 'compact' is only in the title of the thread and your proof. The statement you quoted doesn't mention 'compact'.

 

[mahler1]

You just put your finger on the problem. If M is compact then d:MxM->R attains a maximum. So M must consist of a single point for the reasons you just indicated. So it obviously has a trivial fixed point. I notice 'compact' is only in the title of the thread and your proof. The statement you quoted doesn't mention 'compact'.

Oh, that's simply because I'm an idiot and I didn't notice that I haven't wrote $M$ a COMPACT metric space. That is one of the hypothesis of the problem, and now I cannot edit my original post :(

Wait, now that it's been clarified $M$ is compact, the function I've defined is from $I \times I \to \mathbb R$, I need compactness of $I$ to say the function attains a maximum

 

[mahler1]

Homework Statement .

Let $(M,d)$ be a metric space and let $f:M \to M$ be a continuous function such that $d(f(x),f(y))>d(x,y)$ for every $x, y \in M$ with $x≠y$. Prove that $f$ has a unique fixed point

The attempt at a solution.

The easy part is always to prove unicity. Suppose there exist $x,y$, $x≠y$ : $x$ and $y$ are both fixed points. Then $d(x,y)=d(f(x),f(y)>d(x,y)$, which is absurd. Then, $x$ must be unique.

Now I have to prove existence and here I had problems:

First I've tried to prove it trying to repeat the standard proof of the fixed point theorem on a complete m.e. with $f$ being a contraction, I mean:

Let $x$ be an arbitrary element in M, I've defined a sequence $\{x_n\}_{n \in \mathbb N} : x_1=x, x_2=f(x_1)=f(x), x_3=f(x_2)=f^2(x_1)$ and, in general, $x_n=f(x_{n-1})=f^{n-1}(x)$.

As $M$ is compact, there exists $\{x_{n_k}\}_{k \in \mathbb N}$ a convergent subsequence of $\{x_n\}_{n \in \mathbb N}$. Then, $x_{n_k} \to z$. I would love to apply $f$ and say $z=lim_{k \to \infty} x_{n_{k+1}}=f(lim_{k \to \infty} x_{k_n})=f(z)$ (using that $f$ is continuous), but then I've realized this is completely wrong as $f(x_{n_k})=x_{n_k+1}≠x_{n_{k+1}}$.

One of the hypothesis of the exercise is that $M$ is a compact metric space, I've forgot to write that.

 

[Dick]

One of the hypothesis of the exercise is that $M$ is a compact metric space, I've forgot to write that.

Sure, sure. But if M is compact, doesn't your argument show M consists of a single point? Forget I.

 

[mahler1]

Sure, sure. But if M is compact, doesn't your argument show M consists of a single point?

Yes, but my argument is based on the fact that $I=f(I)$ and that $I$ is compact, these are two facts I've assumed to be true without proving them because I didn't know how to.

I had another idea to prove the statement without using Cantor's intersection theorem but there is something that doesn't convince me, if you want/can check it, maybe you realize where my mistake is:

In a previous post I've proved that if a fixed point exists, then it must be unique. Now I want to prove existence:
Consider $f:M \to \mathbb R$ defined as $f(x)=d(x,f(x))$. Since $f$ is continuous, $f$ attains a maximum. Let $x$ be te point where $f$ attains it maximum and let $D$ be the maximum, $D=d(x,f(x))$, if $D=0 \implies d(x,f(x))=0 \implies x=f(x)$, so we are done. If $D>0$, then by hypothesis, $D=d(x,f(x))<d(f(x),f(f(x)))$, which is absurd since $D$ is the maximum. Then it must be $D=0$ and $x=f(x)$.

If I read this proof, I think it's correct, but one conclusion of this proof is that for any $z \in M$, $0≤d(z,f(z)≤d(x,f(x))=D=0$, then $d(z,f(z))=0$ for every $z$ so all the points are fixed points!. There must be something wrong here and I can't see where.

 

[Dick]

Yes, but my argument is based on the fact that $I=f(I)$ and that $I$ is compact, these are two facts I've assumed to be true without proving them because I didn't know how to.

I had another idea to prove the statement without using Cantor's intersection theorem but there is something that doesn't convince me, if you want/can check it, maybe you realize where my mistake is:

In a previous post I've proved that if a fixed point exists, then it must be unique. Now I want to prove existence:
Consider $f:M \to \mathbb R$ defined as $f(x)=d(x,f(x))$. Since $f$ is continuous, $f$ attains a maximum. Let $x$ be te point where $f$ attains it maximum and let $D$ be the maximum, $D=d(x,f(x))$, if $D=0 \implies d(x,f(x))=0 \implies x=f(x)$, so we are done. If $D>0$, then by hypothesis, $D=d(x,f(x))<d(f(x),f(f(x)))$, which is absurd since $D$ is the maximum. Then it must be $D=0$ and $x=f(x)$.

If I read this proof, I think it's correct, but one conclusion of this proof is that for any $z \in M$, $0≤d(z,f(z)≤d(x,f(x))=D=0$, then $d(z,f(z))=0$ for every $z$ so all the points are fixed points!. There must be something wrong here and I can't see where.

All points are fixed points, and there aren't many of them. d:MxM->R is a continuous function from the compact space MxM into R. So it attains a maximum. So there is a D (diam(M)) such that d(x,y)<=D for all x and y in M. There is also an x' and y' such that d(x',y')=D. That d(f(x'),f(y'))>d(x',y')=D is obvious rubbish. So x'=y' and D=0. M consists of a single point. It's the same argument you applied to I.

 

[mahler1]

All points are fixed points, and there aren't many of them. d:MxM->R is a continuous function from the compact space MxM into R. So it attains a maximum. So there is a D (diam(M)) such that d(x,y)<=D for all x and y in M. There is also an x' and y' such that d(x',y')=D. That d(f(x'),f(y'))>d(x',y')=D is obvious rubbish. So x'=y' and D=0. M consists of a single point. It's the same argument you applied to I.

Ooooh, so the conclusion of my proof would be $|M|=1$, I thought about it but I still kept suspecting there was something wrong with the proof. Thanks!

 

[Dick]

Ooooh, so the conclusion of my proof would be $|M|=1$, I thought about it but I still kept suspecting there was something wrong with the proof. Thanks!

Welcome! The whole thing does seem like kind of a cheat. Didn't need to use f is continuous. Etc, etc. I still wonder if they didn't mean to ask a somewhat different question. But it is true that compact metric spaces don't have mappings like that. Unless the metric space is has a single point.