If the set of finite binary strings is enumerable, why isn't the set of infinite binary strings countable?

358 Views Asked by At

It can be shown that the set of binary strings is countable by enumerating the natural numbers through the combinatorial possibilities, using this pattern. Why can't the same argument be used to show that an infinite binary sequence is countable? The tree I have made along with the enumeration drawing corresponds to {},{0},{1},{0,0},{0,1},{1,0},{1,1}...

An answer I saw to a similar question here stated that this would only enumerate through the finite sets of binary strings but not the infinite sets, but I fail to see why this doesn't reach the "infinite" binary strings, since this sequence could go on forever.

enter image description here

1

There are 1 best solutions below

0
On

This method will cover all finite strings .. of which there are infinitely many ... and yet any infinite length string never occurs in this tree.