0
$\begingroup$

Question: Prove that the set of all infinite binary sequences is uncountable.

Comments: I think that there are a couple of ways of going about this. My first approach was to show that the set of all infinite binary sequences are not finite and they are not denumerable. I then noted that the set of all binary sequences is not finite ( by definition) I then choose to suppose that the set of all binary sequences is denumerable, and find a contradiction. However, I couldn't seem to find a function that would do this. I then scraped this approach. Then I tried to find a bijection from (0,1) to the set of all infinite binary sequences. Again, with no luck. Will either one of the two approaches I did work out?

$\endgroup$
  • 1
    $\begingroup$ Both will work. It turns out that $2^\omega$ the set of binary sequences has the same carnality as $\mathbb{R}$, and hence any interval. If you want an explicit bijection, you can looking at the base 2 expansion of a real, but you run into trouble with trailing $1$s. As for the contradiction approach, if you could find an example of a function enumerating $2^\omega$, then it wouldn't be uncountable, right? The way the argument goes is that you suppose it is denumerable, which means, by definition, that there is a bijection from it to $\mathbb{N}$. Pick such a function and reason about it. $\endgroup$ – James Nov 26 '15 at 3:40
  • 1
    $\begingroup$ If you want to go back to basics, think in terms of Cantor diagonalization. $\endgroup$ – André Nicolas Nov 26 '15 at 3:42
  • $\begingroup$ Sorry, I should have specified in the question that we have not even talked about cantor diagonalization. $\endgroup$ – Alex Nov 26 '15 at 3:48
  • 1
    $\begingroup$ $2^\omega$ is the set of all binary sequences. In set theory $B^A$ denotes the collection of all functions from $A$ to $B$. Also, $\omega$ represents (roughly) the natural numbers, and $2 = \{0,1\}$. Thus $2^\omega$ is the collection of all functions from the natural numbers to $\{0,1\}$ which is precisely the collection of binary sequences. $\endgroup$ – James Nov 26 '15 at 15:34
  • 1
    $\begingroup$ An argument could go something like this: As the set of all binary sequences is clearly infinite, we must show it isn't countable. Suppose we have a function $f:\mathbb{N} \rightarrow 2^\omega$. We must show that this function is not a surjection. That is, we must find a binary sequence not equal to any of $f(0),f(1),f(2),\ldots$. Can you find such a sequence? If you need a hint, remember that, to make the sequence different than $f(0)$ it only needs to be different from $f(0)$ at one place. To make it different than $f(0),f(1)$ you might need two places, for $f(0),f(1),f(2)$ you need 3... $\endgroup$ – James Nov 26 '15 at 15:41
3
$\begingroup$

Take the 1-to-1 function $f$ of the open interval $]0,1[$ in $\mathbb R$ defined by

$f(x)=$ representation of x in the numerical system of base $2$

This is enough.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I don't understand what that function is or what it means. Could you explain? This is just an intro to proofs class, and we have not been introduced to things like this. $\endgroup$ – Alex Nov 26 '15 at 3:54
  • 1
    $\begingroup$ Each number of our decimal system has a unique representation in an arbitrary numerical system (of base distinct of $10$). This fact ensure the function is injective (1-to-1). You determine this way an uncountable subset of your set. $\endgroup$ – Piquito Nov 26 '15 at 16:54
  • $\begingroup$ All right. Is there any reason why you wrote ]0,1[ as compared to [0,1]?Does it mean something different? $\endgroup$ – Alex Nov 26 '15 at 22:35
  • $\begingroup$ Not particularly; it was for taking the open interval excluding the integers $0$ and $1$. $\endgroup$ – Piquito Nov 27 '15 at 9:02
  • 1
    $\begingroup$ You are very welcome. I like much to help students. $\endgroup$ – Piquito Nov 28 '15 at 12:00

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.