Continuity and All That

Blake's Newton

Back

Contents

(A) Compactness and Continuity: Preliminaries
(B) Weierstrass Maximum Theorem
(C) Upper and Lower Semicontinuity of Correspondences
(D) Berge's Theorem

Selected References

(A) Compactness and Continuity: Preliminaries

Let (X, r ) be a metric space, with X as the space and r as the associated metric. Then, in any given metric space (X, r ), the following things may be defined:

Neighborhood: Ne(x) = {y X r (x, y) < e } is a "neighborhood" around x, i.e. Ne(x) is a set of points in X which are within metric distance e of x.

Limit: x X is a "limit point" of a set E X if every neighborhood Ne(x) (i.e. for every e > 0) has some point y E where y x.

Complement: Ec is the "complement" of E if any x マE implies x Ec

Closed: a set E X is "closed" if every limit point of E is in E.

Interior: x is an "interior point" of E if there is some e > 0 such that Ne(x) E

Open: a set E is "open" if every point x E is an interior point.

Bounded: a set E is "bounded" if for every x E, there is some real number m such that for any y E, r (x, y) < m.

Closure: cl(E) = E E where E is the set of limit points in E is defined as the "closure" of E (i.e. cl(E) is the smallest closed set containing E).

Theorem: (Closed/Open Complementarity) E is open iff Ec closed.

Proof: (i) Suppose Ec closed. Consider any x E. As Ec closed, then x Ec and x not limit of Ec. Thus, it must be that there is an e such that Ne(x) Ec = . This is true for all x E. Thus, E open. (ii) Suppose E open. Consider x = lim Ec. Then, Ne(x) Ec for all e > 0. Thus, x is not an interior point of E. Since E is open and x is not an interior point of E, then it must be that x Ec. Thus, Ec is closed.

Continuity: Let :(X, r ) (X, r ) be a function. is "continuous on x0" if, for any e > 0, there exists a d > 0 such that r ( (x), (x0)) < e wherever r (x, xo) < d . is a "continuous" function when it is continuous on all x0 X.

Theorem: (Continuity) :X Y is continuous iff for every open subset G Y, -1(G) is open.

Proof: (i) Let be continuous function. Choose x0 X. Then consider an open subset G Y where (x0) G. As G is open, then (x0) is in the interior of G so that we can then define Ne[ (x0)] G, i.e. an open e -ball around (x0). By continuity of at x0, we know that there is a d > 0 such that (Nd(x0)) Ne[ (x0)] G, thus Nd(x0) -1(G). As Nd (x0) is an open d -ball within -1(G), then x0 is an interior point. Thus -1(G) is open.Ne

(ii) Suppose -1(G) is open for every open set G Y. As G is open, we can define an open neighborhood Ne [ (x0)] G for any (x0) G. As -1(G) is open in X, then -1(Ne[ (x0)]) is open ball in X which contains x0. Thus, there is a neighborhood Nd(x0) -1(Nd [ (x0)]). Thus, (Nd(x0)) Ne ( (x0)). Thus is continuous in X.

Open Cover: let {Ga } be a collection of open subsets of X such that E a Ga , then {Ga} is an "open cover" of E.

Compactness: E is "compact" if every open cover of E has a finite subcover.

Thus, we approach one of the more important important theorems regarding a special type of metric space - the Euclidian space Rn:

Theorem: (Compactness Theorems) Let E be a set in Rn. Then the following are equivalent:
(a) E is closed and bounded (Heine-Borel)
(b) E is compact
(c) Every infinite subset of E has a limit point in E (Bolzano-Weierstrass)

Proof: We want to prove (a) (b) (c) (a). For this we need the following two lemmas:

Lemma: (Nested Set Property) If {In} is a sequence of closed intervals in R such that In In+1 (decreasing sequence of sets), then n=1 In .

Proof: In = [an, bn], thus we have a collapsing sequence of intervals. Let E = {a1, a2, ... } be the set of lower bounds. Obviously, E is non-empty and bounded above by b1 (the upper bound of the largest interval). Let x = sup E, i.e. the sup of the lower bounds. If m and n are positive integers, then an am+n < bm+n < bm, thus x < bm for each m 1 2, .... But, as x = sup E, then x am. Thus, x [am, bm) for each m = 1, 2, .... or, simply, x Im for m = 1, 2, ... or x n=1In . Q.E.D.

Lemma: (Nested Boxes) Let {Bk} be a sequence of "boxes" in Rn such that Bk Bk+1, n = 1, 2, ... Then k=1 Bk .

Proof: If B is a box, then B = {x Rn ai xi bi for i = 1, ..., n}. Thus, box Bk = {x Rn aki x bki for i = 1, .., n.} and {Bk} is a sequence of collapsing boxes. Let interval Bki = [aki, bki]. Consider sequence {Bki} where Bki B(k+1)i ...., i.e. a sequence of collapsing closed intervals. By previous lemma, k=1 Bki , i.e. there is a xi such that xi Bki for all k = 1, ..., n. Of course, this is true for all i, thus x = [x1, ...,xi, ... xn] Bk for all k = 1, .., n, i.e. x k=1 Bk. Q.E.D

(a) (b) (Heine-Borel Theorem): If E is bounded, we can enclose E in box B, i.e. E B = {x Rn ai xi bi, i = 1, .., n}. If B is compact, then as E is a closed subset of a compact set, is also compact. Thus, we claim B is compact. Proof: If not, then {Ga } is an open cover for B, but there is no finite sub-cover. Now, consider the following: for every i, Bi = {x R ai xi bi}. Define d = [・/font> ni=1 (bi - ai)] so, for all x, y B, r (x, y) d . Now, consider ci = (ai + bi)/2, i.e. ci bisects every interval Bi into two intervals, [ai, ci] and [ci, bi]. Thus, {ci} divides B into 2n boxes, call then Qj Rn where jQj = B.

Now, recall that {Ga }is an open cover for B, thus there must be at least one Qj that is not covered by any finite subcollection of {Ga} (otherwise B is compact). Call Qj = B1. Thus, r (x, y) d /2 for any x, y B1. Subdivide B1 again by bisection, e.g. there is a di = (ai + ci)/2, etc. Thus, we subdivide B1 into 2n boxes Jj whose union jJj = B1. So, define B2 as the "uncovered set" where B2 B1. Obviously, r (x, y) d /4 for any x, y B2. Continuing the process of subdividing eternally, then we obtain a sequence of boxes B B1 B2 .... where any Bk in this sequence is not covered by any finite subcollection of {Ga}. Obviously, for any x, y Bk, r (x, y) d /2k.

However, by previous lemma, there is an x Rn such that x Bk for all k = 1, 2, ...., i.e. $ x k=1 Bk. But x B and {Ga } is an open cover of B, thus there is some a such that x Ga . At this point, define Ne (x) = {y Rn r (x, y) < e } as an open e -neighborhood of x. But, as Ga is open, then for any e > 0, there is a y such that y Ne (x). But as {Bk} is an eternal subdivision, we can fit a box inside of Ne (x), i.e. there is some Bk (k sufficiently large) such that Bk Ne (x), which implies that r (x, y) > d /2k. But then, when this box is fitted, we need divide no further. Thus, for any Bk, there is some Ga such that Bk Ga . Thus we have a finite subcollection of {Ga } 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 Rn 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 Ne (x) with at most a finite number of elements in M. However, as M is infinite, thus no finite collection of open neighborhoods{Ne (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 xk E such that r (0, xk) > k for all k = 1, 2, .... The set S of such points xk is infinite and has no limit in Rn. Thus, (c) is not true. Case 2: suppose E is not closed. Then consider point x0 Rn such that x0 E but is nonetheless a limit point of E. Thus, there is a sequence {xn} x0 as n and xn E. Thus, {xn} 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 {Ga } be an open cover of (X). As is continuous, then -1(Ga) is an open subset of X for all a . Thus, a{-1(Ga )} is an open cover of X. But X is compact. Thus, there is a finite subcover, i.e. indices a 1, ..., a n such that X a in{ -1(Ga i)}. Since, by continuity, ( -1(E) E for all E Y, then (X) a in { -1(Ga i)} or (X) a in{Ga 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 Ne (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 = supx X (x) and m = infx X (x). Then, there is a point xM and a point xm in X such that (xM) = M and (xm) = 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 Rm and Y Rn. 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 Rm, Y Rn) is "upper semicontinuous at x" if whenever the following three conditions are met for any two sequences {xn} and {yn}:

(i) xn x
(ii) yn j (xn)
(iii) yn 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 {yn} 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 {yn} drawn in the graph of the correspondence will approximate a point (e.g. y) within the graph of the correspondence.

contin1.gif (4315 bytes)

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 Rn are compact. Then, j is upper semicontinuous if and only if the graph of j is closed, i.e. Gj ={(x, y) X Y y j (x)} is a closed set in Rn Rn.

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 yn in the convergent sequence yn y, it is true that yn j (xn) " xn x. Thus, by the definition of the graph of j , it is true that (xn, yn) Gj " xn, yn in their respective convergent sequences. As (xn, yn) 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) Gj ? Again, yes, as by the definition of u.s.c., y j (x). Thus every convergent sequence (xn, yn) in Gj has its limit in Gj . Thus Gj is closed.

(ii) closed graph usc: If Gj is closed, then every convergent sequence (xn, yn) Gj has its limit (x, y) in Gj . This implies that for all sequences xn x, yn j (xn), yn 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) Gj and thus Gj 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}ki=1 be a series of upper semicontinuous correspondences where j i: X Y. Then, the sum correspondence j : X Y (i.e. j = ・/font> ki=1 j i) is also upper semicontinuous.

Proof: Let us have convergent sequence{xn} in X where xn x and consider a sequence {yn} in Y where yn j (xn) and where j (xn) = ・/font> ki=1j (xn) and yn = ・/font> ki=1yni with yin j i(xn). As j i is upper semicontinuous, then there is a yi j i(x) such that the sequence {yni} converges to it, i.e. yni yi. As this is true for all i = 1, .., k, then limn ・/font> i=1k yni = ・/font> i=1k yi and ・/font> i=1k yi ・/font> i=1k j i(x) = j (x). Defining y = ・/font> i=1k yi, then limn yn = y and y j (x). Thus j is upper semicontinuous.

The next theorem is practically the same:

Theorem: (Product of usc) Let {j i}ki=1 be a series of upper semicontinuous correspondences where j i: X Y. Then, the product correspondence j : X Y (i.e. j = ki=1 j i = j 1 j 2 ... j k) is also upper semicontinuous.

Proof: Let us have convergent sequence{xn} in X where xn x and consider a sequence {yn} in Y where yn j (xn) and with j (xn) = ki=1j (xn) and yn = [yn1, yn2, .., ynk] with yin j i(xn). As j i is upper semicontinuous, then there is a yi j i(x) such that the sequence {yni} converges to it, i.e. yni yi. As this is true for all i = 1, .., k, then limn [yn1, yn2, ..., ynk] = [y1, y2, ..., yk] and [y1, y2, .., yk] j 1(x) j 2(x) .. j k(x) = i=1k j i(x). Defining y = [y1, y2, .., yk] and recalling that i=1k j i(x) = j (x), then limn yn = 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 Rm, Y Rn) is "lower semicontinuous at x" if whenever the following three conditions are met for any two sequences {xn} and {yn}:

(i) xn x
(ii) yn j (xn)
(iii) y j (x)

then it is also true that (iv) yn 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 {yn} 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 {yn} 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).

contin2.gif (4310 bytes)

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=1kj i or j = i=1kj i are lower semicontinuous if the series {j i}i=1k 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 : Rm Rn is "continuous" if it is both uppersemicontinuous and lower semicontinuous at all x Rm.

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 : Rn Rm R and j : Rm Rn (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 Back top Top

nextNext