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

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.

## marked as duplicate by Andrés E. Caicedo, J.-E. Pin, muaddib, Mostafa Ayaz, abiessuJan 31 '18 at 20:56

• all natural numbers can be represented as a binary number With a finite number of digits. – dxiv Jan 30 '18 at 4:01
• The answer to your question "is there not a one to one mapping fronB to A?" is exactly what you wrote in your first paragraph. – Mariano Suárez-Álvarez Jan 30 '18 at 4:03
• What natural number does the sequence "....010101010" correspond to? – JonathanZ Jan 30 '18 at 4:38
• This seems to be a duplicate, but I don't know which to choose between this one, this closed as a duplicate one, this one, this one and ... – J.-E. Pin Jan 30 '18 at 6:35
• ... this one. – J.-E. Pin Jan 30 '18 at 6:36

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.

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...

Most binary numerals1 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