# Prove that the set of all binary sequences is uncountable

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?

• 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. – James Nov 26 '15 at 3:40
• If you want to go back to basics, think in terms of Cantor diagonalization. – André Nicolas Nov 26 '15 at 3:42
• Sorry, I should have specified in the question that we have not even talked about cantor diagonalization. – Alex Nov 26 '15 at 3:48
• $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. – James Nov 26 '15 at 15:34
• 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... – James Nov 26 '15 at 15:41

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$
• 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. – Piquito Nov 26 '15 at 16:54
• Not particularly; it was for taking the open interval excluding the integers $0$ and $1$. – Piquito Nov 27 '15 at 9:02