# Why is there no bijection between the set of all sequences whose elements are the digits $0$ and $1$ and the positive integers? [duplicate]

I have a problem understanding theorem 2.14 of Rudin's Principles of Mathematical Analysis. The theorem is the following:

$$\textbf{Theorem 2.14:}$$ Let $$A$$ be the set of all sequences whose elements are the digits $$0$$ and $$1$$. This set is uncountable. The elements of $$A$$ are sequences like $$1,0,0,1,0,1,1,1,...$$

$$\textbf{Question:}$$ Why there is not a $$1$$-$$1$$ mapping of the set $$A$$ to the set of all the positive integers?

I would think that every positive integer (denoted by $$J$$ by Rudin) can be represented by an element of $$A$$ by using the binary representation. So each number is $$J_n = \sum_{i=0}^\infty s_{ni}2^i$$ where $$s_{ni}$$ is the $$i^\text{th}$$ element of the sequence $$s_n$$ (using zero-based numbering).

Then, if $$A\sim J$$, shouldn't $$A$$ be countable?

Rudin mentions this theorem implies that the set of all real numbers is uncountable, so I understand this sequences actually represent real numbers and not the natural numbers, but why? I know my logic has at least one mistake (likely a huge blunder), but what is it?

• Integers are represented by finite binary sequences or, more precisely, by binary sequences for which all but finitely many entries are $0$.
– lulu
Jun 12, 2020 at 21:58
• I think this question has a similar idea Jun 12, 2020 at 22:00
• Note that proper MathJax usage is not $A$~$J$ but $A\sim J.$ I edited this question accordingly. Jun 12, 2020 at 22:16

What would be the integer corresponding to the sequence $$1,1,1,1,1,1...$$ ?!

• Does that sequence represent a number in the set of real numbers? And, can’t we say that this sequence represents the largest number of the natural numbers? Or is it because this sequence is well defined (differently from the largest element of the natural numbers?
– Ivan
Jun 12, 2020 at 22:30
• there is no largest element of the natural numbers; and this sequence is an element of $A$, which is what I thought your question was about Jun 12, 2020 at 22:37
• @IvanMartinez : The sequence $.010101010101\ldots$ in base $2,$ represents a real number between $0$ and $1.$ It cannot represent a natural number since each of those in binary has only finitely many digits. There is no largest of all natural numbers since you can always add $1$ to any natural number to get a larger one. Jun 13, 2020 at 19:28

[these] sequences actually represent real numbers and not the natural numbers, but why?

Because they are infinitely long sequences, with the sequence $$(s_{n,1}, s_{n,2}, s_{n,3}, \ldots)$$ corresponding to the number $$\sum_{i=0}^\infty s_{ni}2^{-i}$$ (note the minus sign in the exponent).

The set of all natural numbers can be placed in one-to-one correspondence with the set of all sequences of $$0\text{s}$$ and $$1\text{s}$$ in which there are only finitely many $$1\text{s}.$$ But the set that Rudin considers is not restricted to those containing only finitely many $$1\text{s}.$$

The non-existence of a one-to-one correspondence between this set and the set of all positive integers can be shown as follows. Suppose $$s_{n,i}$$ is the $$i^\text{th}$$ member of the $$n^\text{th}$$ sequence for $$n\in \mathbb N.$$ Then let $$t_i = 1 - s_{ii} \text{ for all } i \in \mathbb N.$$ Then this sequence $$t$$ of $$0\text{s}$$ and $$1\text{s}$$ differs from every sequence corresponding as above to some natural number $$n,$$ because its $$n^\text{th}$$ digit differs from the $$n^\text{th}$$ digit of the $$n^\text{th}$$ sequence.