4 ms·

> 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

> 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 ago
  When 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 ago
Considering 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.
- DougBTX 8y ago
  That argument seems like it makes total sense, but I feel like I’m missing something so I’ll just have to say I don’t know!
  - joshuamorton 8y ago
    A more handwavy, but conceptually sound argument is that these functions to generate bit sequences can themselves be represented as turing machines. And if they can be represented as turing machines, we can write them down as a string (or a bit sequence). In general, a bunch of magic happens once you recognize (heh) that the sets of turing machines, strings (binary or otherwise), and integers are all countable and that you can biject between them fairly cleanly.
  - tomp 8y ago
    The argument is basically, "all actual Turing machines are finite, because the universe/computer memory is finite".

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 ago
When 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 ago

Considering 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.

DougBTX 8y ago
That argument seems like it makes total sense, but I feel like I’m missing something so I’ll just have to say I don’t know!
- joshuamorton 8y ago
  A more handwavy, but conceptually sound argument is that these functions to generate bit sequences can themselves be represented as turing machines. And if they can be represented as turing machines, we can write them down as a string (or a bit sequence). In general, a bunch of magic happens once you recognize (heh) that the sets of turing machines, strings (binary or otherwise), and integers are all countable and that you can biject between them fairly cleanly.
- tomp 8y ago
  The argument is basically, "all actual Turing machines are finite, because the universe/computer memory is finite".