Wednesday, July 29, 2009

Math Time

Apropos of nothing, I want to talk about the Brouwer fixed point theorem.

This theory states, basically, there is at least one point on that function that sends the point to itself. That is, there is always at least one point x such that, for a function f, f(x) = x.

I find this property of life so unequivocally awesome that I have to talk about it.

What this theorem shows is that regardless of how you manipulate the world around you, something will end up back where it started.

Let's start simple...

1. Imagine you had a flat map of your country sitting in front of you...or, indeed, dear reader, go get one now. Were you to drop it on the ground, there would be, without a doubt, one point on that map that was directly above the point it represented no matter the scale of the map as long as one sat inside the other.

2. Alternatively, take two pieces of paper with identical pictures on them, crumble one up and place it on top of the other piece of paper. At least one point on the crumbled up piece of paper would be sitting above its corresponding point.

3. Let's say you had a cup of coffee and a spoon. After stirring your coffee, there would always be at least ONE atom of coffee in that cup that was in the exact same place as where it began.

4. This property is also the reason why you could never have a tie in a game of Hex.

As for the proof itself, it's omfg a head tripsomewhat difficult to understand if you don't know the jargon*.

The proof is normally done by contradiction--that is, we try to prove the opposite (i.e. that there are no fixed points) in the hopes that we find a result that shouldn't exist.

Effectively, we begin by saying "Assume there is no fixed point" and then try to "break" the proof using what we already know. If we can show that saying there is no fixed point is absurd, then there can only be one recourse...that there is at least one fixed point somewhere.

Interestingly enough, later Brouwer rejected this proof because he felt that all proofs must be "constructed." That is to say, he felt that proof by contradiction was cheating and that if you are going to prove something, you should do it directly--which he did end up doing for some proofs, including, eventually, the Fixed Point Theorem**.

I hope you feel more enlightened now.

*I know the feeling quite well. My first time being given this proof was in a special guest lecture about the history of proof. It whizzed by me so fast that when I copied it down, even now it makes no sense...which is a terrible shame.

**Which was, I'm sure, awesome for him. Even I don't want to touch that one.

9 comments:

  1. Does it work only for 2D or has it been extended to n-dimensions? I can look it up, but if you have it on the tip o'your brain...

    ReplyDelete
  2. @ The skepTick

    Actually, yes. This theorem is extended to n-dimensions.

    You might want to look at the wikipedia page for more information that I left out.

    http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem

    It has a lot of interesting facts and most of the explanations are in as plain of speech as it can be.

    ReplyDelete
  3. wouldn't the function have to be continuous?

    well obviously. f(x)={0 for x != 0 ^ 1 for x = 0} CLEARLY doesn't follow the theorem.

    And consequently, wouldn't you need to have a little more proving to do first in your coffee example, i.e., prove that the stirring mapped to a continuous function?

    ReplyDelete
  4. ugh... I think it ate a post.

    Anyway, I imagine the theorem actually requires a continuous function, because it's trivial to construct a discontinuous function defying the theorem. Therefore your coffee example is VERY suspect 'cuz you're going to have to convince me that stirring maps to a continuous function...

    ReplyDelete
  5. @jemand

    Indeed, it does have to be continuous.

    As for the coffee example, it's not something that I have the ability to prove...but there is at least one fixed point in that coffee cup...if only because the fixed point theorem has indeed been proven for R3.

    Next time you have a cup and a liquid, give it a stir or two. There should be one point on the surface around which everything rotates.

    ReplyDelete
  6. ok, you've convinced me that you are correct if we're only dealing with the spoon, but I've spent the last few minutes trying to figure out if you are correct when accounting for Brownian motion.

    Somehow that seems like it would come into play a lot more in the coffee example than the two dimensional solid objects. I'm trying to figure out if each atom stochastically moving is still going to be part of a continuous function and I'm kinda doubting it but I really don't know. They aren't teleporting so now I think it probably is continuous.

    Annoying reality! lol.

    Btw, your blog is awesome. Math is awesome. What are your favorite topics? I was having lots of fun with measure theory and metric spaces and set theory and then I had to go graduate and now I'll only be taking physics classes. :(

    ReplyDelete
  7. I really like set theory, though my math has only just in these last couple semesters ceased to be incredibly spotty. I took an intro to Topology as an independent study with my favorite professor which ended up being sort of a general intro to higher math and analysis.

    I've come to really really like analysis and that has sort of fueled the other aspects of my life including teaching and the whole atheism thing.

    Also, if you are having trouble thinking about three dimensional fixed points try looking up Hairy Ball Theory as it is somewhat of a realization of the fixed point theory.

    http://en.wikipedia.org/wiki/Hairy_ball_theorem

    Hope this helps!

    ReplyDelete