5 ms·
Nitpicking but I don't think this is quite right: > The BitSequence type holds infinitely many values. In fact, it holds an unconscionable number of values. It
by kccqzy 8y ago
Nitpicking but I don't think this is quite right:
> The BitSequence type holds infinitely many values. In fact, it holds an unconscionable number of values. It has more values than String does.
Assuming UInt is infinite precision and Strings can be infinitely long, there is an easy injection from BitSequence to String, therefore String is at least as equinumerous as BitSequence.
If we bend the definition a bit and allow UInt to be infinite precision (which it is not), there's no reason not to allow String to have infinite length as well.
Also, the article mentioned multiple times how awesomely large the cardinality of BitSequence is. But in fact, the cardinality is the same as that of the real numbers—both have cardinality $2^{\aleph_0}$. So its size is rather intuitively grasped.
- saagarjha 8y agoI think the assumption is that String is a possibly infinitely long ordered list of fixed-size characters, in which case it is countably infinite. Edit: I actually meant "arbitrarily long but finite" instead of "possibly infinitely"; thanks dagw.
- rcthompson 8y agoWe're not talking about the size of single values, we're talking about the cardinality of the set of all distinct values of a given type. I.e. "How many different Strings are there?"
- saagarjha 8y agoYes, I'm aware of that. The set of all languages over a finite alphabet should be countably infinite, since you can list them all. For example, for the alphabet {0, 1} all your strings are just the binary representations of natural numbers, which is countable since ℕ is.
- dagw 8y agoIf you only allow arbitrarily long, but finite, strings then the set is countable. If you allow infinitely long strings then the cardinality of that set is uncountable. For a trivial example consider the string representation of every element in ℝ in the alphabet {0-9,.}
- saagarjha 8y agoYes, you're right; this is what I meant, and I see why my current wording is wrong.
- tomp 8y agoEach string is finite, its characters come from a finite set; that’s countably infinite (think of it as integers written in base Unicode). Bitsequences are infinitely long, so that’s uncountably infinite or continuity (think of it as real numbers between 0 and 1, written in binary).
- rcthompson 8y agoThe point of the original comment was that if you consider BitSequences to be of infinite length, then for consistency you also have to allow infinite-length strings. Otherwise you're ignoring the limitations of machine representation for one type but not the other, which is comparing apples to oranges.
- nicky0 8y ago*infinite?
- saagarjha 8y agoYup, sorry. Fixed.
- 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?
- DougBTX 8y ago> Assuming UInt is infinite precision and Strings can be infinitely long, there is an easy injection from BitSequence to String, therefore String is at least as equinumerous as BitSequence. You’re right that a particular series of bits can be mapped to a string, but here the article is talking about the function that produces the bit sequence not the bit sequence itself. There are an infinite number of functions that can create a particular bit sequence, and each bit sequence can be mapped to a single string, so there must be more functions than strings.
- kccqzy 8y ago> The BitSequence type holds infinitely many values. In fact, it holds an unconscionable number of values. It has more values than String does. In the last sentence, the word "it" seems to refer to "the BitSequence type" and not a function that produces it.
- saagarjha 8y ago> There are an infinite number of functions that can create a particular bit sequence, and each bit sequence can be mapped to a single string, so there must be more functions than strings. I don't think this logic works. For example, there are an infinite number of "rational numbers" of the form np/p where n, p ∈ ℤ, and each of these can be mapped to a single integer (namely, n). But there are not more these "rational numbers" than integers.
- kccqzy 8y agoWhen you have an injection from A to B, you only know that B is at least as equinumerous as A. Maybe their cardinality is the same, and maybe the cardinality of B is strictly bigger. For your example, we can construct an injection from rational numbers to integers, as well as an injection from integers to rational numbers. Therefore, by the Schröder–Bernstein theorem they are equinumerous.
- ulucs 8y agoConsidering cardinalities, functions and strings are equal. Using javascript notation, ‘fn => fn.toString()’ is an injective function from functions to strings and ‘str => () => str’ is an injective function from strings to functions.
- omaranto 8y agoI think that probably in Swift each individual string is required to be of finite length, as in most programming languages. The set of finite (but arbitrary) length strings drawn from a finite set of characters is countable. On the other hand this type BitSequence (pretending UInt contains all non-negative sequences) is the set of all countable infinite sequences of bits. That set, as you explained, has the cardinality of the continuum.
- JadeNB 8y ago> > The BitSequence type holds infinitely many values. In fact, it holds an unconscionable number of values. It has more values than String does. I like the typo of 'unconscionable' for 'uncountable'.