What do these fixed points have in common?
A question asked while standing in the shower: What do all of the following have in common?
- Banach and Brouwer fixed points. If you’re in Manhattan, and you crumple up a map of Manhattan and place it on the ground, at least one point on your map will be exactly over the corresponding point on the ground. (This is true even if your map is larger than life.)
- The fixed points computed by the Y combinator, which is used to construct anonymous recursive functions in the lambda calculus.
- The Nash equilibrium, which is the stable equilibrium of a multi-player game (and one of the key ideas of economics). See also this lovely—if metaphorical—rant by Scott Aaronson.
- The eigenvectors of a matrix, which will still point in the same direction after multiplication by the matrix.
At what level of abstraction are all these important ideas really just the same idea? If we strip everything down to generalized abstract nonsense, is there a nice simple formulation that covers all of the above?
(I can’t play with this shiny toy today; I have to work.)
Want to contact me about this article? Or if you're looking for something else to read, here's a list of popular posts.
Derek Elkins
wrote on May 12, 2011:
There's a "small" (categorical) diagram that is rarely talked about that is relevant here. The popular examples are empty diagrams, finite diagrams of discrete points, parallel pairs of arrows, and wedges. The colimits of those are, respectively, initial objects, coproducts, coequalizers, and pushouts. There is another notable diagram however, the loop. Barry Jay has a couple of papers on the limits and colimits of a diagram of this form. I don't know if this will capture all of these examples (in particular, the Nash equilibria would take a bit of twisting I'd think), but it certainly is a place to start.
Eric
wrote on May 12, 2011:
Thank you for the pointer! I'll try to dig up those papers when I have time to play with this stuff a bit.
Some related links of interest:
1. The Wikipedia article on [fixed-point theorems](http://en.wikipedia.org/wiki/Fixed_point_theorem).
2. A MathOverflow question about the [relation between two of the big fixed-point theorems](http://mathoverflow.net/questions/34511/banach-and-knaster-tarski-fixed-point-theorems-are-they-related).
Nash equilibria can apparently be [derived from Brouwer fixed points](http://en.wikipedia.org/wiki/Nash_equilibrium#Alternate_proof_using_the_Brouwer_fixed_point_theorem), according to Wikipedia, but I haven't read the proof yet.