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

  • 3
    $\begingroup$ Where does the string of "0000..." which goes on infinitely long appear in your order? I think you're conflating "the set of infinite strings" with "the set of all finite strings." $\endgroup$ – Milo Brandt Oct 13 '19 at 2:19
  • 1
    $\begingroup$ When you do a proof by induction, do you ever hit an "infinite" natural number? For the same reason, your construction will never consider an infinite binary string. $\endgroup$ – Nicholas Viggiano Oct 13 '19 at 2:58

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.