Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I think there is some confusion of terminology going on here. What you are calling "uncountable" is what is also known as "countably infinite".


There is no confusion here. The set of infinite strings is not countably infinite, it has cardinality larger than the set of integers.


Why? If your alphabet is [0-9] then it seems like your set is just the integers, and those are countably infinite. This case is even more restricted, where you only have two elements in the alphabet. So where does the continuum come in?


There exists no integer whose representation is an infinite sequence of digits. In other words, "1..." is not an integer, neither is "...1". Even though there is an infinite number of integers, every integer has a finite representation. On the other hand, the set of infinite bitstrings has a trivial bijection to the real numbers in the interval [0, 1) and thus to the real numbers as a whole. This is a key point in Cantor's diagonal argument.


Just to help me out (I don't doubt you, I'm just struggling to work it out) can to tell me what that trivial bijection from the set of infinite bitstrings to [0, 1) is?


I must correct myself a bit: what is trivial here is a surjection from bitstrings to reals, but this is plenty enough to prove that there are strictly more bitstrings than integers. Also, the mapping is to [0, 1] inclusive, as is shown below.

For any bitstring a = a₁a₂a₃a₄…, aᵢ ∈ {0,1}, simply prefix "0." and interpret it as the binary representation of the corresponding real number; in other words, construct the real number 2⁻¹a₁ + 2⁻²a₂ + 2⁻³a₃ + 2⁻⁴a₄ + …

Now, it should be evident that this mapping covers all the reals, but some reals have multiple representations. For instance, both 0.1 and 0.0111… represent the same number. So the function is a surjection. As another example, the bitstring of all ones, 1…, maps to the binary number 0.1… which is famously equal to 1. [1]

[1] https://en.wikipedia.org/wiki/0.999...


That makes me feel better because it is roughly what I had come up with too. Thanks for the reply.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: