Compact Sets

# Set Covers

An open cover, or cover, of a set $$E$$ in metric space $$X$$ is a collection of open sets, denoted $$\{G_\alpha\}$$, whose union covers, or contains, $$E$$.

A subcover of $$\{G_\alpha\}$$ is a subcollection $$\{G_{\alpha_\gamma}\}$$ that still covers $$E$$.

For example,

1. In $$\mathbb{R}$$, we have $$\left[\frac{1}{2}, 1\right)$$ has cover $$\{V_n\}_{n = 3}^{\infty}$$ where $$V_n = \left(\frac{1}{n}, 1 - \frac{1}{n}\right)$$. It also has cover $$\{(0, 2)\}$$. It also has cover $$\{W_x\}_{x \in \left(\frac{1}{2}, 1\right)}$$, where $$W_x = N_\frac{1}{10}(x)$$. $$\{V_n\}_{n = 3}^{\infty}$$ has subcovers $$\{V_n\}_{n = 22}^{\infty}$$ and $$\{V_n\}_{n = 1000000}^{\infty}$$. $$\{(0, 2)\}$$ has only one subcover $$\{(0, 2)\}$$. $$\{W_x\}_{x \in \left(\frac{1}{2}, 1\right)}$$ has a subcover $$\left\{W_\frac{5}{10}, W_\frac{6}{10}, W_\frac{7}{10}, W_\frac{8}{10}, W_\frac{8}{10}, W_\frac{9}{10}\right\}$$.
2. $$[0, 1] \in \mathbb{R}$$ has a cover by $$\{V_n\} \cup \{W_0, W_1\}$$. A finite subcover is $$\{W_0, W_1, V_{11}\}$$.

# Compact Sets

A set $$K$$ is compact (in $$X$$) if every open cover of $$K$$ contains a finite subcover.

So, $$K$$ is not compact means there exists an open cover of $$K$$ with no finite subcover.

For example,

1. $$\left[\frac{1}{2}, 1\right)$$ is not compact (see $$\{V_n\}$$).
2. $$\mathbb{Z}$$ in $$\mathbb{R}$$ is not compact. One witness cover is $$\{U_i\}_{i \in \mathbb{Z}}$$, where $$U_i = \left(i - \frac{1}{10}, i + \frac{1}{10}\right)$$.

Theorem. Finite sets are compact.

Proof. Consider some open cover $$\{G_\alpha\}$$ covering $$x_1, x_2, \dots, x_n$$. For all $$x_i$$, choose $$G_{\alpha_i}$$. Then $$\{G_{\alpha_i}\}_{i = 1}^n$$ covers the set. QED.

A set $$K$$ is bounded if there is some ball $$N_r(x)$$ for some $$x \in X$$ such that $$K \subset N_r(x)$$.

Theorem. Compact sets are bounded.

Proof. Consider a compact set $$K$$. Let $$B(x) = N_1(x)$$, i.e. $$B(x)$$ are balls of radius $$1$$. Consider a collection $$\{B(x)\}_{x \in K}$$, which is an open cover of $$K$$. By compactness of $$K$$, there exists a finite subcover $$\{B(x_i)\}_{i = 1}^n$$. Let $$R = max_{1 \leq i \leq n}\{d(x_1, x_i)\}$$; this maximum exists because the set $$\{x_1, \dots, x_n\}$$ is finite. Then $$N_{R + 2}(x_1)$$ contains all of $$K$$. QED.

# Relative Open Sets

If $$Y \subset X$$, where $$X$$ is a metric space, $$Y$$ is said to inherit a metric from $$X$$.

A set $$U$$ is open in $$Y$$ (or open relative to $$Y$$) if every point of $$U$$ is an interior point of $$U$$. Here, the notion of interior is using the neighborhoods in $$Y$$.

Theorem. Suppose $$E \subset Y \subset X$$. Then $$E$$ is open in $$Y$$ if and only if $$E = Y \cap G$$ for some $$G$$ open in $$X$$.

# Compactness is Intrinsic

Theorem. Suppose $$K \subset Y \subset X$$, where $$X$$ is a metric space. Then $$K$$ is compact in $$Y$$ if and only if $$K$$ is compact in $$X$$.

Proof.

($$\Rightarrow$$): Assume $$K$$ is compact in $$Y$$. Consider any open cover $$\{U_\alpha\}$$ of $$K$$ in $$X$$. Let $$V_\alpha = U_\alpha \cap Y$$. Then $$\{V_\alpha\}$$ covers $$K$$ in $$Y$$. Since $$K$$ is compact in $$Y$$, there exists a finite subcover $$\{V_{\alpha_1}, \dots, V_{\alpha_n}\}$$ in $$Y$$. Then $$\{U_{\alpha_1}, \dots, U_{\alpha_n}\}$$ is a finite subcover of $$K$$ in $$X$$, as desired.

($$\Leftarrow$$): Assume $$K$$ is compact in $$X$$. Consider any open cover $$\{V_\alpha\}$$ of $$K$$ in $$Y$$. By above theorem, there exists open $$U_\alpha$$ such that $$V_\alpha = U_\alpha \cap Y$$. Then $$\{U_\alpha\}$$ covers $$K$$ in $$X$$. Since $$K$$ is compact in $$X$$, there exists a finite subcover $$\{U_{\alpha_1}, \dots, U_{\alpha_n}\}$$. Then $$\{V_{\alpha_1}, \dots, V_{\alpha_n}\}$$ is a finite subcover of $$K$$ in $$Y$$, as desired. QED.

# Relationship between Compact Sets and Closed Sets

Theorem. Compact sets are closed.

Proof. Let $$K$$ be compact. Consider $$p \notin K$$. We’ll show $$p$$ has a neighborhood that does not intersect $$K$$ (or $$p$$ is not a limit point of $$K$$). For any $$q \in K$$, let $$V_q = N_\frac{r}{2}(q)$$ and $$U_q = N_\frac{r}{2}(p)$$, where $$r = d(p, q)$$. Notice $$\{V_q\}$$ is an open cover of $$K$$. By compactness of $$K$$, there exists a finite subcover $$\{V_{q_1}, \dots, V_{q_n}\}$$. Let $$W = \bigcap_{i = 1}^n U_{q_i}$$. So $$W$$ is an intersection of finitely many open sets. Hence, $$W$$ is open (it is a ball of radius $$\min \left\{\frac{d(p, q_i)}{2}\right\}$$). We have $$W \cap V_{q_i} = \emptyset$$ for all $$q_i$$ because $$W \subset V_{q_i}$$ and $$V_{q_i} \cap U_{q_i} = \emptyset$$. So $$W$$ is the desired neighborhood. QED.

For example,

1. $$(0, 1)$$ in $$\mathbb{R}$$ is not compact because it’s not closed.
2. $$\mathbb{R}$$ in $$\mathbb{R}$$ is not compact although it’s closed because it’s not bounded.

Theorem. A closed subset $$B$$ of a compact set $$K$$ is compact.

Proof. Consider any open cover $$\{U_\alpha\}$$ of $$B$$. Since $$B$$ is closed, $$B^c$$ is open. So $$B^c \cup \{U_\alpha\}$$ is an open cover of $$K$$. Since $$K$$ is compact, there exists a finite subcover $$\{U_{\alpha_1}, \dots, U_{\alpha_n}, B^c\}$$ of $$K$$. Since $$B^c \cap B = \emptyset$$, $$\{U_{\alpha_1}, \dots, U_{\alpha_n}\}$$ covers $$B$$ and it is a finite subcover of the original cover. QED.

Corollary. Suppose set $$B$$ is closed and set $$K$$ is compact. Then $$B \cap K$$ is compact.

Consider intervals $$I_n = [a_n, b_n]$$. They are nested means if $$m > n$$ then $$a_n \leq a_m \leq b_m \leq b_n$$.

Theorem. Nested closed intervals in $$\mathbb{R}$$ are not empty (in $$\mathbb{R}^k$$, nested closed $$k$$-cells are not empty).

Proof. Let $$x = \sup\{a_i\}$$. It exists because $$a_i$$’s are bounded by $$b_1$$. Since $$x$$ is a supremum, $$x \geq a_i$$ for all $$i$$. We have $$x \leq b_i$$ for all $$i$$ since $$b_i$$ is an upper bound of all $$a_i$$’s (due to nestedness). QED.

Aside: Proof that $$\mathbb{R}$$ is uncountable. Suppose $$\mathbb{R}$$ is countable, i.e. $$\mathbb{R} = \{x_1, x_2, x_3, \dots\}$$. Choose closed intervals $$I_1$$ that misses $$x_1$$, $$I_2 \subset I_1$$ that misses $$x_1$$ and $$x_2$$, $$I_3 \subset I_2$$ that misses $$x_1$$, $$x_2$$, and $$x_3$$, and so on. So, $$I_n$$ is a nested closed interval. By previous theorem, there exists a point in $$\bigcap I_n$$ that is not one of the $$x_i$$’s and is thus not on the original listing. QED.

Theorem. Any closed interval $$[a, b]$$ is compact (in $$\mathbb{R}$$). This is also true for $$k$$-cells in $$\mathbb{R}^k$$.

Proof (by contradiction). Suppose there is a closed interval $$[a, b]$$ that is not compact. Then there exists an open cover $$\{U_\alpha\}$$ for $$[a, b]$$ which has no finite subcover. Then $$\{U_\alpha\}$$ covers both $$[a, c_1]$$ and $$[c_1, b]$$, at least one of which has no finite subcover of $$\{U_\alpha\}$$. Without loss of generality, assume $$I_1 = [a, c_1]$$ has no finite subcover. Subdivide $$I_1$$ again using $$c_2$$ which is the half way point of $$a$$ and $$c_1$$. Note that at least one of $$[a, c_2]$$ and $$[c_2, c_1]$$ has no finite subcover. Continue and we’ll obtain $$I_1 \supset I_2 \supset I_3 \supset \dots$$ of nested closed intervals, each halves at each step and has no finite subcover of $$\{U_\alpha\}$$. By the nested interval theorem, there exists $$x \in I_n$$ for all $$n$$. Then $$x$$ is in some $$U_\widehat{\alpha}$$ of the cover $$\{U_\alpha\}$$. Since $$U_\widehat{\alpha}$$ is open, there exists an $$r > 0$$ such that $$N_r(x) \subset U_\widehat{\alpha}$$. Since the intervals halve at each step, some $$I_n$$ is contained in $$N_r(x)$$. This means that $$G_\widehat{\alpha}$$ covers $$I_n$$, which contradicts the fact that it has no finite subcover. QED.

# The Heine-Borel Theorem

Theorem. In $$\mathbb{R}$$ (or in $$\mathbb{R}^n$$), $$K$$ is compact if and only if $$K$$ is both closed and bounded.

Proof.

($$\Rightarrow$$): already done.

($$\Leftarrow$$): (it is not true in arbitrary metric spaces) Since $$K$$ is bounded, $$K \subset [-r, r]$$ for some $$r > 0$$. Since $$K$$ is closed (by assumption) and $$[-r, r]$$ is compact (by the previous theorem), $$K$$ is also compact. QED.

For $$\mathbb{R}^n$$, replace closed interval by $$n$$-cell.

For example,

1. Discrete metric on infinite set $$A$$: $$A$$ is closed and bounded but is not compact.
2. Let $$\mathcal{C}_b(\mathbb{R})$$ is the set of all bounded continuous functions $$f : \mathbb{R} \rightarrow \mathbb{R}$$. Let $$d(f, g) = \sup_{x \in \mathbb{R}}|f(x) - g(x)|$$.

Theorem. $$K$$ is compact if and only if every infinite subset $$E$$ of $$K$$ has a limit point in $$K$$.

Proof.

($$\Rightarrow$$): If no point in $$K$$ is a limit point of $$E$$ then each point $$q \in E$$ has a neighborhood $$V_q$$ containing no other point of $$E$$ other than $$q$$. $$\{V_q\}$$ covers $$E$$ with no finite subcover, implying $$K$$ is not compact, which is a contradiction.

($$\Leftarrow$$) proof for $$\mathbb{R}^n$$ but is true for all metric spaces: Need to show $$K$$ is closed and bounded. Suppose $$K$$ is not bounded. Choose $$x_n$$ such that $$|x_n| > n$$. These have no limit point, which is a contradiction. So $$K$$ is bounded. Suppose $$K$$ is not closed. There exists a point $$p \notin K$$ that is a limit point of $$E$$. Choose $$x_n$$ such that $$d(x_n, z) < \frac{1}{n}$$. $$x_n$$ has a limit point at $$p$$ and no other. QED.

Corollary (Bolzano-Weierstrass Theorem). Every bounded infinite subset of $$\mathbb{R}^n$$ has a limit point in $$\mathbb{R}^n$$.

Proof. If subset $$E$$ is bounded then $$E$$ is in some compact $$k$$-cell. So $$E$$ has a limit point in the $$k$$-cell. QED.

A collection of sets has the finite intersection property if any finite subcollection has a non-empty intersection.

Theorem (due to Cantor). Let $$\{K_\alpha\}$$ be compact subsets of some metric space $$X$$. If $$\{K_\alpha\}$$ has the finite intersection property then the intersection of all $$K_\alpha$$ is non-empty.

Proof (by contradiction). Let $$U_\alpha = K_\alpha^c$$, which is open. Choose an arbitrary $$K$$ from $$\{K_\alpha\}$$. If $$\bigcap\limits_\alpha K_\alpha = \emptyset$$, then $$\{U_\alpha\}$$ covers $$K$$. Since $$K$$ is compact, there exists a finite subcover $$\{U_{\alpha_1}, \dots U_{\alpha_n}\}$$ covering $$K$$. So, $$K \cap K_{\alpha_1} \cap \dots \cap K_{\alpha_n} = \emptyset$$, which constradicts the hypothesis. QED.

Corollary. Let $$\{K_n\}$$ be a sequence of compact nested sets. Then $$\bigcap_{n = 1}^\infty K_n$$ is non-empty.

Theorem. Any space $$X$$ is compact if and only if any collection of closed sets $$\{D_\alpha\}$$ that satisfies the finite intersection property has a non-empty intersection (or, if every finite subcollection has non-empty intersection, then $$\bigcap D_\alpha \neq \emptyset$$).

Proof.

($$\Rightarrow$$): Consider $$\{D_\alpha\}$$. These are closed subset of a compact space $$X$$, so they are compact. Apply the previous theorem to get the conclusion.

($$\Leftarrow$$, by contrapositive): Assume $$X$$ is not compact. Hence, there exists an open cover $$\{U_\alpha\}$$ with no finite subcover. Since $$\{U_\alpha\}$$ is a cover, every point $$y \in X$$ is in $$\bigcup\limits_\alpha U_\alpha$$, which implies every point $$y \in X$$ is not in $$\bigcap\limits_\alpha U_\alpha$$. Hence, $$\bigcap\limits_\alpha U_\alpha = \emptyset$$. Consider any subcollection $$\{U_{\alpha_i}\}_{i = 1}^n$$. Since $$\{U_{\alpha_i}\}_{i = 1}^n$$ is not a subcover of $$X$$, there exists $$x \in X \setminus \bigcup\limits_{i = 1}^n U_{\alpha_i}$$, which implies $$x \in X \cap \bigcap\limits_{i = 1}^n U_{\alpha_i}$$. So $$\bigcap\limits_{i = 1}^n U_{\alpha_i} \neq \emptyset$$, as desired. QED.

# Perfect Sets

A set is perfect if it is closed and every point is a limit point.

For example,

1. Any closed interval $$[a, b]$$ is perfect.
2. $$\mathbb{R}$$ is perfect.

# Cantor Sets

Start with $$K_0 = [0, 1]$$. Construct $$K_1$$ by removing the middle third of $$K_0$$, i.e. $$K_1 = \left[0, \frac{1}{3}\right] \cup \left[\frac{2}{3}, 1\right]$$. Construct $$K_2$$ by removing the middle thirds of the intervals in $$K_1$$, i.e. $$K_2 = \left[0, \frac{1}{9}\right] \cup \left[\frac{2}{9}, \frac{3}{9}\right] \cup \left[\frac{6}{9}, \frac{7}{9}\right] \cup \left[\frac{8}{9}, 1\right]$$. Continue with the construction.

Each $$K_n$$ has $$2^n$$ intervals. Each is closed because each is a finite union of closed sets. Each is compact because each is a closed subset of the compact set $$[0, 1]$$. Finally, all $$K_n$$ are nested. Hence, their intersection is non-empty.

Let $$C = \bigcap\limits_{n = 0}^\infty K_n$$, called the Cantor set. Notice that

• $$C$$ is closed because it is the intersection of arbitrary many closed sets.
• $$C$$ is perfect.
• $$C$$ consists of real numbers whose ternary expansion contains only $$0$$s or $$2$$s, which shows that $$C$$ is uncountable (or $$C$$ has non-endpoints of $$K_n$$).
• $$C$$ has no interior.
• $$C$$ is totally disconnected.
• $$C$$ has measure $$0$$, i.e. for any $$\epsilon > 0$$, $$C$$ can be covered by intervals of total length less than $$\epsilon$$.