Why is the bit sequences of infinite length not the same size as bit sequences with finite length?

Question

By sequences of fixed size I mean:

say the one with length 1: $$\{ 0,1 \}$$ then length 2: $$\{ 00,01,10,11 \}$$ so let the squence be :

$$F =\{\{0,1\}^k : k \in\mathbb{N}\}$$

Let the sequence with infinite length be:

$$I = \{ \{0,1\}^k : k = |\aleph_0| \}$$

so this is what I am confused about, its very strange to me that $F$ does not contain every bit sequence that $I$ contains because, if we let k go to infinite, then F should contain everything $I$ has. But at the same time we restricted k to be finite, however, as k increases unboundedly it should eventually have all the elements of $I$. I know that is not true for some reason. However, its just counter intuitive for me, what is a precise or rigorous way to make the distinction between these two sets? Are they the same? I suspect either they are the same size or $F$ is larger, but I am unsure how to prove this.

Is the only way to make a distinction of these two is by making a precise bijection of the natural numbers to F and then showing by diagonalization that natural numbers don't bisect to $I$?

What exactly is this bijection of natural number to $F$?

The thing that was confusing me about a candidate bijection (from reals) to $F$ was that, for each finite k, we would have the sequence $0^k$. Like 0, 00, 000, 0000, 0000 etc. If I were to do the bit representation of each natural number that would map a bunch of numbers but would leave these sequences that are similar to another without a pair, right? If I decide to pair say:

• 0 to 0
• 1 to 1
• 2 to 10
• 3 to 11
• 4 to 100
• ... etc

i.e. f maps a real number to its binary number representation. Then this mapping seems to not cover all of $F$, but we already ran out of elements of the natural numbers to map to bit sequences in $F$, therefore, $F$ has to be uncountable. Is that right?

Then if that is right, then the mapping function I defined, what does it actually map to then? Does its range have a special name? Its not all the sequences of fixed length nor of infinite length... cuz thats what $F$ and $I$ are...

Is $F$ countable or not?

Answer 1

Why is it strange? The fact that you can approximate every infinite string by its finite initial segments, doesn't mean that the string is there.

The fact that $\pi$ is the limit of its decimal expansions, all of which are rational, doesn't mean that $\pi$ itself is rational.

The fact that every natural number has only finitely many predecessors doesn't mean that the set of natural numbers itself is finite.

Limits sit "beyond" the approximations. And this is exactly that. I also wrote about this exact issue here, both in my answer and in many comments throughout that page.

---

I should also remark that sequences are indexed with ordinals, not with cardinals, since sequences are in their nature objects of a sequential manner, and ordinals measure "length of a queue" where as cardinals just measure "how large it is". While for the finite case this is the same, for the infinite case it's not the same anymore (there are queues of different lengths of the same cardinality). So writing $\{0,1\}^k$ for all $|k|=\aleph_0$ you actually bite off a lot more than you can chew with finite sequences, since you allow all the countable ordinals. Instead you should probably write $\{0,1\}^\Bbb N$ which is what you have meant, I suppose.

Answer 2

The candidate mapping you present indeed does not cover all for $F$, but a similar idea does cover all of $F$:

$$\begin{array}{c} \cdot 0 \mapsto \emptyset \\ \cdot 1 \mapsto 0, 2 \mapsto 1\\ \cdot 3 \mapsto 00,4 \mapsto 01, 5 \mapsto 10, 6 \mapsto 11\\ \cdots \end{array}$$

Note, howver, that this mapping does not cover every possible infinite sequence, since every member of the image of this map is a finite sequence.

To show that no possible mapping covers all infinite sequences, you do the usual diagonal proof, constructing, from a any specified map, a sequenc3e which cannot be in the image of that map.