Brouwer fixed-point theorem: Difference between revisions

Revision as of 18:09, 17 March 2022

Latest revision as of 16:49, 13 August 2025

(48 intermediate revisions by 33 users not shown)

Line 1:

{{Short description|Theorem in topology}}

<!-- The French version of this article is a featured article. Large portions have been translated and inserted here in 2009. -->

'''Brouwer's fixed-point theorem''' is a [[fixed-point theorem]] in [[topology]], named after [[Luitzen Egbertus Jan Brouwer|L. E. J. (Bertus) Brouwer]]. It states that for any [[continuous function]] <math>f</math> mapping a nonempty [[compactness|compact]] [[convex set]] to itself, there is a point <math>x_0</math> such that <math>f(x_0)=x_0</math>. The simplest forms of Brouwer's theorem are for continuous functions <math>f</math> from a closed interval <math>I</math> in the real numbers to itself or from a closed [[Disk (mathematics)|disk]] <math>D</math> to itself. A more general form than the latter is for continuous functions from a nonempty convex compact subset <math>K

</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 [e-mail] {{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]].

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’indicel'indice de Kronecker]'' in [[Jules Tannery]]: ''Introduction à la théorie des fonctions d’uned'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>

==Statement==

Line 22 ⟶ 19:

A slightly more general version is as follows:<ref>This version follows directly from the previous one because every convex compact subset of a Euclidean space is homeomorphic to a closed ball of the same dimension as the subset; see {{cite book|title=General Equilibrium Analysis: Existence and Optimality Properties of Equilibria|first=Monique|last=Florenzano|publisher=Springer|year=2003|isbn=9781402075124|page=7|url=https://books.google.com/books?id=cNBMfxPQlvEC&pg=PA7|access-date=2016-03-08}}</ref>

:;Convex compact set:Every continuous function from a nonempty [[Convex set|convex]] [[Compact space|compact]] subset ''K'' of a Euclidean space to ''K'' itself has a fixed point.<ref>V. & F. Bayart ''[http://www.bibmath.net/dico/index.php3?action=affiche&quoi=./p/pointfixe.html Point fixe, et théorèmes du point fixe ]'' on Bibmath.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>

An even more general form is better known under a different name:

:;[[Schauder fixed point theorem]]:Every continuous function from a nonempty convex compact subset ''K'' of a [[Banach space]] to ''K'' itself has a fixed point.<ref>C. Minazzo K. Rider ''[http://math1.unice.fr/~eaubry/Enseignement/M1/memoire.pdf Théorèmes du Point Fixe et Applications aux Equations Différentielles] {{Webarchive|url=https://web.archive.org/web/20180404001651/http://math1.unice.fr/~eaubry/Enseignement/M1/memoire.pdf |date=2018-04-04 }}'' Université de Nice-Sophia Antipolis.</ref>

==Importance of the pre-conditions==

The theorem holds only for functions that are ''endomorphisms'' (functions that have the same set as the ___domain and rangecodomain) and for nonempty sets that are ''compact'' (thus, in particular, bounded and closed) and ''convex'' (or [[Homeomorphism|homeomorphic]] to convex). The following examples show why the pre-conditions are important.

===The function ''f'' as an endomorphism===

Consider the function

:<math>f(x) = x+1</math>

with ___domain [-1,1]. The range of the function is [-2,0,2]. Thus, f is not an endomorphism.

===Boundedness===

Line 44 ⟶ 41:

Consider the function

:<math>f(x) = \frac{x+1}{2},</math>

which is a continuous function from the open interval <math>(−1-1,1)</math> to itself. InSince thisthe interval,point it<math>x=1</math> shiftsis everynot pointpart toof the rightinterval, sothere itis cannotno havepoint ain fixedthe point___domain such that <math>f(x) = x</math>. The spaceset <math>(−1-1,1)</math> is convex and bounded, but not closed. TheOn the other hand, the function ''<math>f''</math> {{em|does}} have a fixed point forin the ''closed'' interval <math>[−1-1,1]</math>, namely ''f''<math>x=1</math>. The closed interval <math>[-1,1]</math> is compact, the open interval <math>(-1,1)</math> =is 1not.

===Convexity===

Convexity is not strictly necessary for BFPTBrouwer's fixed-point theorem. Because the properties involved (continuity, being a fixed point) are invariant under [[homeomorphism]]s, BFPTBrouwer's fixed-point theorem 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 Brouwer's fixed-point theorem 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.

The following example shows that BFPT doesn't 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 BFPTBrouwer's fixed-point theorem 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 even [[surjective]].

==Illustrations==

Line 62 ⟶ 58:

# Take two sheets of graph paper of equal size with coordinate systems on them, lay one flat on the table and crumple up (without ripping or tearing) the other one and place it, in any fashion, on top of the first so that the crumpled paper does not reach outside the flat one. There will then be at least one point of the crumpled sheet that lies directly above its corresponding point (i.e. the point with the same coordinates) of the flat sheet. This is a consequence of the ''n'' = 2 case of Brouwer's theorem applied to the continuous map that assigns to the coordinates of every point of the crumpled sheet the coordinates of the point of the flat sheet immediately beneath it.

# Take an ordinary map of a country, and suppose that that map is laid out on a table inside that country. There will always be a "You are Here" point on the map which represents that same point in the country.

# In three dimensions a consequence of the Brouwer fixed-point theorem is that, no matter how much you stir a delicious cocktail in a glass (or think about milk shake), when the liquid has come to rest, some point in the liquid will end up in exactly the same place in the glass as before you took any action, assuming that the final position of each point is a continuous function of its original position, that the liquid after stirring is contained within the space originally taken up by it, and that the glass (and stirred surface shape) maintain a convex volume. Ordering a cocktail [[shaken, not stirred]] defeats the convexity condition ("shaking" being defined as a dynamic series of non-convex inertial containment states in the vacant headspace under a lid). In that case, the theorem would not apply, and thus all points of the liquid disposition are potentially displaced from the original state. {{Citation needed|date=September 2018}}

==Intuitive approach==

===Explanations attributed to Brouwer===

The theorem is supposed to have originated from Brouwer's observation of a cup of gourmet coffee.<ref>The interest of this anecdote rests in its intuitive and didactic character, but its accuracy is dubious. As the history section shows, the origin of the theorem is not Brouwer's work. More than 20 years earlier [[Henri Poincaré]] had proved an equivalent result, and 5 years before Brouwer P.&nbsp;Bohl had proved the three-dimensional case.</ref>

If one stirs to dissolve a lump of sugar, it appears there is always a point without motion.

He drew the conclusion that at any moment, there is a point on the surface that is not moving.<ref name=Arte>This citation comes originally from a television broadcast: ''[https://archive.today/20130113210953/http://archives.arte.tv/hebdo/archimed/19990921/ftext/sujet5.html Archimède]'', [[Arte]], 21 septembre 1999</ref>

Line 87 ⟶ 83:

The Brouwer fixed point theorem was one of the early achievements of [[algebraic topology]], and is the basis of more general [[fixed point theorem]]s which are important in [[functional analysis]]. The case ''n'' = 3 first was proved by [[Piers Bohl]] in 1904 (published in ''[[Journal für die reine und angewandte Mathematik]]'').<ref name=Bohl1904>{{cite journal |first=P. |last=Bohl |title= Über die Bewegung eines mechanischen Systems in der Nähe einer Gleichgewichtslage |journal=J. Reine Angew. Math. |volume=127 |issue=3/4 |pages=179–276 |year=1904 }}</ref> It was later proved by [[Luitzen Egbertus Jan Brouwer|L. E. J. Brouwer]] in 1909. [[Jacques Hadamard]] proved the general case in 1910,<ref name="hadamard-1910" /> and Brouwer found a different proof in the same year.<ref name="brouwer-1910" /> Since these early proofs were all [[Constructive proof|non-constructive]] [[indirect proof]]s, they ran contrary to Brouwer's [[intuitionist]] ideals. Although the existence of a fixed point is not constructive in the sense of [[Constructivism (mathematics)|constructivism in mathematics]], methods to [[Approximation theory|approximate]] fixed points guaranteed by Brouwer's theorem are now known.<ref name=Karamardian1977>{{cite book|last1=Karamardian|first1=Stephan|title=Fixed points: algorithms and applications|date=1977|publisher=Academic Press|___location=New York|isbn=978-0-12-398050-2}}</ref><ref name=Istratescu1981>{{cite book|last1=Istrăţescu|first1=Vasile|title=Fixed point theory|date=1981|publisher=D. Reidel Publishing Co.|___location=Dordrecht-Boston, Mass.|isbn=978-90-277-1224-0}}</ref>

===PrehistoryBefore discovery===

[[File:Théorème-de-Brouwer-(cond-1).jpg|thumb|right|For flows in an unbounded area, or in an area with a "hole", the theorem is not applicable.]]

[[File:Théorème-de-Brouwer-(cond-2).jpg|thumb|left|The theorem applies to any disk-shaped area, where it guarantees the existence of a fixed point.]]

To understand the prehistory of Brouwer's fixed point theorem one needs to pass through [[differential equation]]s. At the end of the 19th century, the old problem<ref>See F. Brechenmacher ''[https://arxiv.org/abs/0704.2931 L'identité algébrique d'une pratique portée par la discussion sur l'équation à l'aide de laquelle on détermine les inégalités séculaires des planètes]'' CNRS Fédération de Recherche Mathématique du Nord-Pas-de-Calais</ref> of the [[stability of the solar system]] returned into the focus of the mathematical community.<ref>[[Henri Poincaré]] won the [[Oscar II, King of Sweden|King of Sweden]]'s mathematical competition in 1889 for his work on the related [[three-body problem]]: [[Jacques Tits]] ''[http://www.culture.gouv.fr/culture/actualites/celebrations2004/poincare.htm Célébrations nationales 2004]'' Site du Ministère Culture et Communication</ref>

Its solution required new methods. As noted by [[Henri Poincaré]], who worked on the [[three-body problem]], there is no hope to find an exact solution: "Nothing is more proper to give us an idea of the hardness of the three-body problem, and generally of all problems of Dynamics where there is no uniform integral and the Bohlin series diverge."<ref name=methodes>[[Henri Poincaré]] ''Les méthodes nouvelles de la mécanique céleste'' T Gauthier-Villars, Vol 3 p 389 (1892) new edition Paris: Blanchard, 1987.</ref>

He also noted that the search for an approximate solution is no more efficient: "the more we seek to obtain precise approximations, the more the result will diverge towards an increasing imprecision".<ref>Quotation from [[Henri Poincaré]] taken from: P. A. Miquel ''[http://www.arches.ro/revue/no03/no3art03.htm La catégorie de désordre] {{Webarchive|url=https://web.archive.org/web/20160303205947/http://www.arches.ro/revue/no03/no3art03.htm# |date=2016-03-03 }}'', on the website of l'Association roumaine des chercheurs francophones en sciences humaines</ref>

Line 96 ⟶ 92:

He studied a question analogous to that of the surface movement in a cup of coffee. What can we say, in general, about the trajectories on a surface animated by a constant [[flow (mathematics)|flow]]?<ref>This question was studied in: {{cite journal |first=H. |last=Poincaré |title=Sur les courbes définies par les équations différentielles |journal=[[Journal de Mathématiques Pures et Appliquées]] |volume=2 |issue=4 |pages=167–244 |year=1886 }}</ref> Poincaré discovered that the answer can be found in what we now call the [[topology|topological]] properties in the area containing the trajectory. If this area is [[compact space|compact]], i.e. both [[closed set|closed]] and [[bounded set|bounded]], then the trajectory either becomes stationary, or it approaches a [[limit cycle]].<ref>This follows from the [[Poincaré–Bendixson theorem]].</ref> Poincaré went further; if the area is of the same kind as a disk, as is the case for the cup of coffee, there must necessarily be a fixed point. This fixed point is invariant under all functions which associate to each point of the original surface its position after a short time interval&nbsp;''t''. If the area is a circular band, or if it is not closed,<ref>Multiplication by {{sfrac|1|2}} on ]0,&nbsp;1[² has no fixed point.</ref> then this is not necessarily the case.

To understand differential equations better, a new branch of mathematics was born. Poincaré called it ''analysis situs''. The French [[Encyclopædia Universalis]] defines it as the branch which "treats the properties of an object that are invariant if it is deformed in any continuous way, without tearing".<ref>"concerne les propriétés invariantes d'une figure lorsqu’onlorsqu'on la déforme de manière continue quelconque, sans déchirure (par exemple, dans le cas de la déformation de la sphère, les propriétés corrélatives des objets tracés sur sa surface". From C. Houzel M. Paty ''[http://www.scientiaestudia.org.br/associac/paty/pdf/Paty,M_1997g-PoincareEU.pdf Poincaré, Henri (1854–1912)] {{webarchive|url=https://web.archive.org/web/20101008232932/http://www.scientiaestudia.org.br/associac/paty/pdf/Paty%2CM_1997g-PoincareEU.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.scientiaestudia.org.br/associac/paty/pdf/Paty%2CM_1997g-PoincareEU.pdf |archive-date=2022-10-09 |url-status=live |date=2010-10-08 }}'' Encyclopædia Universalis Albin Michel, Paris, 1999, p.&nbsp;696–706</ref> In 1886, Poincaré proved a result that is equivalent to Brouwer's fixed-point theorem,<ref>Poincaré's theorem is stated in: V. I. Istratescu ''Fixed Point Theory an Introduction'' Kluwer Academic Publishers (réédition de 2001) p 113 {{isbn|1-4020-0301-3}}</ref> although the connection with the subject of this article was not yet apparent.<ref>{{SpringerEOM|title=Brouwer theorem |first=M.I. |last=Voitsekhovskii |isbn=1-4020-0609-8}}</ref> A little later, he developed one of the fundamental tools for better understanding the analysis situs, now known as the [[fundamental group]] or sometimes the [[Poincaré group]].<ref>{{cite book |first=Jean |last=Dieudonné |author-link=Jean Dieudonné |title=A History of Algebraic and Differential Topology, 1900–1960 |___location=Boston |publisher=Birkhäuser |year=1989 |isbn=978-0-8176-3388-2 |pages=[https://archive.org/details/historyofalgebra0000dieu_g9a3/page/17 17–24] |url=https://archive.org/details/historyofalgebra0000dieu_g9a3/page/17 }}</ref> This method can be used for a very compact proof of the theorem under discussion.<!-- fr.wikipedia has it in its article on the fundamental group, we don't -->

Poincaré's method was analogous to that of [[Charles Émile Picard|Émile Picard]], a contemporary mathematician who generalized the [[Cauchy–Lipschitz theorem]].<ref>See for example: [[Charles Émile Picard|Émile Picard]] ''[http://portail.mathdoc.fr/JMPA/PDF/JMPA_1893_4_9_A4_0.pdf Sur l'application des méthodes d'approximations successives à l'étude de certaines équations différentielles ordinaires] {{Webarchive|url=https://web.archive.org/web/20110716055143/http://portail.mathdoc.fr/JMPA/PDF/JMPA_1893_4_9_A4_0.pdf# |archive-url=https://web.archive.org/web/20110716055143/http://portail.mathdoc.fr/JMPA/PDF/JMPA_1893_4_9_A4_0.pdf |archive-date=2011-07-16 |url-status=live |date=2011-07-16 }}'' Journal de Mathématiques p 217 (1893)</ref> Picard's approach is based on a result that would later be formalised by [[Banach fixed-point theorem|another fixed-point theorem]], named after [[Stefan Banach|Banach]]. Instead of the topological properties of the ___domain, this theorem uses the fact that the function in question is a [[contraction mapping|contraction]].

===First proofs===

[[Image:Hadamard2.jpg|thumb|right|[[Jacques Hadamard]] helped Brouwer to formalize his ideas.]]

At the dawn of the 20th century, the interest in analysis situs did not stay unnoticed. However, the necessity of a theorem equivalent to the one discussed in this article was not yet evident. [[Piers Bohl]], a [[Latvia]]n mathematician, applied topological methods to the study of differential equations.<ref>J. J. O'Connor E. F. Robertson ''[http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Bohl.html Piers Bohl]''</ref> In 1904 he proved the three-dimensional case of our theorem,<ref name="Bohl1904" /> but his publication was not noticed.<ref>{{cite journal |first1=A. D. |last1=Myskis |first2=I. M. |last2=Rabinovic |title=Первое доказательство теоремы о неподвижной точке при непрерывном отображении шара в себя, данное латышским математиком П.Г.Болем |trans-title=The first proof of a fixed-point theorem for a continuous mapping of a sphere into itself, given by the Latvian mathematician P. G. Bohl |language=ru |journal=Успехи математических наук |volume=10 |issue=3 |year=1955 |pages=188–192 |url=http://mi.mathnet.ru/eng/umn/v10/i3/p179 }}</ref>

Line 111 ⟶ 106:

[[Image:John f nash 20061102 2.jpg|thumb|220px|left|[[John Forbes Nash|John Nash]] used the theorem in [[game theory]] to prove the existence of an equilibrium strategy profile.]]

The theorem proved its worth in more than one way. During the 20th century numerous fixed-point theorems were developed, and even a branch of mathematics called [[fixed-point theory]].<ref>V. I. Istratescu ''Fixed Point Theory. An Introduction'' Kluwer Academic Publishers (new edition 2001) {{isbn|1-4020-0301-3}}.</ref>

Brouwer's theorem is probably the most important.<ref>"... Brouwer's fixed point theorem, perhaps the most important fixed point theorem." p xiii V. I. Istratescu ''Fixed Point Theory an Introduction'' Kluwer Academic Publishers (new edition 2001) {{isbn|1-4020-0301-3}}.</ref> It is also among the foundational theorems on the topology of [[topological manifold]]s and is often used to prove other important results such as the [[Jordan curve theorem]].<ref>E.g.: S. Greenwood J. Cao'' [http://www.math.auckland.ac.nz/class750/section5.pdf Brouwer’sBrouwer's Fixed Point Theorem and the Jordan Curve Theorem]'' University of Auckland, New Zealand.</ref>

Besides the fixed-point theorems for more or less [[contraction mapping|contracting]] functions, there are many that have emerged directly or indirectly from the result under discussion. A continuous map from a closed ball of Euclidean space to its boundary cannot be the identity on the boundary. Similarly, the [[Borsuk–Ulam theorem]] says that a continuous map from the ''n''-dimensional sphere to '''R'''ⁿ has a pair of antipodal points that are mapped to the same point. In the finite-dimensional case, the [[Lefschetz fixed-point theorem]] provided from 1926 a method for counting fixed points. In 1930, Brouwer's fixed-point theorem was generalized to [[Banach space]]s.<ref>{{cite journal |first=J. |last=Schauder |title=Der Fixpunktsatz in Funktionsräumen |journal=[[Studia Mathematica]] |volume=2 |year=1930 |pages=171–180 |doi= 10.4064/sm-2-1-171-180|doi-access=free }}</ref> This generalization is known as [[Fixed-point theorems in infinite-dimensional spaces|Schauder's fixed-point theorem]], a result generalized further by S. Kakutani to [[multivaluedSet-valued function|set-valued functions]]s.<ref>{{cite journal |first=S. |last=Kakutani |title=A generalization of Brouwer's Fixed Point Theorem |journal= Duke Mathematical Journal|volume=8 |year=1941 |issue=3 |pages=457–459 |doi=10.1215/S0012-7094-41-00838-4 }}</ref> One also meets the theorem and its variants outside topology. It can be used to prove the [[Hartman-Grobman theorem]], which describes the qualitative behaviour of certain differential equations near certain equilibria. Similarly, Brouwer's theorem is used for the proof of the [[Central Limit Theorem]]. The theorem can also be found in existence proofs for the solutions of certain [[partial differential equation]]s.<ref>These examples are taken from: F. Boyer ''[http://www.cmi.univ-mrs.fr/~fboyer/ter_fboyer2.pdf Théorèmes de point fixe et applications]'' CMI Université Paul Cézanne (2008–2009) [https://www.webcitation.org/5refXIDvI?url=http://www.cmi.univ-mrs.fr/%7Efboyer/ter_fboyer2.pdf Archived copy] at [[WebCite]] (August 1, 2010).</ref>

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. The first algorithm to approximate a fixed point was proposed by [[Herbert Scarf]].<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}}.

==Proof outlines==

===A proof using degree===

Brouwer's original 1911 proof relied on the notion of the [[degree of a continuous mapping]], stemming from ideas in [[differential topology]]. Several modern accounts of the proof can be found in the literature, notably {{harvtxt|Milnor|1965}}.<ref name="Milnor">{{harvnb|Milnor|1965|pages=1–19}}</ref><ref>{{cite book | last = Teschl| first = Gerald| author-link = Gerald Teschl| title = Topics in Linear and Nonlinear Functional Analysis|url=https://www.mat.univie.ac.at/~gerald/ftp/book-fa/fa.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.mat.univie.ac.at/~gerald/ftp/book-fa/fa.pdf |archive-date=2022-10-09 |url-status=live|chapter=10. The Brouwer mapping degree|access-date=1 February 2022|year=2019|publisher=[[American Mathematical Society]]|series=Graduate Studies in Mathematics}}</ref>

Let <math>K=\overline{B(0)}</math> denote the closed unit ball in <math>\mathbb R^n</math> centered at the origin. Suppose for simplicity that <math>f:K\to K</math> is continuously differentiable. A [[regular value]] of <math>f</math> is a point <math>p\in B(0)</math> such that the [[Jacobian matrix and determinant|Jacobian]] of <math>f</math> is non-singular at every point of the preimage of <math>p</math>. In particular, by the [[inverse function theorem]], every point of the preimage of <math>f</math> lies in <math>B(0)</math> (the interior of <math>K</math>). The degree of <math>f</math> at a regular value <math>p\in B(0)</math> is defined as the sum of the signs of the [[Jacobian determinant]] of <math>f</math> over the preimages of <math>p</math> under <math>f</math>:

Line 128 ⟶ 123:

:<math>\operatorname{deg}_p(f) = \sum_{x\in f^{-1}(p)} \operatorname{sign}\,\det (df_x).</math>

The degree is, roughly speaking, the number of "sheets" of the preimage ''f'' lying over a small [[open set]] around ''p'', with sheets counted oppositely if they are oppositely oriented. This is thus a generalization of [[winding number]] to higher dimensions.

The degree satisfies the property of ''homotopy invariance'': let <math>f</math> and <math>g</math> be two continuously differentiable functions, and <math>H_t(x)=tf+(1-t)g</math> for <math>0\le t\le 1</math>. Suppose that the point <math>p</math> is a regular value of <math>H_t</math> for all ''t''. Then <math>\deg_p f = \deg_p g</math>.

If there is no fixed point of the boundary of <math>K</math>, then the function

:<math>g(x)=\frac{x-f(x)}{\sup_{xy\in K}\left|xy-f(xy)\right|}</math>

is well-defined, and

<math>H(t,x) = \frac{x-tf(x)}{\sup_{xy\in K}\left|xy-tf(xy)\right|}</math>

defines a homotopy from the [[identity function]] to it. The identity function has degree one at every point. In particular, the identity function has degree one at the origin, so <math>g</math> also has degree one at the origin. As a consequence, the preimage <math>g^{-1}(0)</math> is not empty. The elements of <math>g^{-1}(0)</math> are precisely the fixed points of the original function ''f''.

This requires some work to make fully general. The definition of degree must be extended to singular values of ''f'', and then to continuous functions. The more modern advent of [[homology theory]] simplifies the construction of the degree, and so has become a standard proof in the literature.

Line 145 ⟶ 140:

The [[hairy ball theorem]] states that on the unit sphere {{mvar|''S''}} in an odd-dimensional Euclidean space, there is no nowhere-vanishing continuous tangent vector field {{mvar|'''w'''}} on {{mvar|''S''}}. (The tangency condition means that {{mvar|'''w'''('''x''') ⋅ '''x'''}} = 0 for every unit vector {{mvar|'''x'''}}.) Sometimes the theorem is expressed by the statement that "there is always a place on the globe with no wind". An elementary proof of the hairy ball theorem can be found in {{harvtxt|Milnor|1978}}.

In fact, suppose first that {{mvar|'''w'''}} is '''''continuously differentiable'''''. By scaling, it can be assumed that {{mvar|'''w'''}} is a continuously differentiable unit tangent vector on {{mvar|'''S'''}}. It can be extended radially to a small spherical shell {{mvar|''A''}} of {{mvar|''S''}}. For {{mvar|''t''}} sufficiently small, a routine computation shows that the mapping {{mvar|'''f'''_''t''}}({{mvar|'''x'''}}) = {{mvar|''t'' '''x'''}} + {{mvar|''t'' '''w'''('''x''')}} is a [[contraction mapping]] on {{mvar|''A''}} and that the volume of its image is a polynomial in {{mvar|''t''}}. On the other hand, as a contraction mapping, {{mvar|'''f'''_''t''}} must restrict to a homeomorphism of {{mvar|''S''}} onto (1 + {{mvar|''t''²}})^{½{{sfrac|1|2}}} {{mvar|''S''}} and {{mvar|''A''}} onto (1 + {{mvar|''t''²}})^{½{{sfrac|1|2}}} {{mvar|''A''}}. This gives a contradiction, because, if the dimension {{mvar|''n''}} of the Euclidean space is odd, (1 + {{mvar|''t''²}})^{{{mvar|''n''}}/2} is not a polynomial.

If {{mvar|'''w'''}} is only a '''''continuous''''' unit tangent vector on {{mvar|''S''}}, by the [[Weierstrass approximation theorem]], it can be uniformly approximated by a polynomial map {{mvar|'''u'''}} of {{mvar|''A''}} into Euclidean space. The orthogonal projection on to the tangent space is given by {{mvar|'''v'''}}({{mvar|'''x'''}}) = {{mvar|'''u'''}}({{mvar|'''x'''}}) - {{mvar|'''u'''}}({{mvar|'''x'''}}) ⋅ {{mvar|'''x'''}}. Thus {{mvar|'''v'''}} is polynomial and nowhere vanishing on {{mvar|''A''}}; by construction {{mvar|'''v'''}}/||{{mvar|'''v'''}}|| is a smooth unit tangent vector field on {{mvar|''S''}}, a contradiction.

The continuous version of the hairy ball theorem can now be used to prove the Brouwer fixed point theorem. First suppose that {{mvar|''n''}} is oddeven. If there were a fixed-point-free continuous self-mapping {{mvar|'''f'''}} of the closed unit ball {{mvar|''B''}} of the {{mvar|''n''}}-dimensional Euclidean space {{mvar|''V''}}, set

:<math>{\mathbf w}({\mathbf x}) = (1 - {\mathbf x}\cdot {\mathbf f}({\mathbf x}))\, {\mathbf x} - (1 - {\mathbf x}\cdot {\mathbf x})\, {\mathbf f}({\mathbf x}).</math>

Line 157 ⟶ 152:

:<math>{\mathbf X}({\mathbf x},t)=(-t\,{\mathbf w}({\mathbf x}), {\mathbf x}\cdot {\mathbf w}({\mathbf x})).</math>

By construction {{mvar|'''X'''}} is a continuous vector field on the unit sphere of {{mvar|''W''}}, satisfying the tangency condition {{mvar|'''y'''}} ⋅ {{mvar|'''X'''}}({{mvar|'''y'''}})&nbsp;=&nbsp;0. Moreover, {{mvar|'''X'''}}({{mvar|'''y'''}}) is nowhere vanishing (because, if {{var|'''x'''}} has norm 1, then {{mvar|'''x'''}} ⋅ {{mvar|'''w'''}}({{mvar|''x''}}) is non-zero; while if {{mvar|'''x'''}} has norm strictly less than 1, then {{mvar|''t''}} and {{mvar|'''w'''}}({{mvar|'''x'''}}) are both non-zero). This contradiction proves the fixed point theorem when {{mvar|''n''}} is oddeven. For {{mvar|''n''}} evenodd, one can apply the fixed point theorem to the closed unit ball {{mvar|''B''}} in {{mvar|''n''}} + 1}} dimensions and the mapping {{mvar|'''F'''}}({{mvar|'''x'''}},{{mvar|''y''}}) = ({{mvar|'''f'''}}({{mvar|'''x'''}}),0).

The advantage of this proof is that it uses only elementary techniques; more general results like the [[Borsuk-Ulam theorem]] require tools from [[algebraic topology]].<ref name="Milnor78">{{harvnb|Milnor|1978}}</ref>

Line 164 ⟶ 159:

[[Image:Brouwer fixed point theorem retraction.svg|thumb|right|Illustration of the retraction ''F'']]

Suppose, for contradiction, that a continuous function {{nowrap|''f'' : ''D''^''n'' → ''D''^''n''}} has ''no'' fixed point. This means that, for every point x in ''D''^''n'', the points ''x'' and ''f''(''x'') are distinct. Because they are distinct, for every point x in ''D''^''n'', we can construct a unique ray from ''f''(''x'') to ''x'' and follow the ray until it intersects the boundary ''S''^''n''−1 (see illustration). By calling this intersection point ''F''(''x''), we define a function ''F''&nbsp;:&nbsp;''D''^''n''&nbsp;→&nbsp;''S''^''n''−1 sending each point in the disk to its corresponding intersection point on the boundary. As a special case, whenever ''x'' itself is on the boundary, then the intersection point ''F''(''x'') must be ''x''.

Consequently, ''F'' is a special type of continuous function known as a [[retraction (topology)|retraction]]: every point of the [[codomain]] (in this case ''S''^''n''−1) is a fixed point of ''F''.

Intuitively it seems unlikely that there could be a retraction of ''D''^''n'' onto ''S''^''n''−1, and in the case ''n'' = 1, the impossibility is more basic, because ''S''⁰ (i.e., the endpoints of the closed interval ''D''¹) is not even connected. The case ''n'' = 2 is less obvious, but can be proven by using basic arguments involving the [[fundamental group]]s of the respective spaces: the retraction would induce a surjective [[group homomorphism]] from the fundamental group of ''D''² to that of ''S''¹, but the latter group is isomorphic to '''Z''' while the first group is trivial, so this is impossible. The case ''n'' = 2 can also be proven by contradiction based on a theorem about non-vanishing [[vector field]]s.

Line 172 ⟶ 167:

For ''n'' > 2, however, proving the impossibility of the retraction is more difficult. One way is to make use of [[Homology (mathematics)|homology groups]]: the homology ''H''_''n''−1(''D''^''n'') is trivial, while ''H''_''n''−1(''S''^''n''−1) is infinite [[cyclic group|cyclic]]. This shows that the retraction is impossible, because again the retraction would induce an injective group homomorphism from the latter to the former group.

The impossibility of a retraction can also be shown using the [[de Rham cohomology]] of open subsets of Euclidean space ''E''^''n''. For ''n'' ≥ 2, the de Rham cohomology of ''U'' = ''E''^''n'' – (0) is one-dimensional in degree 0 and ''n'' -– 1, and vanishes otherwise. If a retraction existed, then ''U'' would have to be contractible and its de Rham cohomology in degree ''n'' -– 1 would have to vanish, a contradiction.<ref>{{harvnb|Madsen|Tornehave |1997|pages=39–48}}</ref>

===A proof using Stokes' theorem===

Line 209 ⟶ 204:

===A proof by Hirsch===

There is also a quick proof, by [[Morris Hirsch]], based on the impossibility of a differentiable retraction. TheLet [[indirect''f'' proof]]denote startsa bycontinuous notingmap from the unit ball Dⁿ in n-dimensional Euclidean space to itself and assume that ''f'' fixes no point. By continuity and the fact that Dⁿ is compact, it follows that for some ε > 0, ∥x - ''f''(x)∥ > ε for all x in Dⁿ. Then the map ''f'' can be approximated by a smooth map retaining the property of not fixing a point; this can be done by using the [[Weierstrass approximation theorem]] or by [[convolution|convolving]] with smooth [[bump function]]s. One then defines a retraction as above whichby sending each x to the point of ∂Dⁿ where the unique ray from x through ''f''(x) intersects ∂Dⁿ, and this must now be a differentiable mapping. Such a retraction must have a non-singular value p ∈ ∂Dⁿ, by [[Sard's theorem]], which is also non-singular for the restriction to the boundary (which is just the identity). Thus the inverse image ''f''^-1(p) would be a compact 1-manifold with boundary. TheSuch a boundary would have to contain at least two end pointsendpoints, bothand of whichthese would have to lie on the boundary of the original ball—whichball. isThis impossiblewould inmean that the inverse image of one point on ∂Dⁿ contains a different point on ∂Dⁿ, contradicting the definition of a retraction Dⁿ → ∂Dⁿ.<ref>{{harvnb|Hirsch|1988}}</ref>

R. Bruce Kellogg, Tien-Yien Li, and [[James A. Yorke]] turned Hirsch's proof into a [[Computability|computable]] proof by observing that the retract is in fact defined everywhere except at the fixed points.{{sfn|Kellogg|Li|Yorke|1976}} For almost any point, ''q'', on the boundary, (— assuming it is not a fixed point) the— onethe 1-manifold with boundary mentioned above does exist and the only possibility is that it leads from ''q'' to a fixed point. It is an easy numerical task to follow such a path from ''q'' to the fixed point so the method is essentially computable.{{sfn|Chow|Mallet-Paret|Yorke|1978}} gave a conceptually similar path-following version of the homotopy proof which extends to a wide variety of related problems.

===A proof using oriented area===

A variation of the preceding proof does not employ the Sard's theorem, and goes as follows. If <math>r\colon B\to \partial B</math> is a smooth retraction, one considers the smooth deformation <math>g^t(x):=t r(x)+(1-t)x,</math> and the smooth function

:<math>\varphi(t):=\int_B \det D g^t(x) \, dx.</math>

Differentiating under the sign of integral it is not difficult to check that ''{{prime|φ}}''(''t'') = 0 for all ''t'', so ''φ'' is a constant function, which is a contradiction because ''φ''(0) is the ''n''-dimensional volume of the ball, while ''φ''(1) is zero. The geometric idea is that ''φ''(''t'') is the oriented area of ''g''^''t''(''B'') (that is, the Lebesgue measure of the image of the ball via ''g''^''t'', taking into account multiplicity and orientation), and should remain constant (as it is very clear in the one-dimensional case). On the other hand, as the parameter ''t'' passes formfrom 0 to 1 the map ''g''^''t'' transforms continuously from the identity map of the ball, to the retraction ''r'', which is a contradiction since the oriented area of the identity coincides with the volume of the ball, while the oriented area of ''r'' is necessarily 0, as its image is the boundary of the ball, a set of null measure.<ref>{{harvnb|Kulpa|1989}}</ref>

===A proof using the game hexHex===

A quite different proof given by [[David Gale]] is based on the game of [[Hex (board game)|Hex]]. The basic theorem aboutregarding Hex, first proven by John Nash, is that no game of Hex can end in a draw.; the Thisfirst player always has a winning strategy (although this theorem is nonconstructive, and explicit strategies have not been fully developed for board sizes of dimensions 10 x 10 or greater). This turns out to be equivalent to the Brouwer fixed-point theorem for dimension 2. By considering ''n''-dimensional versions of Hex, one can prove in general that Brouwer's theorem is equivalent to the [[determinacy]] theorem for Hex.<ref>{{cite journal|author=David Gale |year=1979|title=The Game of Hex and Brouwer Fixed-Point Theorem | journal=The American Mathematical Monthly | volume=86 | pages=818–827|doi=10.2307/2320146|jstor=2320146|issue=10}}</ref>

===A proof using the Lefschetz fixed-point theorem===

Line 227 ⟶ 222:

===A proof in a weak logical system===

In [[reverse mathematics]], Brouwer's theorem can be proved in the system [[Weak KönigKőnig's lemma|WKL₀]], and conversely over the base system [[reverse mathematics|RCA₀]] Brouwer's theorem for a square implies the [[weak KönigKőnig's lemma]], so this gives a precise description of the strength of Brouwer's theorem.

==Generalizations==

Line 250 ⟶ 245:

==See also==

* [[Banach fixed-point theorem]]

* [[Fixed-point computation]]

* [[Infinite compositions of analytic functions]]

* [[Nash equilibrium#Alternate proof using the Brouwer fixed-point theorem|Nash equilibrium]]

Line 259 ⟶ 255:

==References==

*{{cite journal|mr=0283792|last=Boothby| first=William M.|title=On two classical theorems of algebraic topology|journal=[[Amer. Math. Monthly]]|volume= 78|year=1971|issue=3 |pages=237–249|doi=10.2307/2317520 |jstor=2317520}}

*{{cite book|mr=0861409|last=Boothby|first= William M. |title=

An introduction to differentiable manifolds and Riemannian geometry|edition=Second|series= Pure and Applied Mathematics|volume= 120|publisher= Academic Press|year= 1986|isbn= 0-12-116052-1}}

Line 281 ⟶ 277:

*{{cite book|mr=0226651|last=Milnor|first= John W.|author-link=John Milnor|title=Topology from the differentiable viewpoint|publisher=[[University Press of Virginia]]|___location= Charlottesville|year= 1965

|url=https://archive.org/details/topologyfromdiff0000miln}}

*{{cite journal|mr=0505523|last=Milnor|first= John W.|title=Analytic proofs of the "'hairy ball theorem'' and the Brouwer fixed-point theorem|journal=[[Amer. Math. Monthly]]|volume=85 |year=1978|issue= 7|pages=521–524

|url=https://people.ucsc.edu/~lewis/Math208/hairyball.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://people.ucsc.edu/~lewis/Math208/hairyball.pdf |archive-date=2022-10-09 |url-status=live|jstor=2320860}}

*{{springer | title=Brouwer theorem | id=B/b017670 | last=Sobolev | first=Vladimir I. | author-link=<!--Vladimir Ivanovich Sobolev-->}}

*{{cite book|last=Spanier|first= Edwin H.|title=Algebraic topology|publisher= McGraw-Hill |___location= New York-Toronto-London|year= 1966}}

Line 288 ⟶ 284:

==External links==

* [http://www.cut-the-knot.org/do_you_know/poincare.shtml#brouwertheorem Brouwer's Fixed Point Theorem for Triangles] at [[cut-the-knot]]

* {{PlanetMath|BrouwerFixedPointTheorem}}

* [http://planetmath.org/encyclopedia/BrouwerFixedPointTheorem.html Brouwer theorem], from [[PlanetMath]] with attached proof.

* [http://www.mathpages.com/home/kmath262/kmath262.htm Reconstructing Brouwer] at MathPages

* [https://web.archive.org/web/20110314100800/http://mathforum.org/mathimages/index.php/Brouwer_Fixed_Point_Theorem Brouwer Fixed Point Theorem] at Math Images.

{{Authority control}}

Line 296 ⟶ 292:

{{DEFAULTSORT:Brouwer Fixed Point Theorem}}

[[Category:Fixed-point theorems]]

[[Category:ContinuousTheory mappingsof continuous functions]]

[[Category:Theorems in topology]]

[[Category:Theorems in convex geometry]]