As promised, I will attempt to finish up the rest of the proof for Nash’s Theorem tonight (albeit a few weeks late). Let’s start again with a few definitions from where we left off.

- A subset of is
**compact**if the set is closed and bounded. Every sequence in a compact set has a convergent subsequence. - The
**centroid**of a simplex is the average of the its vertices or, in mathematical terms, the centroid is . - Now we are set to prove
**Brouwer’s Fixed Point Theorem**which states that a continuous function mapping a transformation of a simplex contains a fixed point for such that . There are various different proofs of this theorem spread out through mathematical literature (for examples, see here, here, and here). However, I will be following the proof explained by Shosham and Leyton-Brown since the proof uses Sperner’s lemma (and is one of the easier proofs to understand).- To begin, let . We then simplicially subdivide such that the Euclidean distance between any two vertices in a subsimplex is at most . We label the vertices in the subsimplex with a labeling function where (1). For each vertex in the division, , is the th component of the vertex and is the th component of . To ensure that is well defined, we must show that weakly decreases for all possible . We show this by assuming first the opposite that for all . Given the definition of a standard simplex (all vertices within the simplex is some combination of the components), we know that . By the definition of , a component is greater than zero, , if and only if . Thus, we can deduce the following rule:
(2)

By our assumption, for all so we conclude that:

(3)

Given that is on the standard simplex, we know that

(4)

We have reached a contradiction by Eqs. 3 and 4. Therefore, is well defined and satisfies Eq. 1 with a non-empty set on the right for every .

- Since we have shown that is a proper labeling, we know by Sperner’s lemma that a complete labeling exists in the subsimplexes. As we let approach zero, we see a convergent sequence composed of the centroids of the completely labeled subsimplexes. We can call the point that the sequence of centroids converges to . As , every point of the completely labeled subsimplex, , will converge to , where . Thus, we have since for all . This is because we have shown that . Since all points of the completely labeled subsimplex converges to , . If , then
(5)

But we know by definition that

(6)

and

(7)

so Eqs. 5, 6 and 7 reach a contradiction and for all and . QED

It appears that it has taken longer to write the proof for Brouwer’s theorem than expected. I will finish up the last and final part (where I actually prove Nash’s theorem–hard to believe) in my final blog post for Proving Nash’s Theorem.

Advertisements

- To begin, let . We then simplicially subdivide such that the Euclidean distance between any two vertices in a subsimplex is at most . We label the vertices in the subsimplex with a labeling function where (1). For each vertex in the division, , is the th component of the vertex and is the th component of . To ensure that is well defined, we must show that weakly decreases for all possible . We show this by assuming first the opposite that for all . Given the definition of a standard simplex (all vertices within the simplex is some combination of the components), we know that . By the definition of , a component is greater than zero, , if and only if . Thus, we can deduce the following rule: