# Heine-Borel covering property (proof by contradiction)

This is taken from Stein & Shakarchi's Real Analysis, page 3.

"Assume $E$ is compact, $E\subset\bigcup_\alpha \mathcal{O}_\alpha$, and each $\mathcal{O}_\alpha$ is open. Then there are finitely many of the open sets, $\mathcal{O}_{\alpha _1}, \mathcal{O}_{\alpha _2},\cdots, \mathcal{O}_{\alpha_N}$, such that $E\subset\bigcup_{j=1}^N \mathcal{O}_{\alpha_j}$.

I want to prove this by contraction, and I was hoping someone could check my general thought process. I essentially want to show that given the assumptions, that for all finite subcoverings $\mathcal{O}_{\alpha _1}, \mathcal{O}_{\alpha _2},\cdots, \mathcal{O}_{\alpha_N}$ of $\mathcal{O}_{\alpha}$, that $E$ is not a subset of $\bigcup_{j=1}^N \mathcal{O}_{\alpha_j}$. So from $E\subset\bigcup_\alpha \mathcal{O}_\alpha$, we know that for any $x\in E$, $x$ is in some $\mathcal{O}_\alpha$. So let's consider that particular $\mathcal{O}_\alpha$, call it $\mathcal{O}_{\alpha_x}$, and assume there is not any finite subcovering that contains this x.

Now from here, would I begin to construct a finite subcovering that contains x, thereby showing a contradiction? Thoughts would be greatly appreciated.

-
I'm not sure what you want to prove here. The statement is pretty much the definition of a compact set. – Ayman Hourieh Oct 13 '12 at 22:17
What is your definition of compact? As Ayman says, the property that you’re being asked to prove is the usual definition, so you must be using something different. – Brian M. Scott Oct 13 '12 at 22:19
In the book, a set $E$ is compact if it is bounded (contained in some ball of finite radius) and closed. – madisonfly Oct 13 '12 at 22:20
Are you working in $\Bbb R$, or more generally in $\Bbb R^n$ for arbitrary $n$? – Brian M. Scott Oct 13 '12 at 22:26
I'm working in $\mathbb{R}^n$, but I've been trying to figure out a proof for $\mathbb{R}$, in the hopes of generalizing to $\mathbb{R}^n$. – madisonfly Oct 14 '12 at 0:43

One approach, perhaps the easiest if you already have the right tools, uses the fact that $$\mathscr{B}_m=\{B(x,r):x\in\Bbb Q^m\text{ and }0<r\in\Bbb Q\}$$ is a base of the topology of $\Bbb R^m$, meaning simply that every non-empty open set in $\Bbb R^m$ is a union of members of $\mathscr{B}_m$. Let $E\subseteq\Bbb R^m$ be closed and bounded, and let $\mathscr{U}$ be an open cover of $E$. For each $x\in E$ there is some $B_x\in\mathscr{B}_m$ such that $x\in B_x\subseteq U$ for some $U\in\mathscr{U}$. Let $\mathscr{B}_0=\{B_x:x\in E\}$; $\mathscr{B}$ is countable, so $\mathscr{B}_0$ is certainly countable. For each $B\in\mathscr{B}_0$ there is a $U_B\in\mathscr{U}$ such that $B\subseteq U_B$. Let $\mathscr{U}_0=\{U_B:B\in\mathscr{B}_0\}$; then $\mathscr{U}_0$ is a countable subfamily of $\mathscr{U}$ that still covers $E$.

Because $\mathscr{U}_0$ is countable, it is either finite or countably infinite. If it’s finite, we’re done, so assume that it’s countably infinite. Then we can enumerate it as $\mathscr{U}_0=\{U_n:n\in\Bbb N\}$. For $n\in\Bbb N$ let $V_n=\bigcup_{k\le n}U_k$, so that $V_0\subseteq V_1\subseteq V_2\subseteq\ldots\;$, and $E\subseteq\bigcup_{n\in\Bbb N}V_n=\bigcup_{n\in\Bbb N}U_n$. If no finite subset of $\mathscr{U}_0$ covers $E$, then $E\nsubseteq V_n$ for every $n\in\Bbb N$, and therefore for each $n\in\Bbb N$ we can choose a point $x_n\in E\setminus V_n$. Then $\langle x_n:n\in\Bbb N\rangle$ is a sequence in the closed, bounded set $E$. If you’ve already proved that such a sequence must have a convergent subsequence, or even simply that it must have a limit point $p$ (which will in fact be the limit of a convergent subseqence), you get a fairly easy contradiction: on the one hand $p\in E$, since $\{x_n:n\in\Bbb N\}\subseteq E$ and $E$ is closed, and on the other hand $p\in\Bbb R^m\setminus V_n$ for each $n\in\Bbb N$, so $p\notin E$.

Here’s another approach, harder but with fewer prerequisites. I’m going to follow standard topological practice and say that a set $E$ is compact if every open cover of it has a finite subcover; in those terms you’re trying to prove that every closed, bounded subset of $\Bbb R^n$ is compact. One way is to start by proving that every closed interval in $\Bbb R$ is compact. Let $[a,b]$ be a closed interval, and let $\mathscr{U}$ be a cover of $[a,b]$ by open sets. Let $$A=\left\{x\in[a,b]:[a,x]\subseteq\bigcup\mathscr{F}\text{ for some finite }\mathscr{F}\subseteq\mathscr{U}\right\}\;.$$ $A$ is bounded above by $b$, so $c=\sup A$ exists. Show first that $c\in A$, and then show that $c=b$, to conclude that some finite $\mathscr{F}\subseteq\mathscr{U}$ covers $[a,b]$.

Then prove by induction on $n$ that if $I_k$ ($k=1,\dots,n$) are closed intervals in $\Bbb R$, the Cartesian product $\prod_{k=1}^nI_k$ is a compact subset of $\Bbb R^n$. I’ll sketch how to show that $I_1\times I_2$ is compact; you should be able to adapt that argument to get the induction step.

Let $\mathscr{U}$ be an open cover of $[a,b]\times[c,d]$. Fix $x\in[a,b]$, and let $I_x=\{x\}\times[c,d]$. Each $U\in\mathscr{U}$ is a union of open sets of the form $(u,v)\times(w,z)$, so for each $y\in[c,d]$ there is a $U_y\in\mathscr{U}$, and there are $u_y,v_y,w_y,z_y\in\Bbb R$, such that $\langle x,y\rangle\in(u_y,v_y)\times(w_y,z_y)\subseteq U_y$. $\{(w_y,z_y):y\in[c,d]$ is an open cover of $[c,d]$, so there is a finite $Y_x\subseteq[c,d]$ such that $[c,d]\subseteq\bigcup_{y\in Y_x}(w_y,z_y)$. It follows that $$I_x\subseteq\bigcup_{y\in Y_x}\Big((u_y,v_y)\times(w_y,z_y)\Big)\subseteq\bigcup_{y\in Y_x}U_y\;.$$ Now let $J_x=\bigcap_{y\in Y_x}(u_y,v_y)$; $J_x$ is an open interval in $\Bbb R$ containing $x$, and $$I_x\subseteq J_x\times[c,d]\subseteq\bigcup_{y\in Y_x}U_y\;.$$ Finally, $\{J_x:x\in[a,b]$ is an open cover of $[a,b]$, so there is a finite $X\subseteq[a,b]$ such that $$[a,b]\subseteq\bigcup_{x\in X}J_x\;,$$ which implies that $$[a,b]\times[c,d]\subseteq\bigcup_{x\in X}\big(J_x\times[c,d]\big)\subseteq\bigcup_{x\in X}\bigcup_{y\in Y_x}U_y=\bigcup_{y\in Y}U_y\;,$$ where $Y=\bigcup_{x\in X}Y_x$. $Y$ is finite, so $\{U_y:y\in Y\}$ is a finite subset of $\mathscr{U}$ covering $[a,b]\times[c,d]$.

The final step is to show that if $E$ is a closed subset of a compact set $K\subseteq\Bbb R^n$ (e.g, a product of closed intervals), then $E$ is compact. This is easy: if $\mathscr{U}$ is an open cover of $E$, let $\mathscr{V}=\mathscr{U}\cup\{\Bbb R^n\setminus E\}$. Then $\mathscr{V}$ is an open cover of $K$, so there is a finite $\mathscr{V}'\subseteq\mathscr{V}$ covering $K$. From here you should have no trouble finding a finite subfamily of $\mathscr{U}$ covering $E$.

-
Wow, thank you so much for your response! – madisonfly Oct 14 '12 at 20:59
@DJM: You’re very welcome. – Brian M. Scott Oct 14 '12 at 21:46

I'm not sure I'm following your idea, but here's a sketch of an argument for the case that the ambient space is $\mathbb{R}^n$ and the original covering is countable. Say it's $O_0$, $O_1$, $O_2$... Assume there is no finite subcovering (this means that $\{O_n\}$ is infinite). Define $U_n = \bigcup_{i \le n} O_i$ for $n \ge 0$. $U_n$ is the union of a finite subset of the $O_n$, so by assumption it does not cover $E$, which means we can find some $x_n \in E - U_n$. Using the assumptions on $E$, the sequence $x_0, x_1, ...$ has a subsequence with a limit point $x$, and $x$ is in $E - \bigcup U_n$. But $\bigcup U_n = \bigcup O_n$, so $\{O_n\}$ does not cover $E$, and that gives us our contradiction.

As @BrianMScott points out, it is no handicap to assume above that the covering is countable. Because we are in $\mathbb{R}^n$, there is a countable base, and so it's pretty easy to show that any open cover has a countable subcover.

If we want to generalize beyond $\mathbb{R}^n$, this argument should work for any complete separable metric space.

-