5 ms·
> String is a possibly infinitely long ordered list of fixed-size characters, in which case it is countably finite. BitSequence, as defined in the blogpost, is
by pedrosorio 8y ago
> String is a possibly infinitely long ordered list of fixed-size characters, in which case it is countably finite.
BitSequence, as defined in the blogpost, is an "infinitely long ordered list of fixed-size characters" (where the size is 1 bit in this case) - the set of all BitSequence values is infinite - and uncountable.
By the same logic, the set of infinite strings is also uncountable (as the GP says, it's trivial to do an injection from BitSequence to infinite strings, so it can't have lower cardinality).
- saagarjha 8y agoYes, you're right. I have amended my comment; I had meant to say that Strings must have finite length. The "meat" of my comment was an argument that Strings could not infinitely long, which was exactly the opposite of what I actually ended up saying ;)
- hawkice 8y agoIt's not uncountable because they have to be computable, which makes them countable again.
- nicky0 8y agoI think there is some confusion of terminology going on here. What you are calling "uncountable" is what is also known as "countably infinite".
- pedrosorio 8y agoThere is no confusion here. The set of infinite strings is not countably infinite, it has cardinality larger than the set of integers.
- brianpgordon 8y agoWhy? 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?
- Sharlin 8y agoThere 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.
- nicky0 8y agoJust 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?
- Sharlin 8y agoI 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.. https://en.wikipedia.org/wiki/0.999...
- nicky0 8y agoThat makes me feel better because it is roughly what I had come up with too. Thanks for the reply.