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

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?

• This argument works only if there are finitely many $x_i$'s which are $1$, otherwise your $f(x)$ wouldn't be well-defined. Your argument shows that the subset $X$ of $\{0,1\}^\omega$, the elements of which have finitely many $1$s and rest $0$s, is countable. Dec 20, 2021 at 20:11
• Which positive integer corresponds to the sequence $(1,1,1,1,1,\ldots)$? Dec 20, 2021 at 20:11
• Infinite binary expressions correspond to $2$-adic integers. The sequence of all $1$s corresponds to the $2$-adic integer $-1$. Other nonzero $2$-adic integers exist that are neither positive nor negative integers (but are rational), such as the $2$-adic integer $...101010=-\frac{2}{3}$, and there are also others that are not even rational, such as the $2$-adic integer $...10001010110$ (with $1$s at prime positions counting from right to left and $0$s elsewhere). Dec 20, 2021 at 20:26
• Although @Jacob's answer explains your mistake, your strategy can biject $\{0,\,1\}^\omega$ with a supernatural generalization of squarefree numbers.
– J.G.
Dec 20, 2021 at 21:06
• Also, the uncountability of $\{0,1\}^\omega$ does not use the axiom of choice! Dec 20, 2021 at 22:59

$$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}^+$$.