2

It seems we can cover each rational in (0,1) by a set of open intervals of decreasing lenghts whose sum is arbitrarily small. So it looks like there are a lot of holes. But on the other side, rationals are dense on (0,1)... Does it mean the original covering would cover the whole (0,1)?

Some assumption must be wrong...

Thanks in advance

Edit: following the example on pi/4. Using its decimal expansion. I am covering any finite decimal expansion on this particular number with an open interval. Each rational on the set of decimal expansions of this particular number has an interval of a given lenght. I can only imagine that the lenght of these intervals (the lenght is a function of the position inside the set of rationals) get too small leaving zeros in the decimal expansion. But this situation must happen no matter what is the base you use for the "decimal" expansion...

Edit 2: I list all rationals in interval (0,1). The first got an open interval of epsilon/2. The second of epsilon/4. The third,... How can I show the diagonal element is not covered by the open intervals linked to all rationals?

Eduard
  • 304
  • As you surmise, there are many reals not contained in the union of the covering sets. – lulu May 30 '20 at 18:13
  • The problem in the visualization here is that the "holes" are just (irrational) points. Since the irrational numbers are "much more" that the rational ones, then you are leaving out a lot – Exodd May 30 '20 at 18:23
  • take for example the open intervals $(\pi/4, x)$ and $(y,\pi/4)$ for every $x>\pi/4>y$. They cover every rational, but not $\pi/4$. Something similar is happening here, but with a lot of irrational numbers not covered – Exodd May 30 '20 at 18:25
  • @Exodd: Well, the similarity is limited with respect to what the OP is wondering about. The point of the question is that the measure of the covering set can be made arbitrarily small, whereas in your case it has full measure and only $\frac\pi4$ is missing. – joriki May 30 '20 at 18:51
  • @Exodd: even with pi/4. I have a rational as close as I want to this number with an open interval surrounding it. Are you sure pi/4 is not included in the interval? – Eduard May 30 '20 at 19:33
  • @Exodd: or in other words, can you construct a real number that for sure it is not in an epsilon covering? – Eduard May 30 '20 at 19:55
  • 1
    @Exodd ... "Can you construct a real number that for sure it is not in an epsilon covering?" Given a constructive description of the covering, yes. It is called Cantor's diagonal argument. – GEdgar May 30 '20 at 19:59
  • 1
    Consider a cover not containing $\pi/4$. What does that mean about the cover? It means that the length of the interval centered at any given rational $q$ must be at most $2|q-\pi/4|$. So for example the interval centered at $0.7$ needs to be of length less than $0.16\dots$, the interval centered at $0.78$ needs to be of length less than $0.01\dots$, etc. But this is possible, because the sequence of lengths and the sequence of rationals are selected independently. – Ian May 30 '20 at 20:14
  • @Ian: I am not asking for a particular that is able to not cover pi/4. I am asking why any rational cover cannot cover all reals in (0,1). If posible a construtive way like a diagonal argument. – Eduard May 30 '20 at 20:18
  • 1
    Well first you need to assume something about the lengths. For instance if you assume that the length of $I_n,n=1,2,\dots$ is $2^{-n-1}$ then I think you might be able to do an explicit diagonal argument with the binary expansion. – Ian May 30 '20 at 20:18
  • I don't know how to construct an omitted real from the ogeneral construction, but the fact that it can't cover the reals is because the sum of the lengths of all the intervals in the cover is epsilon, so the measure of their union is at most epsilon, so the cover can not include the whole unit interval. It might be easier to construct a specific missing real if you took a systematic ordering of the rationals rather than an arbitrary one, but I'm not really sure about that. – Ned May 30 '20 at 20:26
  • 1
    I don't think this explicit calculation will be very illuminating, though. The point is that the a given real number $x$ can be missing if the interval in the cover centered around every rational $q$ has length less than $2|x-q|$, which is entirely possible, especially if the lengths go to zero fast enough. – Ian May 30 '20 at 20:27
  • I used to think the problem with rationals were in the tail of its decimal expansion. There are a whole infinite randomness waiting to be added at the "end" of any rational. I was wondering that adding an open interval to the rational the problem would be gone. The rational is able to cover its tail with any posible random ending. It seems at the end, these tail coverings are not long enough to cover enough body. – Eduard May 30 '20 at 22:10
  • Does considering open intervals make this too easy ? What about covering the closed interval $[0, 1]$ by decreasing closed intervals length $\epsilon/2^n$ ? – Tom Collinge Jan 05 '23 at 08:10

1 Answers1

4

In my opinion this is significantly harder to do "fully explicitly" than one might hope. This is an informal point of course,$^1$ but the difficulty essentially comes from the following. Suppose I have a family of open intervals whose diameters sum to $4\over 5$ and I tell you that the first of these intervals is $({1\over 4}, {3\over 4})$. Intuitively, we don't have enough remaining length to cover both of the remaining "sides" $[0,{1\over 4}]$ and $[{3\over 4}, 1]$, but we do have enough to cover either one of them. So right now we don't know which side to look on for an omitted point - we have to enumerate more elements of our putative cover until we've "used up" enough length, and this could take a while.

The intuitively-simplest diagonal constructions don't have this "delay" feature, and so getting this argument right is actually a bit messier than one might expect. We can either use a significantly messier argument, which is reasonably explicit but annoying, or go to a snappier-but-more-abstract.


My personal favorite approach is a kind of middle ground.

  • Show that no finite cover of a closed interval by open intervals can have a sum-of-diameters less than the length (in the obvious sense) of that closed interval. This is a nice induction exercise:

Clearly the result holds for covers with just one open interval. So suppose it holds for covers with $\le n$ open intervals, and $U_1,...,U_n,U_{n+1}$ are open intervals which together cover $[a,b]$. One of them contains $b$; WLOG, $b\in U_{n+1}$. Pick some $x\in U_{n+1}\cap \bigcup_{1\le i\le n}U_i$, and consider the sub-intervals $[a,x]$ and $[x,b]$ and their respective covers $\{U_1,...,U_n\}$ and $\{U_{n+1}\}$ ... Note that $(x-a)+(b-x)=b-a$.

  • Now suppose $\mathcal{U}$ is a (possibly infinite) family of open intervals. We want to show that either $\mathcal{U}$ does not cover $[0,1]$, or "$\mathcal{U}$ has lots of length" - specifically, there are some finitely many $U_1,...,U_n\in\mathcal{U}$ whose sum of diameters is $\ge 1$.

  • Say that an interval $[a,b]\subseteq [0,1]$ is good iff it is not covered by any finitely many elements of $\mathcal{U}$. By definition, if $[0,1]$ is good then we're done.

  • OK, so now assume $[0,1]$ is not good - this is the situation you're describing. Since the union of two finite sets is finite, whenever we cut a good interval in half one of the two halves must also be good, so by "repeated halving" we can recursively build a decreasing sequence of closed intervals $[a_1,b_1]\supset [a_2,b_2]\supset [a_3,b_3]\supset ...$ such that each $[a_i,b_i]$ is good and $b_i-a_i=2^{-i}$.

  • But then $\bigcap_{i\in\mathbb{N}}[a_i,b_i]$ is a singleton $\{x\}$. Can you show that $x$ is not in fact covered by $\mathcal{U}$?

If $x\in\bigcup \mathcal{U}$, then $x\in U$ for some $U\in\mathcal{U}$. But then we can find some $N$ large enough so that $[x-2^{-N}, x+2^{-N}]\subseteq U$. But then $[a_N,b_N]\subseteq U$, contradicting the goodness of $[a_N,b_N]$.

In terms of "unwinding" to get an explicit construction, the "which half of this good interval is also good?" is hiding the "wait and see when we run out of length" issue above.

As an aside, note that this argument doesn't involve the assumption that the cover $\mathcal{U}$ is countable! It's also not a proof by contradiction: we didn't start out by assuming that $\mathcal{U}$ was in fact a cover of $[0,1]$, we showed a general property of any collection of open sets (namely that either they have a finite subcollection whose sum of diameters is $\ge 1$ or they fail to cover $[0,1]$).


$^1$Actually, it's less informal than it may look! We cannot be as "simple and explicit" as one might hope: in technical language, there is a computable family of open sets whose diameters sum to $<1$ but which cover every computable point in $[0,1]$. This is an "analytical" consequence of the "combinatorial" fact that while every infinite finitely-branching tree has an infinite path, we can whip up an infinite computable subtree of $2^{<\mathbb{N}}$ (that is, a tree of finite binary sequences) with no computable path.

This is in contrast with Cantor's diagonal argument, which is in fact appropriately computable. So there really is a fundamental complexity present in "length-counting" arguments like the above which is not present in "bare" diagonalization.

Noah Schweber
  • 245,398
  • Thanks a lot! I think I understand the proof that any covering (in particular my countable one based on rational ordering) that want to cover [0,1] needs a finite subset whose sum is >=1. Crearly not in my case. Regarding the lack of explicitness not sure if it applies to my question. I would need to read carefully the pointers you give me about computable points and trees and branches,... I would require me some more time to figure out. – Eduard May 30 '20 at 22:59
  • @Eduard Well, in your example what do you mean by "the diagonal element"? – Noah Schweber May 30 '20 at 23:00
  • I wanted to say the element that you construct using the diagonal argument. Like changing 0 by 1 and 1 by 0 in the diagonal element when listing all binary sequences... – Eduard May 30 '20 at 23:12
  • @Eduard Using the diagonal argument in what way? The standard input to the diagonal argument is a sequence of sequences of zeroes and ones; the input here is a sequene of open intervals. What exactly is the thing you're constructing? – Noah Schweber May 30 '20 at 23:16
  • That's the problem. I was not able to use the diagonal argument. I was wondering if there was a clever way of writing the list that makes it easy to construct the counterexample. – Eduard May 31 '20 at 08:32
  • Probably the visualization of reals as a complete binary tree (each particular real is a single path on this tree) could help. The process of pairing a rational with an open interval is like pruning the tree. At the end this process is only able to prune a countable number of times. Not fast enough and too much to the left. I guess a similar argument holds with other countables sets like computable points. – Eduard May 31 '20 at 08:40
  • As an aside in the binary tree visualization is there a easy way to visualize rationals? The all 0 or all 1 expansions are easy, but I don't see an easy way to visualize the cicles in a tree in terms of algorithm (computable functions of a particular form?) – Eduard May 31 '20 at 08:43
  • Does considering open intervals make this too easy ? What about covering the closed interval $[0, 1]$ by decreasing closed intervals length $\epsilon/2^n$ ? – Tom Collinge Jan 05 '23 at 08:10