# Constructive versions of KKM lemma and Brouwer's fixed point theorem.

1. IntroductionIt is often said that Brouwer's fixed point theorem cannot be constructively proved. On the other hand, however, Sperner's lemma which is used to prove Brouwer's theorem can be constructively proved. Some authors have presented a constructive (or an approximate) version of Brouwer's fixed point theorem using Sperner's lemma. See [2] and [6]. We present an alternative proof of this theorem using a constructive version of KKM (Knaster, Kuratowski and Mazurkiewicz) lemma which is proved by Sperner's lemma (2).

2. Sperner's lemma

Let [DELTA] denote an n-dimensional simplex. For example, a 2-dimensional simplex is a triangle. Let partition the simplex. Figure 1 is an example of partition of a 2- dimensional simplex. In a 2-dimensional case we divide each side of [DELTA] in m equal segments, and draw the lines parallel to the sides of [DELTA]. Then, the 2-dimensional simplex is partitioned into [m.sup.2] triangles. We consider partition of [DELTA] inductively for cases of higher dimension. In a 3 dimensional case each face of [DELTA] is a 2-dimensional simplex, and so it is partitioned into [m.sup.2] triangles in the way above mentioned, and draw the planes parallel to the faces of [DELTA]. Then, the 3-dimensional simplex is partitioned into [m.sup.3] trigonal pyramids. And similarly for cases of higher dimension.

Let K denote the set of small n-dimensional simplices of [DELTA] constructed by partition. Vertices of these small simplices of K are labeled with the numbers 0,1, 2, ..., n subject to the following rules.

1. The vertices of A are respectively labeled with 0 to n. We label a point (1, 0, ...,0) with 0, a point (0, 1, 0, ...,0) with 1, a point (0, 0, 1 ...,0) with 2, ..., a point (0, ..., 0, 1) with n. That is, a vertex whose k-th coordinate (k = 0, 1, ...,n) is 1 and all other coordinates are 0 is labeled with k.

2. If a vertex of K is contained in an n--1-dimensional face of [DELTA], then this vertex is labeled with some number which is the same as the number of one of the vertices of that face.

3. If a vertex of K is contained in an n--2-dimensional face of [DELTA], then this vertex is labeled with some number which is the same as the number of one of the vertices of that face. And similarly for cases of lower dimension.

4. A vertex contained inside of A is labeled with an arbitrary number among 0, 1, ..., n.

A small simplex of K which is labeled with the numbers 0, 1, ... , n is called a fully labeled simplex. Sperner's lemma is stated as follows.

Lemma 2.1. [Sperner's lemma] If we label the vertices of K following the rules (1) ~ (4), then there are an odd number of fully labeled simplices, and so there exists at least one fully labeled simplex.

Proof. About constructive proofs of Sperner's lemma see [3] or [5].

3. Constructive version of KKM lemma

In this section we present a constructive version of KKM(Knaster, Kuratowski and Mazurkiewicz) lemma using Sperner's lemma.

[FIGURE 1 OMITTED]

Lemma 3.1. [constructive version of KKM Lemma] Let [DELTA] be an n-dimensional simplex, and [p.sub.0], [p.sub.1], ...,[p.sub.n] be vertices of [DELTA]. Let [[DELTA].sup.k.sub.i], k = 0, 1, ...,n be a k- dimensional face of [DELTA], [p.sub.i0], [p.sub.i1], ...,[p.sub.ik] be its vertices. {[p.sub.i0], [p.sub.i1], ...,[p.sub.ik]} is a subset of {[p.sub.0], [p.sub.1], ...,[p.sub.n]}. Let [A.sub.0], [A.sub.1], ...,[A.sub.n] be non-empty subsets of [DELTA] which satisfy the following condition (3).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then, for each [epsilon] > 0 we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and we can constructively find a point p such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where V([A.sub.i], [epsilon]) is an [epsilon]-neighborhood of [A.sub.i].

Proof. Let K be the set of small n-dimensional simplices constructed by partition of an n-dimensional simplex [DELTA]. The vertices [p.sub.0], [p.sub.1], ...,[p.sub.n] of A are labeled with, respectively, 0, 1, ... and n. Each vertex of all simplices of K is contained in some face of [DELTA]. If a vertex p is contained in more than one faces of [DELTA], we select a face of the least dimension. Let k be its dimension and denote it by [[DELTA].sup.k.sub.i]. By the assumption p is contained in at least one of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII, ... and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Denote it by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and label p with [i.sub.j]. By the condition of this lemma [i.sub.j] is the number (label) of a vertex of [[DELTA].sup.k.sub.i]. This labeling satisfies the condition for Sperner's lemma. Thus, there exists a fully labeled n-dimensional simplex of K. Denote the vertices of this simplex by [q.sub.0], [q.sub.1], ... and [q.sub.n]. We can name them such that [q.sub.i] is labeled with i. Then, each [q.sub.i] is contained in [A.sub.i]. If partition of A is sufficiently fine, the size of this fully labeled n-dimensional simplex is also sufficiently small, and we can make all V([A.sub.i], [epsilon]),s contain this simplex. Then, this simplex is contained in the intersection of all V([A.sub.i], [epsilon])'s. Therefore, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and we can constructively find a point in this set.

4. Constructive version of Brouwer's fixed point theorem

First we define uniform continuity of functions and an approximate fixed point.

Definition 4.1. [Uniform continuity of functions] A function f is uniformly continuous if for each [x.sub.1], [x.sub.2] and [epsilon] > 0 there exists [delta] > 0 such that if [absolute value of [x.sub.2] - [x.sub.1]] < [delta], then [absolute value of f([x.sub.2]) - f([x.sub.1])] < [epsilon].

Definition 4.2. [An approximate fixed point] For each [epsilon] > 0 x is an approximate fixed point of f if [absolute value of x - f(x)] < [epsilon].

Now, using the constructive version of KKM lemma proved in the previous section, we shall show that there exists an approximate fixed point for any uniformly continuous function from an n-dimensional simplex to itself.

Theorem 4.3. [Constructive version of Brouwer's fixed point theorem] Any uniformly continuous function from an n-dimensional simplex [DELTA] to itself has an approximate fixed point.

Proof. Assume that a function f from an n-dimensional simplex [DELTA] to itself is uniformly continuous. Let [p.sub.0], [p.sub.1], ... and [p.sub.n] be the vertices of [DELTA]. Then a point x in [DELTA] is as x = [n.summation over (i=0)][[lambda].sub.i][p.sub.i], [n.summation over (i=0)][[lambda].sub.i] = 1, [[lambda].sub.i] [greater than or equal to] 0. Each pi denotes a point whose i- th component is

1. Components of f(x) and x are, respectively, denoted by [f.sub.i](x) and [x.sub.i]. Let [tau] > 0 be a real number, define a set [A.sub.i] as follows (4),

[A.sub.i] = {x [member of] [DELTA]|[f.sub.i](x) < [x.sub.i] + [tau]}.

Let x be a point contained in an n - 1-dimensional face of [DELTA] such that [x.sub.i] = 0 for one i among 0, 1, 2, ...,n (i-th component of its coordinates is 0) (5). Then, from [n.summation over (j=0)] [f.sub.j](x) =

[n.summation over (j=0)][x.sub.j] = 1 and [x.sub.i] = 0 we obtain

[n.summation over (j=0, j[not equal to]i)][f.sub.j](x) [less than or equal to] [n.summation over (j=0, j[not equal to]i)][x.sub.j].

Thus, there exists at least one j(j [not equal to] i)(denote it by k) such that

[f.sub.k](x) < [x.sub.k] + [tau].

Therefore, x is contained in [A.sub.k]. Similarly we can show that in a face of [DELTA] of less than n - 1 dimension a point x such that [x.sub.i] = 0 for some multiple i's among 0, 1, 2, ...,n is contained in [A.sub.k] for some k such that [x.sub.k] [not equal to] 0.

Because the conditions for the constructive version of KKM lemma are satisfied, we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let x be a point in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then, for each i the distance between x and some x' which satisfies [f.sub.i](x') < [x.sup.'.sub.i] + [tau] is smaller than [epsilon]. The uniform continuity of f implies that for [tau] > 0 we can select [epsilon] > 0 such that when [absolute value of x - x'] < [epsilon] we have [absolute value of f(x') - f(x)] < [tau]. Then, we obtain [absolute value of [f.sub.i](x') - [x.sup.'.sub.i] - ([f.sub.i](x) - [x.sub.i])] < [tau] + [epsilon].

Since x' satisfies [f.sub.i](x') < [x.sup.'.sub.i] + [tau], we have

[f.sub.i](x) - [x.sub.i] < 2[tau] + [epsilon] for all i. (4.1)

Adding (4.1) side by side except for one i yields

[n.summation over (j=0, j[not equal to]i)][f.sub.j](x) - [n.summation over (j=0, j[not equal to]i)] [x.sub.j] < 2n[tau] + n[epsilon].

From [n.summation over (j=0)] [f.sub.j](x) = [n.summation over (j=0)] [x.sub.j] = 1 we have 1 - [f.sub.i](x) < 1 - [x.sub.i] + 2n[tau] + n[epsilon], and so

[f.sub.i](x) - [x.sub.i] > -2n[tau] - n[epsilon] (4.2)

is obtained. From (4.1) and (4.2)

-2n[tau] - n[epsilon] < [f.sub.i](x) - [x.sub.i] < 2[tau] + [epsilon].

Since n is finite, 2n[tau] + n[epsilon] is a positive real number which may be arbitrarily small. Let denote anew 2n[tau] + n[epsilon] by [epsilon], we obtain the following result

[for all]i [absolute value of [f.sub.i](x) - [x.sub.i]] < [epsilon].

Further redefining (n + 1)[epsilon] by [epsilon], we obtain

[absolute value of f(x) - x] < [epsilon].

Therefore, x is an approximate fixed point of f(x). All points contained in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] satisfy this relation. We have completed the proof.

References

[1] D. Bridges and F. Richman, Varieties of Constructive Mathematics, Cambridge University Press, 1987.

[2] D. van Dalen, "Brouwer's [epsilon]-fixed point from Sperner's lemma", Logic Group Preprint Series, No. 275, 2009.

[3] F. E. Su, "Rental harmony: Sperner's lemma for fair devision", American Mathematical Monthly, vol. 106, pp. 930-942, 1999.

[4] H. Knaster, C. Kuratowski and S. Mazurkiewicz, "Ein Beweis des Fixpunktsatzes fur n-dimensional simplexe", Fund. Math., vol. 14, pp. 132-137, 1929.

[5] Y. Tanaka, "A proof of the existence of approximate core in NTU game directly by Sperner's lemma: A constructive analysis", Mathematics Applied in Science and Technology, Research India Publications, in press 2011.

[6] W. Veldman, "Brouwer's approximate fixed point theorem is equivalent to Brouwer's fan theorem", in Logicism, Intuitionism and Formalism, edited by Lindstrom, S., Palmgren, E., Segerberg, K. and Stoltenberg-Hansen, Springer, 2009.

Yasuhito Tanaka (1)

Faculty of Economics, Doshisha University, Kamigyo-ku, Kyoto, 602-8580, Japan E-mail: yasuhito@mail.doshisha.ac.jp

(1) This research was partially supported by the Ministry of Education, Science, Sports and Culture of Japan, Grant-in-Aid for Scientific Research (C), 20530165.

(2) The original paper of KKM lemma is [4].

(3) Usually in KKM lemma [A.sub.0], [A.sub.1], ...,[A.sub.n] are assumed to be closed sets. But in this lemma we do not assume so.

(4) In constructive mathematics, for any real number x we can not prove that x [less than or equal to] 0 or x > 0, that x > 0 or x = 0 or x < 0. Therefore, we can not define the following set.

[B.sub.i] = {x [member of] [DELTA]|[f.sub.i](x) [less than or equal to] [x.sub.i]}.

But for any distinct real numbers x, y and z such that x> z we can prove that x> y or y> z. Thus, we can define a set such as our Ai. See [1] about constructive mathematics.

(5) This face of [DELTA] is a convex hull of the vertices of [DELTA] other than [p.sub.i]. Similarly in cases below.

Printer friendly Cite/link Email Feedback | |

Author: | Tanaka, Yasuhito |
---|---|

Publication: | International Journal of Computational and Applied Mathematics |

Date: | Jan 1, 2012 |

Words: | 2107 |

Previous Article: | Analysis of a local discontinuous Galerkin finite element method for the Burgers-Fisher equation. |

Next Article: | Condition for positive definiteness of a matrix. |