If the set of specific sequences of 0's and 1's is countable then it can be used to count the set of all infinite sequences of 0's and 1's. Right?

Question

I am seeking some help to understand why an infinite sequence of $\{0, 1\}$ is uncountable. While there are similar questions here with detailed answers, I wasn't able to resolve the contradiction below:

Given an alphabet $A$ composed of only $0$ and $1$, the set of all possible sequences of alphabet characters of the form $$a_1, a_2, a_3, ..., a_k,$$ where $a_i \in A$, is countably infinite. How is it possible that at the same time the set of infinite sequences of $0$'s and $1$'s is uncountably infinite?

First, let's prove the following:

Given an alphabet $A$ composed of only $0$ and $1$, the set of all possible sequences of alphabet characters of the form $$a_1, a_2, a_3, ..., a_k,$$ where $a_i \in A$, is countably infinite.

Proof 1

The set that is composed of described sequences, including zero-length sequence (an empty sequence), can be denoted as $A^*$. Let's correspond a zero-length sequence with the number $1$. Then all single-character sequences will take numbers from $2$ to $n + 1$, where $n$ is the number of characters in $A$ (which are unique by alphabet's definition). All two-character sequences will take numbers from $n+2$ to $n^2 + n + 1$. All three character sequences are getting numbers from $n^2 + n + 2$ to $n^3 + n^2 + n + 1$. This pattern can be continued infinitely. Therefore, it is possible to enumerate every element of $A^*$. Thus, I conclude that the set $A^*$ is countably infinite since there is a correspondence between $A^*$ and the set of all natural numbers $\mathbb{N}$.

Contradiction

At the same time, the set of infinite sequences of $0$'s and $1$'s (let's call it $T$) is proved to be uncountably infinite (here is a link to Wikipedia with the proof using Cantor's diagonal argument). If proof 1 is correct, then I can make an infinite sequence of zeros and substitute the first $k$ elements of it with any sequence from $A^*$ of the length $k$ which is enumerated. Since $|k| = |\mathbb{N}|$, with this arrangement, it should be correct (but I guess it is not) to state that now every element of $T$ is numbered, hence $T$ is countably infinite.

Reflection

OBVIOUSLY, there is a problem somewhere in my line of thought, but it is hidden from me. My goal is to properly understand why $A^*$ cannot be used to count all the elements of $T$. The answer to this question will also help me to deepen my understanding of Cantor's diagonal argument and explain why it cannot be applied to $\mathbb{N}$.

I sort of understand that Cantor's diagonal method will not work with $A^*$ because it is impossible to construct an argument that is not counted. But on the other hand, if a set of all infinite sequences of $0$'s and $1$'s is said to be infinite, doesn't it mean that any argument one can make must already be in the set?

Any comments are very much appreciated. Thanks!

Answer 1

The problem is when you say

If proof 1 is correct, then I can make an infinite sequence of zeros and substitute the first $k$ elements of it with any sequence from $A^*$ of the length $k$ which is enumerated. Since $|k| = |\mathbb{N}|$, with this arrangement, it should be correct (but I guess it is not) to state that now every element of $T$ is numbered, hence $T$ is countably infinite.

For one sequence you can indeed make a countable number of approximations by finite sequences. By doing that you won't obtain all sequences of $0,1$.

Answer 2

Notice that no finite sequence of $A^*$ corresponds to the infinite sequence $1,0,1,0,1,0,\dots$. So, for this sequence, there is no element of $A^*$ which corresponds to it. That is the problem with your reasoning. Every sequence that has infinitely many ones can´t be obtained from an element of $A^*$.

Answer 3

In Cantor's argument, there are no finite-length strings. You do have them; in fact, if I read it correctly, that's all you use. That's how you get your contradiction.

There is a translation of Cantor actual paper at http://www.logicmuseum.com/cantor/diagarg.htm. He first assumes that he has a list of infinite length strings. He doesn't assume this list is complete, or even that each listed element is different. Just that each element of the list has infinite length.

He then constructs, from that list, an infinite length string a that cannot be in the list. This is actually a lemma that he uses in the second part of the proof.

That's when he assumes that it is possible to make a list of all such strings. The lemma proves that there is a string a that is not in this new list. The assumption of "all" says that a is in the list. This contradiction proves that the assumption is false.