# Understanding the definition of a compact set

I just need a bit of help clarifying the definition of a compact set.

A set $S$ is called compact if, whenever it is covered by a collection of open sets $\{G\}$, $S$ is also covered by a finite sub-collection $\{H\}$ of $\{G\}$.

Question: Does $\{H\}$ need to be a proper subset of $\{G\}$? If, for instance, $\{G\}$ is already a finite collection, does that mean $S$ is automatically covered by a finite sub-collection of $\{G\}$? Also, is there any need for the open sets in $\{H\}$ to be bounded sets?

-

As with many statements involving nested quantifiers, it may help to think of this in terms of a game. Suppose you are trying to prove that a certain space $G$ is compact. $G$ is compact if, for every open covering $C$ of $G$, there is a finite subcovering. So the game goes like this:

1. You say “$G$ is compact.”

2. Your adversary says “It is not. Here is an open covering $C$.” (The adversary gives you a family of open sets whose union contains $G$.)

3. You reply “Here is a finite subcovering of $C$.” (You reply with a finite subset of $C$ whose union still contains $G$.)

If you succeed in step 3, you win. If you fail, you lose. (If you're trying to prove that $G$ is not compact, you and the adversary exchange roles.)

If the adversary presents a finite open covering $C$ in step 2, you have an easy countermove in step 3: just hand back $C$ itself, and you win!

But to prove that $G$ is compact you also have to be able to find a countermove for any infinite covering $C$ that the adversary gives you.

Must your finite subcovering be a proper subset of $C$? No. If this were required, the adversary would always be able to win in step 2 by handing you a covering $C$ with only a single element, $C=\{ G \}$. Then the only proper subset you could hand back would be $\lbrace\mathstrut\rbrace$, which is not a covering of $G$, and therefore the would be no nonempty compact sets. That would be silly, so you have to be allowed to hand back $C$ unchanged in step 3.

-
+1: Never seen a game approach to quantifying statements. I like it! –  Cameron Buie Jun 20 '12 at 2:10
I didn't invent this. Wikipedia has an article (although it isn't very good). And the idea is crucial to understanding why the strategies of so many games are PSPACE-complete. This is because the central PSPACE-complete problem, analogous to SAT for NP-complete problems, is the satisfiability problem for quantified boolean formulas, and asserting that P1 wins some game can be understood as claiming that there exists a P1 move such that for all P2 moves there exists a P1 move… etc. –  MJD Jun 20 '12 at 2:27
Great explanation, Mark! Thank you very much. –  Sakif Khan Jun 20 '12 at 23:18
@CameronBuie I forgot to ping you on the reply above. –  MJD Jun 21 '12 at 13:48
It's okay. Since it was posted right after mine, it pinged me by default. –  Cameron Buie Jun 21 '12 at 15:36

Does $\{H\}$ need to be a proper sub-collection? No. If $\{G\}$ is finite to start with, then $\{G\}$ is a perfectly fine sub-collection. As an example, cover $[0,1]$ by $\{G\}=\{(-1,3/4),(1/2,2)\}$. If $\{G\}$ is infinite, then the sub-collection $\{H\}$ must be a proper subset due to its finiteness.

The open sets in $\{H\}$ do not need to be bounded. For instance, we could cover the interval $[0,\infty)$ by $$\{G\} = \{ (a,\infty) : a \in \mathbb{R} \}$$

An obvious finite sub-cover is given by $$\{H\} = \{ (-1,\infty) \}$$

However, $[0,\infty)$ is not compact since there is an open cover which has no finite sub-cover:

$$\{G\} = \{ (a,a+2) : a \in \mathbb{R} \}$$

-
That clears up quite a few things for me. Thanks! –  Sakif Khan Jun 20 '12 at 23:19