$\newcommand{\br}{\\}$ $\newcommand{\R}{\mathbb{R}}$ $\newcommand{\Q}{\mathbb{Q}}$ $\newcommand{\Z}{\mathbb{Z}}$ $\newcommand{\N}{\mathbb{N}}$ $\newcommand{\C}{\mathbb{C}}$ $\newcommand{\P}{\mathbb{P}}$ $\newcommand{\F}{\mathbb{F}}$ $\newcommand{\L}{\mathcal{L}}$ $\newcommand{\spa}[1]{\text{span}(#1)}$ $\newcommand{\dist}[1]{\text{dist}(#1)}$ $\newcommand{\max}[1]{\text{max}(#1)}$ $\newcommand{\min}[1]{\text{min}(#1)}$ $\newcommand{\supr}{\text{sup}}$ $\newcommand{\infi}{\text{inf}}$ $\newcommand{\ite}[1]{\text{int}(#1)}$ $\newcommand{\ext}[1]{\text{ext}(#1)}$ $\newcommand{\bdry}[1]{\partial #1}$ $\newcommand{\argmax}[1]{\underset{#1}{\text{argmax }}}$ $\newcommand{\argmin}[1]{\underset{#1}{\text{argmin }}}$ $\newcommand{\set}[1]{\left\{#1\right\}}$ $\newcommand{\emptyset}{\varnothing}$ $\newcommand{\tilde}{\text{~}}$ $\newcommand{\otherwise}{\text{ otherwise }}$ $\newcommand{\if}{\text{ if }}$ $\newcommand{\proj}{\text{proj}}$ $\newcommand{\union}{\cup}$ $\newcommand{\intercept}{\cap}$ $\newcommand{\abs}[1]{\left| #1 \right|}$ $\newcommand{\norm}[1]{\left\lVert#1\right\rVert}$ $\newcommand{\pare}[1]{\left(#1\right)}$ $\newcommand{\brac}[1]{\left[#1\right]}$ $\newcommand{\t}[1]{\text{ #1 }}$ $\newcommand{\head}{\text H}$ $\newcommand{\tail}{\text T}$ $\newcommand{\d}{\text d}$ $\newcommand{\limu}[2]{\underset{#1 \to #2}\lim}$ $\newcommand{\limsupu}[2]{\underset{#1 \to #2}{\lim\supr}}$ $\newcommand{\liminfu}[2]{\underset{#1 \to #2}{\lim\infi}}$ $\newcommand{\limd}[3]{\underset{#1 \to #2; #3}\lim}$ $\newcommand{\der}[2]{\frac{\d #1}{\d #2}}$ $\newcommand{\derw}[2]{\frac{\d #1^2}{\d^2 #2}}$ $\newcommand{\pder}[2]{\frac{\partial #1}{\partial #2}}$ $\newcommand{\pderw}[2]{\frac{\partial^2 #1}{\partial #2^2}}$ $\newcommand{\pderws}[3]{\frac{\partial^2 #1}{\partial #2 \partial #3}}$ $\newcommand{\inv}[1]{{#1}^{-1}}$ $\newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $\newcommand{\nullity}[1]{\text{nullity}(#1)}$ $\newcommand{\rank}[1]{\text{rank }#1}$ $\newcommand{\nullspace}[1]{\mathcal{N}\pare{#1}}$ $\newcommand{\range}[1]{\mathcal{R}\pare{#1}}$ $\newcommand{\var}[1]{\text{var}\pare{#1}}$ $\newcommand{\cov}[2]{\text{cov}(#1, #2)}$ $\newcommand{\tr}[1]{\text{tr}(#1)}$ $\newcommand{\oto}{\text{ one-to-one }}$ $\newcommand{\ot}{\text{ onto }}$ $\newcommand{\ipto}{\overset{\text{i.p.}}\longrightarrow}$ $\newcommand{\asto}{\overset{\text{a.s.}}\longrightarrow}$ $\newcommand{\expdist}[1]{\text{ ~ Exp}(#1)}$ $\newcommand{\unifdist}[1]{\text{ ~ Unif}(#1)}$ $\newcommand{\normdist}[2]{\text{ ~ N}(#1,#2)}$ $\newcommand{\berndist}[2]{\text{ ~ Bernoulli}(#1,#2)}$ $\newcommand{\geodist}[1]{\text{ ~ Geometric}(#1)}$ $\newcommand{\poissondist}[1]{\text{ ~ Poisson}(#1)}$ $\newcommand{\ceil}[1]{\lceil#1\rceil}$ $\newcommand{\floor}[1]{\lfloor#1\rfloor}$ $\newcommand{\Re}[1]{\text{Re}(#1)}$ $\newcommand{\Im}[1]{\text{Im}(#1)}$ $\newcommand{\dom}[1]{\text{dom}(#1)}$ $\newcommand{\fnext}[1]{\overset{\sim}{#1}}$ $\newcommand{\transpose}[1]{{#1}^{\text{T}}}$ $\newcommand{\b}[1]{\boldsymbol{#1}}$ $\newcommand{\None}[1]{}$ $\newcommand{\Vcw}[2]{\begin{bmatrix} #1 \br #2 \end{bmatrix}}$ $\newcommand{\Vce}[3]{\begin{bmatrix} #1 \br #2 \br #3 \end{bmatrix}}$ $\newcommand{\Vcr}[4]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \end{bmatrix}}$ $\newcommand{\Vct}[5]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \br #5 \end{bmatrix}}$ $\newcommand{\Vcy}[6]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \br #5 \br #6 \end{bmatrix}}$ $\newcommand{\Vcu}[7]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \br #5 \br #6 \br #7 \end{bmatrix}}$ $\newcommand{\vcw}[2]{\begin{matrix} #1 \br #2 \end{matrix}}$ $\newcommand{\vce}[3]{\begin{matrix} #1 \br #2 \br #3 \end{matrix}}$ $\newcommand{\vcr}[4]{\begin{matrix} #1 \br #2 \br #3 \br #4 \end{matrix}}$ $\newcommand{\vct}[5]{\begin{matrix} #1 \br #2 \br #3 \br #4 \br #5 \end{matrix}}$ $\newcommand{\vcy}[6]{\begin{matrix} #1 \br #2 \br #3 \br #4 \br #5 \br #6 \end{matrix}}$ $\newcommand{\vcu}[7]{\begin{matrix} #1 \br #2 \br #3 \br #4 \br #5 \br #6 \br #7 \end{matrix}}$ $\newcommand{\Mqw}[2]{\begin{bmatrix} #1 & #2 \end{bmatrix}}$ $\newcommand{\Mqe}[3]{\begin{bmatrix} #1 & #2 & #3 \end{bmatrix}}$ $\newcommand{\Mqr}[4]{\begin{bmatrix} #1 & #2 & #3 & #4 \end{bmatrix}}$ $\newcommand{\Mqt}[5]{\begin{bmatrix} #1 & #2 & #3 & #4 & #5 \end{bmatrix}}$ $\newcommand{\Mwq}[2]{\begin{bmatrix} #1 \br #2 \end{bmatrix}}$ $\newcommand{\Meq}[3]{\begin{bmatrix} #1 \br #2 \br #3 \end{bmatrix}}$ $\newcommand{\Mrq}[4]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \end{bmatrix}}$ $\newcommand{\Mtq}[5]{\begin{bmatrix} #1 \br #2 \br #3 \br #4 \br #5 \end{bmatrix}}$ $\newcommand{\Mqw}[2]{\begin{bmatrix} #1 & #2 \end{bmatrix}}$ $\newcommand{\Mwq}[2]{\begin{bmatrix} #1 \br #2 \end{bmatrix}}$ $\newcommand{\Mww}[4]{\begin{bmatrix} #1 & #2 \br #3 & #4 \end{bmatrix}}$ $\newcommand{\Mqe}[3]{\begin{bmatrix} #1 & #2 & #3 \end{bmatrix}}$ $\newcommand{\Meq}[3]{\begin{bmatrix} #1 \br #2 \br #3 \end{bmatrix}}$ $\newcommand{\Mwe}[6]{\begin{bmatrix} #1 & #2 & #3\br #4 & #5 & #6 \end{bmatrix}}$ $\newcommand{\Mew}[6]{\begin{bmatrix} #1 & #2 \br #3 & #4 \br #5 & #6 \end{bmatrix}}$ $\newcommand{\Mee}[9]{\begin{bmatrix} #1 & #2 & #3 \br #4 & #5 & #6 \br #7 & #8 & #9 \end{bmatrix}}$
Definition: Compactness

A metric space $(X,d)$ is compact iff every sequence in $(X,d)$ has at least one convergent subsequence. i.e.

$$\forall (x^{(n)})^\infty_{n =1} \in X, \exists \limu{ j }{ \infty}(x^{(n_j)})^\infty_{ j =1} = L $$

A subset $Y \subseteq X$ is compact iff the subspace $(Y,d|_{Y\times Y})$ is compact.

Remarks

Compactness of a set $Y$ is an intrinsic property, since it only depends on the metric function $d|_{(Y, d|_{Y \times Y})}$ restricted to $Y$, and not on the choice of the ambient space $X$.

The notions of completeness and of boundedness are also intrinsic, but the notions of open and closed are not.

Definition: Bounded Sets

Let $(X,d)$ be a metric space, and let $Y \subseteq X$.

$Y$ is bounded iff $$\exists B(x, r), Y \subseteq B(x, r) \subseteq X $$

Proposition

A compact metric space is both complete and bounded.

Let $(X, d)$ be a compact metric space. Let $(x^{(n)})^\infty_{ n =1}$ be a Cauchy sequence in $X$.

Proof 
  </span>
</span>
<span class="proof__expand"><a>[expand]</a></span>

Completeness:

Since $(X, d)$ is compact, $(x^{(n)})^\infty_{ n =1}$ has a convergent subsequence.

Therefore $(x^{(n)})^\infty_{ n =1}$ is convergent.

Boundedness:

Assume on the contrary, $(X, d)$ is not bounded.

Then we can construct a sequence as follows.

Choose $x_0 \in X$,
choose $x_1 \in X, d(x_0, x_1) > 1 $,
choose $x_2 \in X, d(x_0, x_2) > 2 $,
choose $x_n \in X, d(x_0, x_n) > n $.

Since $(X, d) $ is not bounded, we can construct such a sequence with infinite elements, and this sequence does not converge to any specific point, because if a limit $L$ exists, $\limu{ n }{ \infty } d(x_n, L) = 0 $

However, $d(x_0, x_n) \leq d(x_0, L) + d(L, x_n)$.

Since $\limu{ n }{ \infty }d(x_0, x_n) = \infty $ by construction, $\limu{ n }{ \infty } d(x_n, L) \to \infty $.

CONTRADICTION.

Hence $(X, d) $ must be bounded.

Corollary : Compact Sets Are Closed and Bounded

Let $(X,d)$ be a metric space, and let $Y$ be a compact subset of $X$. Then $Y$ is closed and bounded.

Proof 
  </span>
</span>
<span class="proof__expand"><a>[expand]</a></span>

$Y$ is a compact subset of $X$.

Closedness:

Assume on the contrary, $Y$ is not closed. Then exists $x_0 \in \bdry{ Y }, x_0 \not \in Y$. Since $x_0$ is an adherent point of $Y$, there must exist a sequence $(y^{(n)})^\infty_{ n =1} $ in $Y$, such that $\limu{ n }{ \infty } (y^{(n)})^\infty_{ n =1} = x_0$.

However, if $(y^{(n)})^\infty_{ n =1} $ does exist, since $Y$ is compact. The limit $x_0 $ must be inside $Y $ as well.

Then $x_0$ is an interior point of $Y$. CONTRADICTION.

Boundedness:

Since $X$ is compact, then $X$ is bounded. Hence $Y$ is bounded.

Theorem : Heine-Borel Theorem

$(R^n, d)$ where $d = d_{l^2}$, or $d = d_{l^1}$, or $d = d_{l^\infty}$. $E \subseteq \R^n $.

Then $E$ is compact $\iff $ $E$ closed and bounded.

Theorem : Every Open Cover of a Compact Set Has a Finite Subcover

Let $(X,d)$ be a metric space, and let $Y \subseteq X$ is compact.

Let $(V_ \alpha)_ { \alpha \in I}$ be a collection of open sets in $X$, and suppose that

$$Y \subseteq \bigcup_{ \alpha \in I } V_ \alpha $$

Then there exists a finite subset $F$ of $I$ such that

$$Y \subseteq \bigcup_{ \alpha \in F } V_ \alpha$$

Proof 
  </span>
</span>
<span class="proof__expand"><a>[expand]</a></span>

$r(y) = \supr{\set{ r> 0 : B(y ,r) \subseteq V_ \alpha }}. r(y) > 0, \forall y \in X$.

($V_\alpha$s are open)

$r_0 = \infi{\set{ r(y) : y \in Y }} $

$r_0 \geq 0$

step 1

$r_0 \neq 0$

Assume $r_0 = 0, \exists r(y ^{(n)}) \in \set{ r(y), y \in Y }$

$0 < r(y^{(n)}) < \frac{ 1 }{ n }$($\limu{ n }{ \infty } r(y^{(n)}) = 0 $)

$(y^{(n)})^\infty_{ n =1} $ is a sequence in $Y $(compact)

$\exists y_0 \in Y$ and subsequence $(y^{(n_j)})^\infty_{ j =1} $

$(y^{(n_j)})^\infty_{ j =1} \to y_0$

$y_0 \in Y, r(y_0) > 0$

This then shows

$$r(y^{(n_0)}) \geq \frac{ r(y_0)}{ 2 }$$

Triangle inequality to show that

$B(y^{(n_j)}, \frac{ r(y_0)}{ 2 }) \subset B(y_0, r(y_0)) $

$s^{(n)} \geq K $

$\limu{ n }{ \infty } s^{(n)} \geq k $

$r(y^{(n_j)}) \geq \frac{ r(y_0)}{ 2 } > 0 $

$\limu{ j }{ \infty } r(y^{(n_j)}) \geq \frac{ r(y_0)}{ 2 }$

$(\limu{ n }{ \infty } r(y^{(n)}) = 0) $

$r_0 > 0 $ Let’s assume $\forall F \subset I $ finite $Y \not \subset \bigcup_{ \alpha \in F } V_ \alpha $

Let $K = \frac{ r_0 }{ 2 } > 0 $

Pick $y^{(i)} \in Y $

$r(y^{(i)}) \geq r_0 > \frac{ r_0 }{ 2 }$

Note

$y^{(1)} \in V_ \alpha_1 $

$B(y^{(1)}, r(y^{(1)})) \leq V_ \alpha_1 $

Is $Y \subset V_ \alpha_1 $

No, by assumption.

$\exists y^{(2)} \in Y \setminus V_ \alpha_1$

$d(y^{(1)}, y^{(2)}) > K, y^{(2)} \in V_ \alpha _2$

Is $Y \subset V_ \alpha_1 \cup \alpha_2 $ ?

No $\exists y^{(3)} \in Y \setminus (V _ \alpha _1 \cup V _ \alpha _2) $

$d(y^{(3)}, y^{(2)}) > K $

$d(y^{(3)}, y^{(1)}) > K $

$y^{(3)} \in V_ \alpha _3 $

Sequence $(y^{(n)})^ \infty _{n = 1} $ in $Y $

$d(y^{(n)}, y^{(m)}) > K > 0 $

So no subseq can converge. HW.

$Y $ is not compact. contradiction.

Theorem

Let $f: [a, b] \to \R $ be a continuous function. Then $f $ attains its max and min in $[a, b]$. max: $\exists c \in [a, b] $ such that $f(c) \geq f(x) , \forall x \in [a, b]$.

Corollary

??????

Let $(X,d)$ be a metric space, and let $K_1, K_2, K_3, …$ be a sequence of non-empty compact subsets of $X$ such that

$$K_1 \subset K_2 \subset K_3 \subset … $$

Then the intersection $\bigcap_{ n=1 }^ \infty K_n $ is non-empty.

Proof 
  </span>
</span>
<span class="proof__expand"><a>[expand]</a></span>

$\forall n$, since $K_n$ is compact, $K_n$ is closed.

First we look at the space $X = K_1$.

Assume on the contrary $\bigcap K_n = \emptyset $.

Take complement $\bigcup_{ n= 1 }^ \infty (X \setminus K_n) = X = \bigcup_{ n= 1 }^ \infty O_n $, which is compact.

We can find $O_{n_1}, O_{n_2}, …, O_{n_k}$ such that

$$\bigcup_{ k= 1 }^ \infty O_{n_k} \subseteq X $$

Notice that $X \setminus K_n = O_n$ is open in $X$.

let $m = \max{ n_1, n_2, …, n_k } $

$O_m = X \setminus X_m = \subseteq X, K_m = \emptyset $.

Theorem

Let $(X,d) $ be a metric space.

  1. $Y \subseteq X$, $Y$ compact, and $Z \subseteq Y$, then $$Z\text{ is compact}\iff Z\text{ is closed}$$

  2. If $Y_1, Y_2, …, Y_n \subseteq X$ are a finite collection of compact subsets $$\bigcup_{ n=0 }^ \infty Y_n\text{ is also compact}$$

  3. Every finite subset of $X$ (including the empty set) is compact.