Content deleted Content added
Erel Segal (talk | contribs) Computing a fixed point |
|||
Line 4:
</math> of [[Euclidean space]] to itself.
Among hundreds of [[fixed-point theorem]]s,<ref>E.g. F & V Bayart ''[http://www.bibmath.net/dico/index.php3?action=affiche&quoi=./p/pointfixe.html Théorèmes du point fixe]'' on Bibm@th.net {{webarchive|url=https://web.archive.org/web/20081226200755/http://www.bibmath.net/dico/index.php3?action=affiche&quoi=.%2Fp%2Fpointfixe.html |date=December 26, 2008 }}</ref> Brouwer's is particularly well known, due in part to its use across numerous fields of mathematics.In its original field, this result is one of the key theorems characterizing the topology of Euclidean spaces, along with the [[Jordan curve theorem]], the [[hairy ball theorem]], the [[invariance of dimension]] and the [[Borsuk–Ulam theorem]].<ref>See page 15 of: D. Leborgne ''Calcul différentiel et géométrie'' Puf (1982) {{ISBN|2-13-037495-6}}</ref> This gives it a place among the fundamental theorems of topology.<ref>More exactly, according to Encyclopédie Universalis: ''Il en a démontré l'un des plus beaux théorèmes, le théorème du point fixe, dont les applications et généralisations, de la théorie des jeux aux équations différentielles, se sont révélées fondamentales.'' [http://www.universalis.fr/encyclopedie/T705705/BROUWER_L.htm Luizen Brouwer] by G. Sabbagh</ref> The theorem is also used for proving deep results about [[differential equation]]s and is covered in most introductory courses on [[differential geometry]]. It appears in unlikely fields such as [[game theory]]. In economics, Brouwer's fixed-point theorem and its extension, the [[Kakutani fixed-point theorem]], play a central role in the [[Arrow–Debreu model|proof of existence]] of [[general equilibrium]] in market economies as developed in the 1950s by economics Nobel prize winners [[Kenneth Arrow]] and [[Gérard Debreu]].
The theorem was first studied in view of work on differential equations by the French mathematicians around [[Henri Poincaré]] and [[Charles Émile Picard]]. Proving results such as the [[Poincaré–Bendixson theorem]] requires the use of topological methods. This work at the end of the 19th century opened into several successive versions of the theorem. The case of differentiable mappings of the {{mvar|''n''}}-dimensional closed ball was first proved in 1910 by [[Jacques Hadamard]]<ref name="hadamard-1910">[[Jacques Hadamard]]: ''[https://archive.org/stream/introductionla02tannuoft#page/436/mode/2up Note sur quelques applications de l’indice de Kronecker]'' in [[Jules Tannery]]: ''Introduction à la théorie des fonctions d’une variable'' (Volume 2), 2nd edition, A. Hermann & Fils, Paris 1910, pp. 437–477 (French)</ref> and the general case for continuous mappings by Brouwer in 1911.<ref name="brouwer-1910">{{cite journal | last1 = Brouwer | first1 = L. E. J. | author-link = Luitzen Egbertus Jan Brouwer | year = 1911| title = Über Abbildungen von Mannigfaltigkeiten | url = http://resolver.sub.uni-goettingen.de/purl?GDZPPN002264021 | journal = [[Mathematische Annalen]] | volume = 71 | pages = 97–115 | doi = 10.1007/BF01456931 | s2cid = 177796823 | language = de }}</ref>
Line 49 ⟶ 46:
Convexity is not strictly necessary for BFPT. Because the properties involved (continuity, being a fixed point) are invariant under [[homeomorphism]]s, BFPT is equivalent to forms in which the ___domain is required to be a closed unit ball <math>D^n</math>. For the same reason it holds for every set that is homeomorphic to a closed ball (and therefore also [[closed set|closed]], bounded, [[connected space|connected]], [[simply connected|without holes]], etc.).
The following example shows that BFPT does not work for domains with holes. Consider the function <math>f(x)=-x</math>, which is a continuous function from the unit circle to itself. Since ''-x≠x'' holds for any point of the unit circle, ''f'' has no fixed point. The analogous example works for the ''n''-dimensional sphere (or any symmetric ___domain that does not contain the origin). The unit circle is closed and bounded, but it has a hole (and so it is not convex) . The function ''f'' {{em|does}} have a fixed point for the unit disc, since it takes the origin to itself.
A formal generalization of BFPT for "hole-free" domains can be derived from the [[Lefschetz fixed-point theorem]].<ref>{{cite web | url=https://math.stackexchange.com/q/323841 | title=Why is convexity a requirement for Brouwer fixed points? | publisher=Math StackExchange | access-date=22 May 2015 | author=Belk, Jim}}</ref>
===Notes===
The continuous function in this theorem is not required to be [[bijective]] or
==Illustrations==
Line 117 ⟶ 113:
Other areas are also touched. In [[game theory]], [[John Forbes Nash|John Nash]] used the theorem to prove that in the game of [[Hex (board game)|Hex]] there is a winning strategy for white.<ref>For context and references see the article [[Hex (board game)]].</ref> In economics, P. Bich explains that certain generalizations of the theorem show that its use is helpful for certain classical problems in game theory and generally for equilibria ([[Hotelling's law]]), financial equilibria and incomplete markets.<ref>P. Bich ''[http://www.ann.jussieu.fr/~plc/code2007/bich.pdf Une extension discontinue du théorème du point fixe de Schauder, et quelques applications en économie] {{webarchive |url=https://web.archive.org/web/20110611140634/http://www.ann.jussieu.fr/~plc/code2007/bich.pdf |date=June 11, 2011 }}'' Institut Henri Poincaré, Paris (2007)</ref>
Brouwer's celebrity is not exclusively due to his topological work. The proofs of his great topological theorems are [[constructive proof|not constructive]],<ref>For a long explanation, see: {{cite journal |first=J. P. |last=Dubucs |url=http://www.persee.fr/web/revues/home/prescript/article/rhs_0151-4105_1988_num_41_2_4094 |title=L. J. E. Brouwer : Topologie et constructivisme |journal=Revue d'Histoire des Sciences |volume=41 |issue=2 |pages=133–155 |year=1988 |doi=10.3406/rhs.1988.4094 }}</ref> and Brouwer's dissatisfaction with this is partly what led him to articulate the idea of [[constructivism (mathematics)|constructivity]]. He became the originator and zealous defender of a way of formalising mathematics that is known as [[intuitionistic logic|intuitionism]], which at the time made a stand against [[set theory]].<ref>Later it would be shown that the formalism that was combatted by Brouwer can also serve to formalise intuitionism, with some modifications. For further details see [[constructive set theory]].</ref> Brouwer disavowed his original proof of the fixed-point theorem.
==Proof outlines==
Line 228 ⟶ 224:
===A proof in a weak logical system===
In [[reverse mathematics]], Brouwer's theorem can be proved in the system [[Weak König's lemma|WKL<sub>0</sub>]], and conversely over the base system [[reverse mathematics|RCA<sub>0</sub>]] Brouwer's theorem for a square implies the [[weak König's lemma]], so this gives a precise description of the strength of Brouwer's theorem.
== Computing a fixed point ==
The first algorithm to approximate a fixed point was proposed by [[Herbert Scarf]].<ref>{{Cite journal |last=Scarf |first=Herbert |date=1967-09-01 |title=The Approximation of Fixed Points of a Continuous Mapping |url=http://epubs.siam.org/doi/10.1137/0115116 |journal=SIAM Journal on Applied Mathematics |language=en |volume=15 |issue=5 |pages=1328–1343 |doi=10.1137/0115116 |issn=0036-1399}}</ref><ref>H. Scarf found the first algorithmic proof: {{SpringerEOM|title=Brouwer theorem|first=M.I.|last=Voitsekhovskii|isbn=1-4020-0609-8}}.</ref> A subtle aspect of Scarf's algorithm is that it finds a point that is {{em|almost fixed}} by a function ''f'', but in general cannot find a point that is close to an actual fixed point. In mathematical language, if {{mvar|ε}} is chosen to be very small, Scarf's algorithm can be used to find a point ''x'' such that ''f''(''x'') is very close to ''x'', i.e., <math>d(f(x),x) < \varepsilon </math>. But Scarf's algorithm cannot be used to find a point ''x'' such that ''x'' is very close to a fixed point: we cannot guarantee <math>d(x,y) < \varepsilon,</math> where <math>f(y)=y.</math> Often this latter condition is what is meant by the informal phrase "approximating a fixed point"{{Citation needed|date=August 2019}}.
==Generalizations==
| |||