Good Math, Bad Math

If you've got a connected topology, there are some neat things you can show about it. One of the interesting ones involves fixed points. Today I'm going to show you a few of the relatively simple fixed point properties of basic connected topologies.

To give you a taste of what's coming: imagine that you have two sheets of graph paper, with the edges numbered with a coordinate system. So you can easily identify any point on the sheet of paper. Take one sheet, and lay it flat on the table. Take the second sheet, and crumple it up into a little ball. No matter how you crumple the paper into a ball, no matter where you put it down on the uncrumpled sheet, there will be at least one point on the crumpled ball of paper which is directly above the point with the same coordinate on the flat sheet.

As a quick aside: today is Yom Kippur, which means that this post is scheduled, and I'm not anywhere near my computer. So I won't be able to make any corrections or answer any comments until late this evening.

We'll start by defining a fixed point. If you've got a function from a set X to itself, f : X → X, then a fixed point of f is a value p ∈ X such that f(p) = p.

The simplest fixed point theorem is one that looks at the topology of the real line. Suppose we take the closed interval, [0,1] on the real line, and look at the topology defined on it by the standard metric. In this topology, if we have a function f : [0,1] → [0,1], then if f is continuous, it must have a fixed point.

If you think about it carefully, you should be able to see why this is true. But to show it formally, it's a bit trickier. Not a lot trickier, but a bit tricker. We'll use something called the intermediate value theorem (IVT). The IVT is just a more general statement of our simple fixed point theorem, but it's easier to prove the IVT, and then the fixed point theorem just falls out as a trivial corollary.

Suppose you have a continuous function from a closed interval [a,b] to the real numbers: f : [a,b] → ℜ, and that f(a) ≠ f(b). Then for all v ∈ [f(a),f(b)], there is some value x ∈ [a,b] such that f(x)=v.

How can we prove that? Since we know that [a,b] is a closed, connected interval, and f is continuous, that means that f([a,b]) is also an interval. Further, since f(a) ∈ f([a,b]) and f(b) ∈ f([a,b]), and f([a,b]) is an interval, that means that the entire range of values between f(a) and f(b) is a subset of the interval f([a,b]). Again taking advantage of the continuity property of f, that means that for any value v between f(a) and f(b), there is some value x between a and b where f(x)=v.

To get from there to the fixed point theorem, we use the IVT to look at the interval [0,1]. Either f(0)=0; f(1)=1; or f(x)=x for some x, 0 ≤ x ≤ 1. The first two cases are trivially true. So we just need to think about that third case.

So, let's define a new function, g(x) : [0,1] → ℜ = x - f(x). Now, we know that g(0) < 0 - because we're looking at the case where f(0) ≠ 0, and f(x) only ranges from 0 to 1 - so f(0)>0; and therefore g(0)=0-f(0)<0. By the same kind of reasoning, we know that g(1)>0. By the IVT, then, there must be some value x where g(x)=0 - and that x is, by definition, the point where x=f(x).

We can easily generalize that fixed point theorem to get it to something more interesting that just the real line. Suppose that we have two topological spaces S and T. If S and T are homeomorphic, then all continuous functions f : S → S have fixed points if/f all continuous functions g : T → T have fixed points. You can see the basic idea of the proof of that using the simple category diagram below, where a and b are the continuous functions that define the homeomorphism; just chase through the paths, and you should be able to see that it's a commutative diagram, and that it's commutativity proves this theorem.

This brings us, at last, to the strongest fixed point theorem yet, called the Brouwer Fixed Point Theorem, which combined with the earlier homeomorphism theorem gives us an extremely powerful result.

Consider the euclidean topological space ℜⁿ. Within that space, we can define a unit cube Iⁿ. The Brouwer fixed point theorem says that for any unit cube Iⁿ, every continuous function f : Iⁿ → Iⁿ, contains a fixed point i ∈ Iⁿ such that f(i) = i.

So what we've gotten to is that continuous functions within anything homeomorphic to a unit cube in any number of dimensions have fixed points. That's a pretty profound fact.

Why does that matter? Why should we care?

My own first contact with topology came from studying the semantics of programming languages. One of the best ways of precisely describing the semantics of a programming language is called denotational semantics. Like many applications of topology, denotational semantics can describe the kinds of value-spaces on which it makes sense in terms of topology. One of the critical properties of the value-spaces over which denotational semantics is valid is that it contain fixed points.

Like denotational semantics, there are many applications of topology that require value spaces that include fixed points; so knowing that any continuous function within anything homeomorphic to a unit cube gives us a great handle on what spaces are usable for those applications.