Principles of Mathematics in Operations Research

10.2 Compact Sets 147

Example 10.2.2 X = Rk with d 2 metric:

E = B 1 (0), for n £ N, Gn = 3^.(0) =>£c U??=i Gn.

Example 10.2.3 X = R, E = (0,1):

V.x 6 (0,1),GX = (-1,1) => E C Ux€(o,i) G-

Definition 10.2.4 i? is said to be compact if for every open cover {Gi : i £ 1}

of E, we can find

Gi,,..., Gin 3 EC [Gu U Gh u • • • U G,;J.

Example 10.2.5 /nX = R, J3 = (0,1) is not compact:

Consider {Gx : x £ (0,1)} where Gx = ( — 1,2;). Suppose 3xi,..., xn 6 (0,1) 3

(0,1) C Ur=i(-^1 'a;i)- Let Y = max{.x 1 ,...,x„} =* 0 < y < 1 =* (0,1) C

(-1,y). Lei ,i = ^ => 0 < K 1, a; £ (-1,2/) Contradiction! Thus, (0,1) is

no/, compact.

Remark 10.2.6 /« i/ie Euclidean space, open sets are not compact.

Theorem 10.2.7 Let K C Y C X. Then, K is compact relative to Y if and
only if K is compact relative to X.

Proof. (=>): Suppose K is compact relative to Y. Let {Gi,i £ 1} be an open
cover of K in X. Then, K c Uie/ ft, so X = /CnY C (U,:e/ G^tlY =
\Ji(:]{GiC\Y): open relative to Y. Since K is open relative to Y, 3i\,.. ., in 3
K <z {Gix n Y) u (Gi 2 n y) u • • • u {Gin n y) => ir c \J"=1 Gz.
{<=): Suppose K is compact relative to X. Let {Ei,i £ 7} be any open
cover of K in Y. Then,
V?; e / 3 an open set Gt £ X 3El = GlnY.K c (\JieT Et) c ((Jie/ G<).
So, {Gi, i G 7} is an open cover in X. Then, 3i\,... ,in 3
K c Gu U Gi2 U • • • U Gin => K = K n r C (G^ n y) U • • • U (Gln n Y) =
EuU..UEln. 0

Theorem 10.2.8 Let {X, d) be a metric space and K C X be compact. Then,
K is closed.

Proof We will show that K° is open.
Let p £ Kc be an arbitrary fixed point. Vg £ K => d(p, g) > 0. Let ?* 9 =
\d{p,q) >0.
Vr, = Br{p), Wq = #r(</)- # C U 9 e/c ^f/ (because if is compact)

=> 3gi,... ,<7„ eifS/fC^U-U W,„ = W.

Let K = Vqx n V 92 n • • • n Vqn Air = Min {rqi,..., r,ln } > 0, then V = Br{p).
Let us show that W n V = 0: If not, 3zeVKnV=>zeVK=>z€ Wg, for
some i — 1,... ,n. Hence, d(z,qi) < r,h — ^d{p,q{). z £ V => z £ Vq% for the
same i. Thus, d{z,p) < r(h = ^d{p,qi).