Now, recall that {G_a }is an open cover for B, thus there must be at least one Q_j that is not covered by any finite subcollection of {G_a} (otherwise B is compact). Call Q_j = B₁. Thus, r (x, y) ｣ d /2 for any x, y ﾎ B₁. Subdivide B₁ again by bisection, e.g. there is a d_i = (a_i + c_i)/2, etc. Thus, we subdivide B₁ into 2ⁿ boxes J_j whose union ﾈ _jJ_j = B₁. So, define B₂ as the "uncovered set" where B₂ ﾌ B₁. Obviously, r (x, y) ｣ d /4 for any x, y ﾎ B₂. Continuing the process of subdividing eternally, then we obtain a sequence of boxes B ﾉ B₁ ﾉ B₂ .... where any B_k in this sequence is not covered by any finite subcollection of {G_a}. Obviously, for any x, y ﾎ B_k, r (x, y) ｣ d /2^k.

However, by previous lemma, there is an x ﾎ Rⁿ such that x ﾎ B_k for all k = 1, 2, ...., i.e. $ x ﾎ ﾇ^･_k=1 B_k. But x ﾎ B and {G_a } is an open cover of B, thus there is some a such that x ﾎ G_a . At this point, define N_e (x) = {y ﾎ Rⁿ ｽ r (x, y) < e } as an open e -neighborhood of x. But, as G_a is open, then for any e > 0, there is a y such that y ﾎ N_e (x). But as {B_k} is an eternal subdivision, we can fit a box inside of N_e (x), i.e. there is some B_k (k sufficiently large) such that B_k ﾌ N_e (x), which implies that r (x, y) > d /2^k. But then, when this box is fitted, we need divide no further. Thus, for any B_k, there is some G_a such that B_k ﾌ G_a . Thus we have a finite subcollection of {G_a } that covers B. Thus B is compact. As E is a closed subset of B, then E is compact. Q.E.D.

(b) ﾞ (c): Suppose E ﾌ Rⁿ is compact. Consider M ﾌ E where M is an infinite subset of E. If M has no limit in E, then for each x ﾎ E, we would have N_e (x) with at most a finite number of elements in M. However, as M is infinite, thus no finite collection of open neighborhoods{N_e (x)} can cover it. Thus M is not compact. However, without limit points, M is closed. As M ﾌ E is a closed subset but not compact, then E cannot be compact. A contradiction. Thus M must have a limit point in E. Q.E.D.

(c) ﾞ (a): we use "not (a)" ﾞ "not (c)" to prove this. Take two cases. Case 1: suppose E is not bounded. Then, there is points x_k ﾎ E such that r (0, x_k) > k for all k = 1, 2, .... The set S of such points x_k is infinite and has no limit in Rⁿ. Thus, (c) is not true. Case 2: suppose E is not closed. Then consider point x₀ ﾎ Rⁿ such that x₀ ﾏ E but is nonetheless a limit point of E. Thus, there is a sequence {x_n} ｮ x₀ as n ｮ ･ and x_n ﾎ E. Thus, {x_n} is an infinite subset of E without limit point in E. Thus, (c) not true. Q.E.D.

Thus equivalence (a) ﾞ (b) ﾞ (c) ﾞ (a) is proved.ｧ

The usefulness of this theorem can hardly be overstated - but the simplest, in our case, is that in Euclidian space, if a set X is closed and bounded, then we can claim it is compact.

Finally, consider the following theorem:

Theorem: (Compact Range of Continuous Functions) X is a compact metric space, Y is a metric space and let ｦ : X ｮ Y is a continuous mapping. Then ｦ (X) is a compact set.

Proof: Let {G_a } be an open cover of ｦ (X). As ｦ is continuous, then ｦ ^-1(G_a) is an open subset of X for all a . Thus, ﾈ_a{ｦ^-1(G_a )} is an open cover of X. But X is compact. Thus, there is a finite subcover, i.e. indices a ₁, ..., a _n such that X ﾌ ﾈ a _iⁿ{ｦ ^-1(G_{a i})}. Since, by continuity, ｦ (ｦ ^-1(E) ﾌ E for all E ﾌ Y, then ｦ (X) ﾌ ﾈ a _iⁿ ｦ {ｦ ^-1(Ga _i)} or ｦ (X) ﾌ ﾈ a _iⁿ{G_{a i}}. Thus, we have a finite subcover of ｦ (X). Thus, ｦ (X) is compact.ｧ

(B) The Weierstrass Maximum Theorem

We want to prove the Weierstrass Theorem, i.e. that a continuous, real-valued function over a compact set attains a maximum and a minimum. For this we need the following lemma:

Lemma: Let E be a non-empty bounded subset of R. Let s = sup E and t = inf E. Then s, t ﾎ cl(E).

Proof: If s ﾎ E, then s ﾎ cl(E). Suppose s ﾏ E, then for every e > 0, there is a z ﾎ E such that s - e < z < s, otherwise s - e would be an upper bound for E. But, then, for all e > 0, there is a z ﾎ N_e (s), thus s is a limit point of E. Thus, s ﾎ cl(E). We can do the same for t = inf E.ｧ

Now we can turn to the Weierstrass Maximum Theorem (Th. 1.7.4’ in Debreu, 1959):

Theorem: (Weierstrass) let ｦ : X ｮ R be a continuous real-valued function on a non-empty compact metric space X. Let M = sup_{xﾎ X} ｦ (x) and m = inf_{xﾎ X} ｦ (x). Then, there is a point x^M and a point x^m in X such that ｦ (x^M) = M and ｦ (x^m) = m, i.e. a continuous function ｦ (ｷ) attains a maximum and a minimum over a compact metric space.

Proof: X is compact. Thus, by the earlier theorem, ｦ(X) is compact. By Heine-Borel, ｦ (X) is closed and bounded. As ｦ (X) is a closed and bounded set of real numbers, then ｦ (X) = clｦ (X) and thus, by the previous lemma, contains its own supremum and infimum, i.e. sup ｦ (X) ﾎ ｦ (X) and inf ｦ (X) ﾎ ｦ (X).ｧ

(C) Upper and Lower Semicontinuity of Correspondences

What can we say about cases when we are not dealing with single-valued functions but rather correspondences (i.e. set-valued functions)? Thus, a correspondence j : X ｮ Y maps to a set and not a point, e.g. X ﾍ R^m and Y ﾍ Rⁿ. How do we define the "continuity" for a correspondence? A different approach must be followed.

Upper Semicontinuity: (Def: 1.8.d. in Debreu, 1959) a correspondence j : X ｮ Y (e.g. X ﾍ R^m, Y ﾍ Rⁿ) is "upper semicontinuous at x" if whenever the following three conditions are met for any two sequences {x_n} and {y_n}:

(i) x_n ｮ x
(ii) y_n ﾎ j (x_n)
(iii) y_n ｮ y

then it is also true that (iv) y ﾎ j (x). If j is "upper semicontinuous at x" for all x ﾎ X, then it is "upper semicontinuous".

Intuitively, we can see this criteria graphically in Figure 1: given a sequence {y_n} in the graph of the correspondence which approaches some endpoint y, does this endpoint y lie in the graph of j (x)? If so, then the correspondence is "upper semicontinuous". We can see this in the figure below where any sequence {y_n} drawn in the graph of the correspondence will approximate a point (e.g. y) within the graph of the correspondence.

Figure 1 - Upper Semicontinuous Correspondence

We now turn to an interesting theorem:

Theorem: (Closed Graph) Let j : X ｮ Y be a correspondence, where X, Y ﾍ Rⁿ are compact. Then, j is upper semicontinuous if and only if the graph of j is closed, i.e. G_j ={(x, y) ﾎ X ｴ Y ｽ y ﾎ j (x)} is a closed set in Rⁿ ｴ Rⁿ_.

Proof: As this is an "if and only if" statement, we need to prove it both ways.

(i) usc ﾞ closed graph: Let j be upper semicontinuous. Then for all yⁿ in the convergent sequence yⁿ ｮ y, it is true that yⁿ ﾎ j (xⁿ) " xⁿ ｮ x. Thus, by the definition of the graph of j , it is true that (xⁿ, yⁿ) ﾎ G_j " xⁿ, yⁿ in their respective convergent sequences. As (xⁿ, yⁿ) converges to (x, y), by the definition of u.s.c., then (x, y) is a limit point of the graph of j . Is (x, y) ﾎ G_j ? Again, yes, as by the definition of u.s.c., y ﾎ j (x). Thus every convergent sequence (xⁿ, yⁿ) in G_j has its limit in G_j . Thus G_j is closed.

(ii) closed graph ﾞ usc: If G_j is closed, then every convergent sequence (xⁿ, yⁿ) ﾎ G_j has its limit (x, y) in G_j . This implies that for all sequences xⁿ ｮ x, yⁿ ﾎ j (xⁿ), yⁿ ｮ y, then y ﾎ j (x), i.e. it cannot be that the first three properties are fulfilled and the last (y ﾎ j (x)) is not for that would mean that (x, y) ﾏ G_j and thus G_j would not be closed. Thus j is upper semicontinuous at x. Since x is arbitrary, then this is true for any x ﾎ X. Thus, j is upper semicontinuous.ｧ

Note: the assumption in this proof that the range of the correspondence j is compact can be seen to be necessary. A counterexample can be constructed of a closed graph which is not u.s.c. if the range fails to be compact. Consider the following correspondence: j (x) = {1/x} for x > 0 and j (x) = {0} for x = 0. There is indeed a closed graph, but it is not u.s.c. at x = 0. Also, for the first part of the proof, that we must assume that the domain X is closed - or else j (.) may not be defined at x.

The sum and Cartesian product of a series upper semicontinuous correspondences is also upper semicontinuous.

Theorem: (Sum of usc) Let {j _i}^k_i=1 be a series of upper semicontinuous correspondences where j _i: X ｮ Y. Then, the sum correspondence j : X ｮ Y (i.e. j = ・/font> ^k_i=1 j _i) is also upper semicontinuous.

Proof: Let us have convergent sequence{x_n} in X where x_n ｮ x and consider a sequence {y_n} in Y where y_n ﾎ j (x_n) and where j (x_n) = ・/font> ^k_i=1j (x_n) and y_n = ・/font> ^k_i=1y_nⁱ with yⁱ_n ﾎ j _i(x_n). As j _i is upper semicontinuous, then there is a yⁱ ﾎ j _i(x) such that the sequence {y_nⁱ} converges to it, i.e. y_nⁱ ｮ yⁱ. As this is true for all i = 1, .., k, then lim_{nｮ ･} ・/font> _i=1^k y_nⁱ = ・/font> _i=1^k yⁱ and ・/font> _i=1^k yⁱ ﾎ ・/font> _i=1^k j _i(x) = j (x). Defining y = ・/font> _i=1^k yⁱ, then lim_{nｮ ･} y_n = y and y ﾎ j (x). Thus j is upper semicontinuous.ｧ

The next theorem is practically the same:

Theorem: (Product of usc) Let {j _i}^k_i=1 be a series of upper semicontinuous correspondences where j _i: X ｮ Y. Then, the product correspondence j : X ｮ Y (i.e. j = ﾕ ^k_i=1 j _i = j ₁ ｴ j ₂ ｴ ... ｴ j _k) is also upper semicontinuous.

Proof: Let us have convergent sequence{x_n} in X where x_n ｮ x and consider a sequence {y_n} in Y where y_n ﾎ j (x_n) and with j (x_n) = ﾕ ^k_i=1j (x_n) and y_n = [y_n¹, y_n², .., y_n^k] with yⁱ_n ﾎ j _i(x_n). As j _i is upper semicontinuous, then there is a yⁱ ﾎ j _i(x) such that the sequence {y_nⁱ} converges to it, i.e. y_nⁱ ｮ yⁱ. As this is true for all i = 1, .., k, then lim_{nｮ ･} [y_n¹, y_n²_{, ...,} y_n^k] = [y¹, y², ..., y^k] and [y¹, y², .., y^k] ﾎ j ₁(x)ｴ j ₂(x)ｴ ..ｴ j _k(x) = ﾕ _i=1^k j _i(x). Defining y = [y¹, y², .., y^k] and recalling that ﾕ _i=1^k j _i(x) = j (x), then lim_{nｮ ･} y_n = y and y ﾎ j (x). Thus j is upper semicontinuous.ｧ

Let us now turn to the analogous concept of lower semicontinuity:

Lower Semicontinuity: (Def: 1.8.e in Debreu, 1959) a correspondence j : X ｮ Y (e.g. X ﾍ R^m, Y ﾍ Rⁿ) is "lower semicontinuous at x" if whenever the following three conditions are met for any two sequences {x_n} and {y_n}:

(i) x_n ｮ x
(ii) y_n ﾎ j (x_n)
(iii) y ﾎ j (x)

then it is also true that (iv) y_n ｮ y. If j is "lower semicontinuous at x" for all x ﾎ X, then it is "lower semicontinuous".

Intuitively, we can see this criteria graphically again, this time in Figure 2: given an endpoint y ﾎ j (x) in the graph, is there a sequence {y_n} in the graph that approaches it? If so, then the correspondence is "lower semicontinuous". In the earlier Figure 1, we do not have a lower semicontinuous function at x as the point y ﾎ j (x) cannot be approximated from the right by a sequence of points in the graph. However, in Figure 2, the correspondence is indeed lower semicontinuous as any endpoint y in j (x) is approximated from either side by a sequence {y_n} in the graph. However, the graph below is not upper semicontinuous as, for instance, we can imagine a sequence in the graph approximating y｢ yet y｢ ﾏ j (x).

Figure 2 - Lower Semicontinuous Correspondence

Finally, we should note that the sum and product of a series of a lower upper semicontinuous correspondences is also lower semicontinuous, i.e. correspondence j : X ｮ Y where j = ・/font> _i=1^kj _i or j = ﾕ _i=1^kj _i are lower semicontinuous if the series {j _i}_i=1^k where j _i:X ｮ Y is also lower semicontinuous. The proof is analogous to that of the upper semicontinuous case.

Finally we turn to continuity:

Continuity (Def. 1.8.f in Debreu, 1959): a correspondence j : R^m ｮ Rⁿ is "continuous" if it is both uppersemicontinuous and lower semicontinuous at all x ﾎ R^m.

Thus, in the previous figures, the correspondences are not continuous as the first is upper semicontinuous (but not lower semi-continuous) while the second is lower semicontinuous (but not upper semi-continuous).

(D) Berge’s Theorem

The following theorem (Berge's Theorem, i.e. Th. 1.8.4 in Debreu, 1959) is very useful. Let ｦ : Rⁿ ｴ R^m ｮ R and j : R^m ｮ Rⁿ (i.e. ｦ is a function and j a correspondence). Then let:

f(t) = max ｦ (x, t) s.t. x ﾎ j (x)

F(t) = argmax ｦ (x, t) s.t. x ﾎ j (x).

thus, f(t) is a function and F(t) is a correspondence (for "argmax" read "the argument (x) that maximizes ｦ (x, t)"). Then the following holds:

Theorem: (Berge) If ｦ (x, t) is a jointly continuous function and j (x) is both an upper semicontinuous and lower semicontinuous correspondence (i.e. a continuous correspondence), then: (i) f(t) is a continuous function and (ii) F(t) is an upper semicontinuous correspondence.

Proof: Omitted. See Hildenbrand (1974: p.30) or Border (1985: p.64)

Selected References

Kim C. Border (1985) Fixed Point Theorems with Applications to Economics and Game Theory. Cambridge, UK: Cambridge University Press.

Gerard Debreu (1959) Theory of Value: An axiomatic analysis of economic equilibrium. New York: Wiley.

Werner Hildenbrand (1974) Core and Equilibria of a Large Economy. Princeton: Princeton University Press.

Hukukane Nikaido (1968) Convex Structures and Economic Theory. New York: Academic Press.

Back

Top

Next

---

Home	Alphabetical Index	Schools of Thought	Surveys and Essays
Web Links	References	Contact	Frames