4 ms·

I'm wondering... can't you map all infinite binary strings to all positive integers? If the rightmost digit is the 1s column, the next rightmost digit is the 2s

I'm wondering... can't you map all infinite binary strings to all positive integers? If the rightmost digit is the 1s column, the next rightmost digit is the 2s column, and so on, you're just enumerating all possible positive integers. And each time you double (or quadruple) your pixels, you add one (or two) digits in front, getting bigger and bigger integers. But this always stays in the set of integers, which is countable. Am I missing something here? To me, this bijection makes it clear that you'll get a countable number of pixels with a countable number of doublings.

megablast 12y ago
Yes, I don't understand how he created an infinite number of binary strings, and suddenly flipping one bit means that the binary string is new? Surely the flipped bit binary string would already appear in the infinite list?
- pdonis 12y ago
  > I don't understand how he created an infinite number of binary strings, and suddenly flipping one bit means that the binary string is new? That's not quite what the diagonal argument does. Take an enumerated list of infinite binary strings, i.e., the strings are numbered as string #1, #2, #3, etc. Now construct a new infinite binary string in the following way: bit #1 of the new string is the opposite of bit #1 of string #1; bit #2 of the new string is the opposite of bit #2 of string #2; bit #3 of the new string is the opposite of bit #3 of string #3; etc. This new string cannot possibly appear in the list, because for all positive integers n, bit #n of the new string differs from bit #n of binary string #n in the list--i.e., the new string differs from every string in the list by at least one bit. In other words, if we are given any list of infinite binary strings enumerated by positive integers, we can always construct a new infinite binary string that is not in the list. So no such list can ever be complete. Hence, there must be more infinite binary strings than there are positive integers.
pdonis 12y ago
> can't you map all infinite binary strings to all positive integers? No. Positive integers are represented by finite binary strings, not infinite ones. Cantor's diagonal argument shows that there is no way to construct a one-to-one mapping between positive integers and infinite binary strings.

megablast 12y ago

Yes, I don't understand how he created an infinite number of binary strings, and suddenly flipping one bit means that the binary string is new? Surely the flipped bit binary string would already appear in the infinite list?

pdonis 12y ago
> I don't understand how he created an infinite number of binary strings, and suddenly flipping one bit means that the binary string is new? That's not quite what the diagonal argument does. Take an enumerated list of infinite binary strings, i.e., the strings are numbered as string #1, #2, #3, etc. Now construct a new infinite binary string in the following way: bit #1 of the new string is the opposite of bit #1 of string #1; bit #2 of the new string is the opposite of bit #2 of string #2; bit #3 of the new string is the opposite of bit #3 of string #3; etc. This new string cannot possibly appear in the list, because for all positive integers n, bit #n of the new string differs from bit #n of binary string #n in the list--i.e., the new string differs from every string in the list by at least one bit. In other words, if we are given any list of infinite binary strings enumerated by positive integers, we can always construct a new infinite binary string that is not in the list. So no such list can ever be complete. Hence, there must be more infinite binary strings than there are positive integers.

pdonis 12y ago

> can't you map all infinite binary strings to all positive integers? No. Positive integers are represented by finite binary strings, not infinite ones. Cantor's diagonal argument shows that there is no way to construct a one-to-one mapping between positive integers and infinite binary strings.