Bijection between $\{0,1\}^\omega$ and the set of positive integers

binarycardinalsintegerssequences-and-seriesset-theory

I have studied the first sections of "Munkres, J.R., Topology". In section 7 I find a theorem (7.7) that states that the set $\{0,1\}^\omega$ ($=\{0,1\}\times\{0,1\}\times\cdots$), i.e., the set of $\omega$-tuples or (infinite) sequences of elements of $\{0,1\}$ is uncountable. I have studied the proof, I understand it, I know that this proof uses implicitely the Axiom of Choice (this theorem is the answer to Exercise 4 of section 9 of this book), and it is OK for me…

Nevertheless, I feel that $\{0,1\}^\omega$ should be countable because I think that there is a bijection between $\{0,1\}^\omega$ and $\mathbb{Z}_+$ (the positive integers). And I would like someone to point me where I am wrong:

Let $x=(x_1,x_2,\ldots)$ be an element of $\{0,1\}^\omega$, so $x_i=0\text{ or }1$ for every $i$ in $\{1,2,\ldots\}$, I define $f(x)=1+1x_1+2 x_2+4x_3+\cdots+2^{i-1}x_i+\cdots\in\mathbb{Z}_+$, i.e., I consider $x$ the reversed binary expression of $f(x)-1$. Then there corresponds one and only one positive integer to every $x$ and vice versa. Thus, there exists a bijection between $\{0,1\}^\omega$ and $\mathbb{Z}_+$, so $\{0,1\}^\omega$ is countable.

Am I wrong? Where? Why?

Best Answer

$f(x)$ is defined only when $x$ has a finite number of $1$s. Indeed, the set $$\bigcup_{n=1}^\infty\{0,1\}^n\times \{0\}^\omega=\{x\in \{0,1\}^\omega: x_i=0\text{ for } i\text{ sufficiently large}\}$$ is countable with $f$ as a bijection to $\mathbb{Z}^+$. However, you'll notice that when $x$ has infinitely many $1$s, then $f(x)=\infty \not\in \mathbb{Z}^+$.

Related Question