Does $\forall n\in \mathbb N: |A_n| \geq 2^n =|\{0,1\}^n|$ imply that $\underset {n\to \infty} \lim |A_i| \geq |\{0,1\}^\mathbb N|$

This is a lemma I would need to get around some confusing Nested Intervals in a proof of Cantor-Staub, but I am not sure if it is correct. (I know I should just learn nested intervals, but I'm told good mathematicians are also lazy so...)

I went over this again, and I realised, there is some context missing:

$A_0 := [0, 1]$

$A_1 := [0, 1/3] \cap[2/3, 1]$

$A_2 := [0, 1/9] \cap[2/9, 3/9] \cap [6/9, 7/9] \cap[8/9, 1]$

And so forth, each step cutting out a third of the largest continuous sub-intervals.

Now trying to show that $\bigcap_{i =0}^\infty A_i = |\{0,1\}^\mathbb N|$.

  • Now as $\mathbb R$ is compact we know that $|[a,b]| \geq 1$ for $a\leq b$ call it $(i)$
  • $\bigcap_{i=1}^n A_i = A_n$, as $\forall n \in \mathbb N:A_{n+1} \subset A_{n}$, so $\bigcap_{i=0}^\infty A_i = \underset {n\to \infty} \lim \bigcap_{i=0}^n A_i = \underset {n\to \infty} \lim A_n$
  • Per $(i)$ it holds that $A_n \geq 2^n =|\{0,1\}^n|$, the number of biggest continuous intervals in $A_i$ doubles in every step ($i\to i+1$) .
  • Now the question is, does this "invariant" persist in the limit, such that $\underset {n\to \infty} \lim A_n \geq \underset {n\to \infty} \lim|\{0,1\}^n|$?

Intuitively I would say yes, but this is very dangerous territory, as $\underset {n\to \infty} \lim 2^n$ is not properly defined...

  • 2
    $\begingroup$ What if for some $k$ for all $n\geq k$ we have $|A_n|=|\mathbb N|$? $\endgroup$
    – amrsa
    Commented May 15 at 14:19
  • 4
    $\begingroup$ For example, if $A_n=\mathbb N$, then $|A_n|\geq 2^n$, but $\lim|A_n|=|\mathbb N|<|\{0,1\}^{\mathbb N}|$. $\endgroup$
    – amrsa
    Commented May 15 at 14:21
  • $\begingroup$ Thanks @amrsa You just answered my question. Thanks. (I feel a little ashamed that I didn't figure it out myself...). Is there some way to equate the growth of a set to the growth of a binary string? Say if $|A_n| = \Omega(2^n)$, i.e. $|A_n|$ grows at least as fast as $2^n$. I can see how this is not helpful notation, as this kind of calculus with infinity doesn't really work... $\endgroup$ Commented May 15 at 14:51
  • 1
    $\begingroup$ Your set theory notation looks off to me. You write for example $$A_0 := \{[0,1]\}$$ This means that $A_0$ is a set of cardinality $1$, having a unique element (namely the set $[0,1]$). Similarly $A_1$ is a set of cardinality $1$, having a unique element (namely the set $[0,1/3] \cup [2/3,1]$). I suspect this is not what you intended, I suspect instead that you intended $A_0 = [0,1]$, $A_1 = [0,1/3] \cup [2/3,1]$, and so on. As currently written, $A_0$ and $A_1$ have no object in common, so $A_0 \cap A_1 = \emptyset$, hence $\bigcap_{i=0}^\infty A_i = \emptyset$. $\endgroup$
    – Lee Mosher
    Commented May 15 at 14:51
  • $\begingroup$ Thanks for noticing @LeeMosher, you are of course right. I adjusted it $\endgroup$ Commented May 15 at 14:54

1 Answer 1


Thanks to @amrsa's comment I have the answer before I could even type out my question properly ^^ For $\forall n:A_n = \mathbb N$ we have $|A_n| \geq 2^n$ but $\lim |A_n| = |\mathbb N| < |\{0,1\}^{\mathbb N}|$

So, the answer is no.

The intuition is of course correct, and the theorem is also correct, but one wants to solve this using an injective function (as we usually do when proving some set is at least as big as the Reals):

The invariant is not the size of the set, but the existence of an injective function from $\{0,1\}^n$ to $A_n$, and therefore it stays greater than or equal. Now I am not sure if this is allowed in the limit.

So what is allowed is to use the binary representation of a real number in $[0,1]$ (we already know that $[0,1] \simeq \mathbb R$:

$$b := \sum_{i=1}^\infty b_i 2^{-i} \in [0,1], \forall i : b_i \in \{0,1\}$$ And then we show that there is a unique point in $A_\infty$ that corresponds to it. This is the classical nested intervals method: We divide an interval into 3, so we have a unique way to distribute 2 possible values. So e.g. 0.000110... could correspond to lllrrl... etc.

Therefore we have a bijection that is invariant under limits. This is probably the easiest way to do it... but do correct me if I'm wrong...


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .