5
$\begingroup$

I could prove the following result from my Real Analysis course:

Let $f:[0,1] \rightarrow [0,1]$ be an increasing mapping. Then it has a fixed point.

I understand that this is a very baby version of Tarski’s Fixed Point Theorem. Now, I wish to generalize this a little bit and get the following:

Let $f:[0,1]^n \rightarrow [0,1]^n$ in which $f$ is increasing in the sense that if $y \geq x$ coordinate wise then $f(y) \geq f(x)$ coordinate wise. Then, f has a fixed point.

From my point of view, we could just pick a point $x_0 \in [0,1]^n$, fix all coordinates but one and apply the above lemma to that coordinate. Then, when the first coordinate of the fixed point is found, we do the same for the second and so on.

However, I am not sure this route would be successful and even if it is, I can’t write the extension formally. Any ideas? Thanks a lot in advance!

$\endgroup$
  • $\begingroup$ Note that $f(\cdot,x_2) : [0,1]\to [0,1]^2$ for fixed $x_2$. $\endgroup$ – amsmath Aug 28 at 3:08
  • $\begingroup$ I tried to go through your route. But the range is not ordered anyway. I could fix $x_2$ in the range too, and I would have a mapping from $[0,1]$ as before. But then I would have a fixed point whose second coordinate is $x_2$. As $x_2$ was arbitrary, this would prove that we would have uncountable many fixed points, right? It seems too strong. What am I missing @amsmath? $\endgroup$ – Raul Guarini Aug 28 at 3:15
  • $\begingroup$ I was trying to say that you cannot apply your lemma to that function because it does not map [0,1] to itself. $\endgroup$ – amsmath Aug 28 at 3:17
  • $\begingroup$ Ok, thank you! Do you have another idea to generalize this result then? @amsmath $\endgroup$ – Raul Guarini Aug 28 at 3:20
4
$\begingroup$

The "baby version" is not sufficient to obtain your result for $n > 1$ as a corollary. This is possible only in case that $f : [0,1]^n \to [0,1]^n$ has the special form $$f(x_1,\dots,x_n) = (\phi_1(x_1),\dots,\phi_n(x_n))$$ with continuous increasing $\phi_i : [0,1] \to [0,1]$. But in general $f$ has the form $$f(x_1,\dots,x_n) = (f_1(x_1,\dots,x_n),\dots,f_n(x_1,\dots,x_n))$$ where each $f_i :[0,1]^n \to [0,1]$ depends on all variables.

In fact, your result is true, but you will need a new proof. See Asaf Karagila's answer.

Let me close with a remark concerning your strategy to find a fixed point. It is not expedient to pick some $x_0 =(x^0_1,\dots,x^0_n)$ and to consider the functions obatined by fixing all but one coordinate. Let us see what happens for $n=2$. You consider the function $f^1 : [0,1] \to [0,1], f^1(x) = f_1(x,x^0_2)$ and conclude that it has a fixed point $\xi_1$, i.e. $f_1(\xi_1,x^0_2) = \xi_1$. Next you consider $f^2 : [0,1] \to [0,1], f^2(x) = f_1(x^0_1,x)$ and conclude that it has a fixed point $\xi_2$, i.e. $f_2(x^0_1,\xi_2) = \xi_2$. But there is no reason why you should have $f(\xi_1,\xi_2) = (\xi_1,\xi_2)$.

$\endgroup$
3
$\begingroup$

The Knaster–Tarski fixed point theorem states that:

Suppose that $(L,\leq)$ is a complete lattice and $f\colon L\to L$ is increasing, i.e. $x\leq y\implies f(x)\subseteq f(y)$. Then $\{x\in L\mid f(x)=x\}$ is a complete lattice under the induced order.

Note that a complete sublattice cannot be empty, since $\varnothing$ must have a supremum and infimum (which make the bottom and top elements of the lattice).


Note that $[0,1]$ is a complete lattice, and $[0,1]^n$ is also a complete lattice. Granted, now, most uses of this theorem really just care that there is a fixed point. This is commonly used in the proof of the Cantor–Bernstein theorem when we want to find a set closed under some function.

Just finding a fixed point is easy. Let $D=\{x\in L\mid x\geq f(x)\}$ and let $s=\inf D$. Even if $D$ is empty, it still has a infimum, it would just be the top element of $L$. This is because $L$ is a complete lattice.

Now, if $s<x$, then $f(s)\leq f(x)$. Since this holds for all $x\in D$, it follows that $f(s)\leq s$, by the virtue of being an infimum. Therefore $s\in D$, and it is in fact a minimum. But now we have that $f^2(s)\leq f(s)\leq s$. So $f(s)\in D$ as well, which means that $s\leq f(s)$—again by the virtue of being an infimum—and therefore $f(s)=s$. We can even show that $s$ is the smallest fixed point, i.e. the bottom element of the fixed points lattice.


If we assume continuity of $f$, in the sense that it respects the $\sup$ operator, we get an even easier proof of what is known as the Kleene fixed points theorem.

Let's use $0$ to denote the bottom element of $L$. Then $0\leq f(0)\leq f^2(0)\leq ...$, let $x=\sup\{f^n(0)\mid n\in\Bbb N\}$, which exists since $L$ is a complete lattice. Since $f$ is continuous we get that $$f(x)=f(\sup\{f^n(0)\mid n\in\Bbb N\}) = \sup\{f(f^n(0)\mid n\in\Bbb N\}=\sup\{f^{n+1}(0)\mid n\in\Bbb N\}=x.$$


Finally, we apply these proofs to your question. And you can see that this is essentially the same proof for both $[0,1]$ and $[0,1]^n$. And in fact, much much more.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.