0
$\begingroup$

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?

$\endgroup$
6
  • 4
    $\begingroup$ 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. $\endgroup$ Dec 20, 2021 at 20:11
  • 1
    $\begingroup$ Which positive integer corresponds to the sequence $(1,1,1,1,1,\ldots)$? $\endgroup$
    – timon92
    Dec 20, 2021 at 20:11
  • $\begingroup$ 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). $\endgroup$ Dec 20, 2021 at 20:26
  • $\begingroup$ Although @Jacob's answer explains your mistake, your strategy can biject $\{0,\,1\}^\omega$ with a supernatural generalization of squarefree numbers. $\endgroup$
    – J.G.
    Dec 20, 2021 at 21:06
  • $\begingroup$ Also, the uncountability of $\{0,1\}^\omega$ does not use the axiom of choice! $\endgroup$ Dec 20, 2021 at 22:59

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you, Jacob. Your answer is perfect to me. $\endgroup$ Dec 21, 2021 at 11:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .