Why is the set of all infinite binary sequences uncountable but the set of all natural numbers are countable?

Question

From Cantor's diagonalization argument, the set B of all infinite binary sequences is uncountable. Yet, the set A of all natural numbers are countable.

Is there not a one-to-one mapping from B to A? It seems all natural numbers can be represented as a binary number (in base 2) and vice versa.

Answer 1

There exists a bijection between infinite binary sequences and $\mathbb{R}$, not $\mathbb{N}$. One way to see this using Cantor's diagonalization argument is to look at a subset $[0,1]$ of $\mathbb{R}$ (which we know is cardinally equivalent to all of $\mathbb{R}$, and represent all $x\in [0,1]$ by their binary decimal expansion.

Answer 2

No. The former has the order of the power set of the latter...

In set theory it is proved that $\lvert P(A)\rvert \gt \lvert A\rvert $ in general.

The power set is defined to be the set of all subsets... To see that we have the power set here, let $n$ be in the subset if there is a $1$ in the $n$-th place; not in the subset if there's a zero...

Answer 3

Most binary numerals¹ do not denote natural numbers — only those binary numerals with repeating zeroes to the left correspond to a natural number.

There is, incidentally, a number system called the 2-adic integers, and there is a bijective correspondence between binary numerals and 2-adic integers.

The 2-adic integers, of course, are uncountable.

_{1: More precisely, left-infinite numerals that terminate in the decimal point. I.e. the numerals whose places are indexed by natural numbers, where the one's place is in index zero, and the indices count to the left}