I was working on this problem for class

B is the set of all infinite binary strings. Show B is uncountable.

The given answer uses a diagonal argument similar to the Cantor proof, however that wasn't my first thought.

I first thought to do the following:

Index every digit in a binary string $1,2,3,...$. The number of digits in a particular string is $\mathbb{N}$, and since each digit can earlier be a $0,1$ we have that our set contains $$ 2^{|\mathbb{N}|} $$ Strings, which is the same as the cardinality of the continuum. Therefore, B is uncountable.

Is this sufficient? I'm not sure how infinite cardinalities hold up to operations like that.

  • $\begingroup$ That is perfect, just worded a bit weirdly. What you want to say is that infinite binary strings can be enumerated by the naturals, and at each position, we can have a $0$ or $1$. That means that there is an obvious bijection between the set of binary strings and the set of functions from $\mathbb N\to\{0,1\}$. However, the cardinality of the latter is $2^\mathbb N$, which is known to be uncountable. $\endgroup$ – Don Thousand Nov 9 '19 at 17:23
  • $\begingroup$ Another variant of this same idea is to enumerate the positions in the binary string with the naturals, and then consider the subset of all naturals where the digit in that place is $0$. Note that for any subset of the naturals, there exists a binary string that outputs the subset via this process. That means that there is a surjection from the set of binary strings to the powerset of $\mathbb N$, which is clearly uncoutanble. $\endgroup$ – Don Thousand Nov 9 '19 at 17:24
  • $\begingroup$ To me, this sounds like you are "reducing" the question to the same question. $\endgroup$ – Michael Nov 9 '19 at 17:29
  • 1
    $\begingroup$ @Michael To me, it looks more like translating the problem to a very similar problem that they have already solved. Infinite binary strings and subsets of $\Bbb N$ and real numbers in $[0,1)$ aren't quite the same, after all. $\endgroup$ – Arthur Nov 9 '19 at 17:33
  • $\begingroup$ @Arthur I agree. Understanding how to construct bijections may be seen as trivial, but for a first encounter, it's quite important. After all, this was quite non-obvious when it was first introduced. $\endgroup$ – Don Thousand Nov 9 '19 at 17:38

If you already know that $2^{\Bbb N}$ is uncountable, then what you have there is enough. As you have shown that there is an injection $2^{\Bbb N}\to B$, which implies $$ \left\lvert2^{\Bbb N}\right\rvert\leq |B| $$


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.