San José State University|
Department of Economics
& Tornado Alley
Fixed Point Theorems
Let f be a function which maps a set S into itself; i.e. f:S → S. A fixed point of the mapping f is an element x belonging to S such that f(x) = x. Fixed points are of interest in themselves but they also provide a way to establish the existence of a solution to a set of equations. For example, in theoretical economics, such as general equilibrium theory, there comes at point where one needs to know whether the solution to a system of equations necessarily exists; or, more specifically, under which conditions will a solution necessarily exist. The mathematical analysis of this question usually relies on fixed point theorems.
As stated previously, if f is a function which maps a set S into itself; i.e. f:S →S, a fixed point of the mapping is an element x belonging to S such that f(x) = x. If the system of equations for which a solution is sought is of the form g(x)=0, then if the function g should be represented as g(x)=f(x)-x. A fixed point of f is a solution to g(x)=0.
The most important fixed point theorem is Brouwer's.
|Brouwer's Fixed Point Theorem: A continuous mapping of a convex, closed set into itself necessarily has a fixed point.|
Below is shown an illustration of Brouwer's Fixed Point Theorem for the mapping of the unit interval into itself. For any continuous mapping there is necessarily some point such that f(x)=x. This is indicated by the point where the continuous fuction crosses the diagonal, which represents x=x. There is no way to draw a continuous function that starts on the vertical axis at x=0 and ends on the vertical axis at x=1 without crossing or touching the diagonal.
Brouwer's Fixed Point Thoerem for a a disk can be easily proven by means of an intuitive proposition.
|No Retraction Theorem: There is no continuous mapping of all points of the interior of disk onto its boundary circle.|
Proof of Brouwer's fixed point theorem for a disk using the No Retraction Theorem.
Assume there is no fixed point and use the intersection of the line from x to f(x) with the boundary circle to map x into the boundary as shown below.
Let point A be an arbitrary point in the disk. Point B represents the point A is mapped to. A line is drawn from A to B and continued until it intersects the boundary of the disk at point C. Now the mapping under consideration is the mapping of A to C.
This would be a continuous mapping of the interior onto the boundary. The existence of such a mapping is a contradiction of the No Retraction Theorem so the process must break down somewhere. It breaks down if f(x)=x because there is no unique line defined. Therefore, since the assumption of no fixed point leads to a contradiction of the No Retraction Theorem there must be at least one fixed point.
A topological space that is such that any continuous mapping of it into itself must have a fixed point is said to have the fixed point property. Not all topological spaces have the fixed point property. The annulus shown below does not have the fixed point property. This can easily be established by noting that the continuous mapping which rotates the annulus has no fixed point. If there were no hole in the disk then the center of the disk would be the fixed point of any rotation. But the center of the disk is not part of the annulus.
A physical example of a fixed point of a mapping is the center of a whirlpool in a cup of tea when it is stirred. (The fact that the center of the whirlpool moves over time is just due to the fact that the mapping is changing over time.)
There is a related problem involving the mapping of the points of a sphere into itself. This is a closed surface but not a convex surface. Nevertheless any continuous mapping of a sphere into itself does have a fixed point. This is illustrated by considering the "hair" on a coconut. Assume each hair lies down so the tip of a hair touchs the sphere. Consider the root of the hair as being x and the point where the tip touches the sphere as f(x). The fact that a fixed point necessarily exists corresponds to the existence of a "whorl." Thus,
You Can't Comb the Hair on a Coconut Without There Being a Whorl (fixed point).
A very important fixed point theorem for economic analysis is:
Let Q and P be n-dimensional vectors of outputs and prices. Let Q=D(P) be the demand functions for the outputs. Let Q = S(P) be the supply functions for the outputs. If suppliers expect a set of prices given by P then they will be on the market the outputs given by Q = S(P). When this vector of outputs is put on the market the prices which will prevail is P* = D-1Q = D-1(S(P)). An equilibrium set of prices is one such that P* is the same as P. In other words, an equilibrium prices are such that P=H(P) where H() = D-1(S()).
Question: If the prices P can have any non-negative values does this set satisfy the conditions of Brouwer's Theorem? Answer: Yes, it is a closed, convex set?
In economics it is really only the relative prices which are important. This means that if all prices are multiplied by an arbitrary constant the prices would generate the same quanities demanded and supplied. This leads to the concept of "normalizing" prices. For example, the price of one good, say gold, may be arbitrarily set equal to unity. The good whose price is set equal to unity is called the "numeraire" for the economy.
Another way the prices can be normalized is by making the sum of the prices equal unity; i.e., Σpi = 1.
Question: Does the set of prices satisfying the "sum equals unity" condition with non-negative prices satisfy the conditions of Brouwer's theorem?
Answer: Yes, it is closed, bounded and convex.
This theorem is especially useful in establishing the existence of solutions to differential and integral equations.
Another approach to looking for a solution to g(x)=0 is by checking the value of g at a finite number of points in an interval and bracketing the solution point.
|Sperner's Lemma: |
(One dimensional version)
Consider a line segment AB subdivided into segments and the end points of the segments labeled with A's and B's arbitrarily. There has to be at least one segment labeled AB.
Let a be the number of segments labeled AA and b the number of segments labeled AB, complete segments. The number of end points labeled with A is 2a+b. Let c be the number of internal end points labeled A. If we count A end points segment by segment we get 2c+1. Therefore 2a+b=2c+1, which implies that b=2(c-a)+1 so b, the number of segments labeled AB, is an odd number. Since zero is not an odd number there has to be at least one segment labeled AB.
Instead of labels of A and B, consider positive and negative.
(Two dimensional version)
Let ABC be a triangle which is divided up into subtriangles with the vertices labeled arbitrarily as A, B, or C. There must be at least one sub-triangle with labeling ABC.
The original vertices are included in the labeling. Let a be the number of triangles whose labels read ABA or BAB. Triangles of these two types have two edges labeled AB where as complete triangles have one edge labeled AB. The other types of triangles have no edges labeled AB. The number of AB edges counted triangle by triangle is 2a+b. However, edges inside the original triangle are counted twice since they belong to two triangles. Let c be the number of edges labeled AB inside the original triangle. Let d be the number of edges labeled AB on the outside of the original triangle. Then the number of AB edges counted is 2c+d and this is equal to 2a+b. So 2c+d=2a+b. From the preceding result b must be odd so d also must be odd. Therefore there must be at least one triangle with labeling ABC.
Some fixed points theorems can be stated in the form that the number of fixed points must be an odd number. Since zero is not an odd number this means that there must be at least one fixed point. However, in order for the number of fixed points to be odd there is a transversality condition that must be satisfied at each fixed point. This transversality condition is essentially that there is not a tangency condition at the fixed point.
Expressed in a more positive form, the important result is that properly enumerated the number of fixed points must be odd.
A continuous function f(x) of the unit interval [0,1] into itself must start out on or above of the diagonal and must end up on or below the diagonal. At some point then the continuous function must cross the diagonal. If the function crosses the diagonal from above and then recrosses it from below it is then above the diagonal again and must recross it to end up on or below it. There must then be at least one more fixed point.
But there is also the case in which the function touches the diagonal tangentially. This case seems to involve an even number of fixed points. However the tangential fixed point should be counted as a double fixed point, two fixed points in one.
Generally if f(x)=x and f'(x)=1 then the degree or multiplicity of such a fixed point is greater than one. If f(x)=x, f'(x)=1 and f"(x)≠0 then the multiplicity of the fixed point is two. The case of f(x)=x, f'(x)=1 and f"(x)=0 is the case of an inflection point and its multiplicity is three.
The sum of the multiplicities of the fixed points must be odd.
(To be continued.)
|HOME PAGE OF applet-magic.com
HOME PAGE OF Thayer Watkins