Editing Brouwer fixed-point theorem (section)

==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>:

:<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_{y\in K}\left|y-f(y)\right|}</math>

is well-defined, and

<math>H(t,x) = \frac{x-tf(x)}{\sup_{y\in K}\left|y-tf(y)\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.
=== A proof using the hairy ball theorem ===
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'''<sub>''t''</sub>}}({{mvar|'''x'''}}) = {{mvar|'''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'''<sub>''t''</sub>}} must restrict to a homeomorphism of {{mvar|''S''}} onto (1 + {{mvar|''t''<sup>2</sup>}})<sup>{{sfrac|1|2}}</sup> {{mvar|''S''}} and  {{mvar|''A''}} onto (1 + {{mvar|''t''<sup>2</sup>}})<sup>{{sfrac|1|2}}</sup> {{mvar|''A''}}. This gives a contradiction, because, if the dimension {{mvar|''n''}} of the Euclidean space is odd, (1 + {{mvar|''t''<sup>2</sup>}})<sup>{{mvar|''n''}}/2</sup> 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 even. 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>

Since {{mvar|'''f'''}} has no fixed points, it follows that, for {{mvar|'''x'''}} in the [[interior (topology)|interior]] of {{mvar|''B''}}, the vector {{mvar|'''w'''}}({{mvar|'''x'''}}) is non-zero; and for {{mvar|'''x'''}} in {{mvar|''S''}},  the scalar  product <br/> {{mvar|'''x'''}} ⋅ {{mvar|'''w'''}}({{mvar|'''x'''}}) = 1 – {{mvar|'''x'''}} ⋅ {{mvar|'''f'''}}({{mvar|'''x'''}}) is strictly positive. From the original {{mvar|''n''}}-dimensional space Euclidean space {{mvar|''V''}}, construct a new auxiliary <br/>({{mvar|''n'' + 1}})-dimensional space {{mvar|''W''}} =  {{mvar|''V''}} x '''R''', with coordinates {{mvar|''y''}} = ({{mvar|'''x'''}}, {{mvar|''t''}}). Set

:<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 even. For {{mvar|''n''}} odd, 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>

===A proof using homology or cohomology===
The proof uses the observation that the [[boundary (topology)|boundary]] of the ''n''-disk ''D''<sup>''n''</sup> is ''S''<sup>''n''−1</sup>, the (''n'' − 1)-[[sphere]].

[[Image:Brouwer fixed point theorem retraction.svg|thumb|right|Illustration of the retraction ''F'']]
Suppose, for contradiction, that a continuous function {{nowrap|''f'' : ''D''<sup>''n''</sup> → ''D''<sup>''n''</sup>}} has ''no'' fixed point. This means that, for every point x in ''D''<sup>''n''</sup>, the points ''x'' and ''f''(''x'') are distinct. Because they are distinct, for every point x in ''D''<sup>''n''</sup>, we can construct a unique ray from ''f''(''x'') to ''x'' and follow the ray until it intersects the boundary ''S''<sup>''n''−1</sup> (see illustration). By calling this intersection point ''F''(''x''), we define a function ''F''&nbsp;:&nbsp;''D''<sup>''n''</sup>&nbsp;→&nbsp;''S''<sup>''n''−1</sup> 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''<sup>''n''−1</sup>) is a fixed point of ''F''.

Intuitively it seems unlikely that there could be a retraction of ''D''<sup>''n''</sup> onto ''S''<sup>''n''−1</sup>, and in the case ''n'' = 1, the impossibility is more basic, because ''S''<sup>0</sup> (i.e., the endpoints of the closed interval ''D''<sup>1</sup>) 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''<sup>2</sup> to that of ''S''<sup>1</sup>, 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.

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''<sub>''n''−1</sub>(''D''<sup>''n''</sup>) is trivial, while ''H''<sub>''n''−1</sub>(''S''<sup>''n''−1</sup>) 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''<sup>''n''</sup>. For ''n'' ≥ 2, the de Rham cohomology of ''U'' = ''E''<sup>''n''</sup> – (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===
As in the proof of Brouwer's fixed-point theorem for continuous maps using homology, it is reduced to proving that there is no continuous retraction {{mvar|''F''}} from the ball {{mvar|''B''}} onto its boundary ∂{{mvar|''B''}}. In that case it can be assumed that {{mvar|''F''}} is smooth, since it can be approximated using the [[Weierstrass approximation theorem]] or by [[convolution|convolving]] with non-negative smooth [[bump function]]s of sufficiently small support and integral one (i.e. [[mollifier|mollifying]]). If {{mvar|ω}} is a [[volume form]] on the boundary then by [[Stokes' theorem]],
:<math>0<\int_{\partial B}\omega = \int_{\partial B}F^*(\omega) = \int_BdF^*(\omega)= \int_BF^*(d\omega)=\int_BF^*(0) = 0,</math>
giving a contradiction.<ref>{{harvnb|Boothby|1971}}</ref><ref>{{harvnb|Boothby|1986}}</ref>

More generally, this shows that there is no smooth retraction from any non-empty smooth oriented compact manifold {{mvar|''M''}} onto its boundary. The proof using Stokes' theorem is closely related to the proof using homology, because the form {{mvar|ω}} generates the [[De Rham cohomology|de Rham cohomology group]] {{mvar|''H''<sup>''n''-1</sup>}}(∂{{mvar|''M''}}) which is isomorphic to the homology group {{mvar|''H''<sub>''n''-1</sub>}}(∂{{mvar|''M''}}) by [[De Rham cohomology#De Rham's theorem|de Rham's theorem]].<ref>{{harvnb|Dieudonné|1982}}</ref>

===A combinatorial proof===
The BFPT can be proved using [[Sperner's lemma]]. We now give an outline of the proof for the special case in which ''f'' is a function from the standard ''n''-[[simplex]], <math>\Delta^n,</math> to itself, where

:<math>\Delta^n = \left\{P\in\mathbb{R}^{n+1}\mid\sum_{i = 0}^{n}{P_i} = 1 \text{ and } P_i \ge 0 \text{ for all } i\right\}.</math>

For every point <math>P\in \Delta^n,</math> also <math>f(P)\in \Delta^n.</math> Hence the sum of their coordinates is equal:

:<math>\sum_{i = 0}^{n}{P_i} = 1 = \sum_{i = 0}^{n}{f(P)_i}</math>

Hence, by the pigeonhole principle, for every <math>P\in \Delta^n,</math> there must be an index <math>j \in \{0, \ldots, n\}</math> such that the <math>j</math>th coordinate of <math>P</math> is greater than or equal to the <math>j</math>th coordinate of its image under ''f'':

:<math>P_j \geq f(P)_j.</math>

Moreover, if <math>P</math> lies on a ''k''-dimensional sub-face of <math>\Delta^n,</math> then by the same argument, the index <math>j</math> can be selected from among the {{nowrap|''k'' + 1}} coordinates which are not zero on this sub-face.

We now use this fact to construct a Sperner coloring.  For every triangulation of <math>\Delta^n,</math> the color of every vertex <math>P</math> is an index <math>j</math> such that <math>f(P)_j \leq P_j.</math>

By construction, this is a Sperner coloring. Hence, by Sperner's lemma, there is an ''n''-dimensional simplex whose vertices are colored with the entire set of {{nowrap|''n'' + 1}} available colors.

Because ''f'' is continuous, this simplex can be made arbitrarily small by choosing an arbitrarily fine triangulation. Hence, there must be a point <math>P</math> which satisfies the labeling condition in all coordinates: <math>f(P)_j \leq P_j</math> for all <math>j.</math>

Because the sum of the coordinates of <math>P</math> and <math>f(P)</math> must be equal, all these inequalities must actually be equalities. But this means that:

:<math>f(P) = P.</math>

That is, <math>P</math> is a fixed point of <math>f.</math>

===A proof by Hirsch===
There is also a quick proof, by [[Morris Hirsch]], based on the impossibility of a differentiable retraction.  Let ''f'' denote a continuous map from the unit ball D<sup>n</sup> in n-dimensional Euclidean space to itself and assume that ''f'' fixes no point. By continuity and the fact that D<sup>n</sup> is compact, it follows that for some ε > 0, ∥x - ''f''(x)∥ > ε for all x in D<sup>n</sup>. 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 by sending each x to the point of ∂D<sup>n</sup> where the unique ray from x through ''f''(x) intersects ∂D<sup>n</sup>, and this must now be a differentiable mapping.  Such a retraction must have a non-singular value p ∈ ∂D<sup>n</sup>, 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''<sup> -1</sup>(p) would be a compact 1-manifold with boundary. Such a boundary would have to contain at least two endpoints, and these would have to lie on the boundary of the original ball. This would mean that the inverse image of one point on ∂D<sup>n</sup> contains a different point on ∂D<sup>n</sup>, contradicting the definition of a retraction D<sup>n</sup> → ∂D<sup>n</sup>.<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 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''<sup>''t''</sup>(''B'') (that is, the Lebesgue measure of the image of the ball via ''g''<sup>''t''</sup>, 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 from 0 to 1 the map ''g''<sup>''t''</sup> 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 Hex===
A quite different proof given by [[David Gale]] is based on the game of [[Hex (board game)|Hex]].  The basic theorem regarding Hex, first proven by John Nash, is that no game of Hex can end in a draw; the first 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===
The Lefschetz fixed-point theorem says that if a continuous map ''f'' from a finite simplicial complex ''B'' to itself has only isolated fixed points, then the number of fixed points counted with multiplicities (which may be negative) is equal to the Lefschetz number
:<math>\displaystyle \sum_n(-1)^n\operatorname{Tr}(f|H_n(B))</math>
and in particular if the Lefschetz number is nonzero then ''f'' must have a fixed point. If ''B'' is a ball (or more generally is contractible) then the Lefschetz number is one because the only non-zero [[simplicial homology]] group is: <math>H_0(B)</math> and ''f'' acts as the identity on this group, so ''f'' has a fixed point.<ref>{{harvnb|Hilton|Wylie|1960}}</ref><ref>{{harvnb|Spanier|1966}}</ref>

===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.