3
$\begingroup$

$F=[0,1] \subset \bigcup B_{r_j}(x_j)$ where $\{x_j\}$ is an arbitrary enumeration of rational numbers in $[0,1]$. $[0,1]$ is compact and thus must have a finite cover. $B_{r_j}(x_j)$ is an open ball around $x_j$ with radius $r_j$.

Please show how to "extract" a finite cover from $\bigcup B_{r_j}(x_j)$.

Note that there is no $r>0$ such that $r_j>r$ $\forall j$ .

$\endgroup$
  • 1
    $\begingroup$ @PraphullaKoushik I think OP means that the infimum of $r_j$ may be $0$ $\endgroup$ – MCT Mar 13 '15 at 17:36
  • $\begingroup$ @PraphullaKoushik tried to make it more clear in OP. $\endgroup$ – Sergey Zykov Mar 13 '15 at 17:38
  • $\begingroup$ Oh... Then my previous comment is irrelevant $\endgroup$ – user87543 Mar 13 '15 at 17:43
  • $\begingroup$ I think the proofs at How to prove $[a,b]$ is compact? all work for this special case. $\endgroup$ – MJD Mar 13 '15 at 17:45
  • $\begingroup$ I am not very sure if there is any method to get a finite cover from arbitrary enumeration..... $\endgroup$ – user87543 Mar 13 '15 at 17:48
6
$\begingroup$

Given a countable covering $\{U_1, U_2, \ldots\}$ of a compact space, there is an easy algorithm to find a finite subcover: Check if $\{U_1\}$ is a cover, then check if $\{U_1,U_2\}$ is a cover, and so on. Compactness guarantees that this process will terminate.

It is unlikely that we can do much better than this, at least without further properties of the cover. You've written down a cover by open intervals that is basically arbitrary except that they have rational midpoints.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is what I think as well. Hard to construct a finite cover from an arbitrary one. $\endgroup$ – MCT Mar 13 '15 at 17:49
  • $\begingroup$ It's kind of interesting that this works even if the given covering is uncountable, even though you never consider most of the intervals in the covering. In a sense this shows that every uncountable covering has a countable subcovering. Of course $[0,1]$ is Lindelöf, but I think there's something else going on here. $\endgroup$ – MJD Mar 13 '15 at 21:12
  • $\begingroup$ @MJD How exactly does this work for an uncountable covering? I can't think of how to pass to a countable subcover in any kind of constructive way. $\endgroup$ – Slade Mar 14 '15 at 2:58
  • $\begingroup$ Yes, I was mistaken. user86418 pointed out my error in the comments in my post in this thread. $\endgroup$ – MJD Mar 14 '15 at 15:39
2
$\begingroup$

This is a (possibly) more efficient variation on Slade's algorithm elsewhere in this thread.

  1. Let $x$ be the smallest point not yet covered; initially $x=0$.
  2. Let $S$ be a partial finite subcover, initially $\emptyset$
  3. Let $L$ be a list of the open intervals considered so far, initially $\emptyset$
  4. Repeat until $x>1$:
    • If $L$ contains an interval $(a,b)$ with $x\in (a,b)$ then
      1. Insert $(a,b)$ into $S$
      2. Set $x=b$
    • If not, then read another interval from the open cover and add it to $L$.
  5. $S$ now contains a finite open cover of $[0,1]$ that is a subcover of the given cover.

The test "If $L$ contains..." is finite; it needs only examine the finite list $L$.

The outer repeat loop must terminate because $[0,1]$ is compact.

The algorithm is therefore guaranteed to terminate in finite time if presented with an open cover of $[0,1]$.

There is an obvious optimization: after reading an interval and adding it to $L$, skip the “if $L$ contains an interval…” test unless $x$ is a member of the latest interval.

$\endgroup$
  • $\begingroup$ This looks OK for the OP's covering (which is countable), but for a general covering of $[0,1]$ by open sets (with a well-ordered set indexing open sets in the covering), mightn't the loop fail to terminate even after countably many iterations (if some initial uncountable set of intervals fails to cover $[0,1]$)? (If this seems right, it may have some bearing on your comment to Slade's post....) $\endgroup$ – Andrew D. Hwang Mar 13 '15 at 22:20
  • $\begingroup$ Yes, I think you're right. This was what I was groping for when I wrote the other comment; in such cases Slade's technique doesn't work either. Thanks! $\endgroup$ – MJD Mar 14 '15 at 0:23
  • $\begingroup$ For what it's worth, Slade does explicitly specify a countable covering, and the OP's cover is countable. :) $\endgroup$ – Andrew D. Hwang Mar 14 '15 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.