6 ms·

Could you show us one of these "random" reals? There is a simple algorithm for generating every possible decimal number: x.0 x.1 x.2 ... x.01 x.02

Could you show us one of these "random" reals? There is a simple algorithm for generating every possible decimal number: x.0 x.1 x.2 ... x.01 x.02 ... x.10 x.11 x.12 ... x.20 x.21 ... x.30 x.31 ... x.99 x.001 x.002 ... In binary, it's even simpler; you just generate every permutation of bits.

rocqua 8y ago
That gives every terminating decimal or binary number. For example, you will never list 1/3, or pi or sqrt(2). To see why you cannot generate every possible real number as a list, look up cantors diagonal argument.
- windows_tips 8y ago
  Are you sure 1/3 is a real number?
  - filmor 8y ago
    Real numbers are defined as a particular extension of the rational numbers, which 1/3 is.
  - TJSomething 8y ago
    It's as "real" as 1/2, which is on your list.
    - windows_tips 8y ago
      I guess you also need to interpret each number in the list in each possible base.
  - rocqua 8y ago
    "Real numbers" here refers to a very specific construction of numbers. There is pretty good argument, which the actual post is about, that states this construction is actually rather unrealistic. The issue being that there are way to many "real numbers".
thomasahle 8y ago
It's counter-intuitive, but your algorithm actually only generate a subset of the rational numbers. That's because all of your numbers have a finite number of decimal digits. Most reals, like 1/3 or pi, will never appear in your list. (Though numbers close to them will.) Most reals don't have a generating algorithm, since there is an uncountable number of reals, but only a countable number of algorithms. (Assuming an algorithm has to be a finite length program.)
- windows_tips 8y ago
  I'm not sure 1/3 is exactly a number. It seems to be an expression when written out. pi, likewise, appears to be a word, not a number.
  - TJSomething 8y ago
    Numbers aren't lists of digits. They're abstract concepts that are referred to by lists of digits for the purpose of convenience. You can even have numbers without having invented digits. It's just annoying to write out one million, two hundred thirty-four thousand, five hundred sixty-seven and eighty-nine hundredths. So, we say 1,234,567.89 (or 1.234.567,89 for countries that use the comma for decimals). 0.5 in base 10 is the same as 0.1 in base 2, which is the same as 0.11111... in base 3. And the choice of base is completely arbitrary, with some societies using others, like base 12 or base 60.
cyphar 8y ago
Your proposed enumeration of decimals (counter-intuitively) would miss an uncountably infinite number of values. This enumeration is not possible in any fashion, which you can prove fairly easily with Cantor's Diagonal Argument[1]. The punch-line is that there are more real numbers between 0 and 1 than there are whole numbers greater than 0. The proof basically shows that even if you imagine that you had a countably-infinitely-long list of all the real numbers between 0 and 1, you can construct a number that must be missing from the list -- which is a contradiction, and thus no such list can exist (implying that there are more numbers between 0 and 1 than numbers greater than 0). For instance, your enumeration is missing every irrational (or even recurring decimal) number. That set of numbers is uncountably infinite. [1]: https://en.wikipedia.org/wiki/Cantor's_diagonal_argument https://en.wikipedia.org/wiki/Cantor's_diagonal_argument
- windows_tips 8y ago
  >The proof basically shows that even if you imagine that you had a countably-infinitely-long list of all the real numbers between 0 and 1, you can construct a number that must be missing from the list -- which is a contradiction, and thus no such list can exist (implying that there are more numbers between 0 and 1 than numbers greater than 0). So, there is no list of all the real numbers between 0 and 1, but you are claiming there are uncountably infinite of them?
  - leephillips 8y ago
    That's the definition of uncountably infinite: can not be put in 1-to-1 correspondence with the integers (can not be listed).
  - filmor 8y ago
    That is pretty much the definition of uncountability :)
  - deleted 8y ago
    [deleted]
  - cyphar 8y ago
    Yes, because if there were such a list then you could assign a 1-to-1 mapping (by list index) of each number between 0 and 1 to a whole number which would prove they have the same size. If it is impossible to have a complete list of all real numbers between 0 and 1 then there cannot be such a mapping, and thus you'll "run out" of integers before you've counted all of the reals (more correctly you're showing that the size must be larger because if it was smaller or of equal size it could fit in such a list). Numberphile did a pretty good introductory video to this if you want to learn more: https://www.youtube.com/watch?v=elvOZm0d4H0 https://www.youtube.com/watch?v=elvOZm0d4H0.
quickthrower2 8y ago
I'll be generous and assume you mean decimal as in the data-type: an interesting set of "floating point" numbers that behaves really badly (not a field, for example)

rocqua 8y ago

That gives every terminating decimal or binary number. For example, you will never list 1/3, or pi or sqrt(2). To see why you cannot generate every possible real number as a list, look up cantors diagonal argument.

windows_tips 8y ago
Are you sure 1/3 is a real number?
- filmor 8y ago
  Real numbers are defined as a particular extension of the rational numbers, which 1/3 is.
- TJSomething 8y ago
  It's as "real" as 1/2, which is on your list.
  - windows_tips 8y ago
    I guess you also need to interpret each number in the list in each possible base.
- rocqua 8y ago
  "Real numbers" here refers to a very specific construction of numbers. There is pretty good argument, which the actual post is about, that states this construction is actually rather unrealistic. The issue being that there are way to many "real numbers".

thomasahle 8y ago

It's counter-intuitive, but your algorithm actually only generate a subset of the rational numbers. That's because all of your numbers have a finite number of decimal digits. Most reals, like 1/3 or pi, will never appear in your list. (Though numbers close to them will.) Most reals don't have a generating algorithm, since there is an uncountable number of reals, but only a countable number of algorithms. (Assuming an algorithm has to be a finite length program.)

windows_tips 8y ago
I'm not sure 1/3 is exactly a number. It seems to be an expression when written out. pi, likewise, appears to be a word, not a number.
- TJSomething 8y ago
  Numbers aren't lists of digits. They're abstract concepts that are referred to by lists of digits for the purpose of convenience. You can even have numbers without having invented digits. It's just annoying to write out one million, two hundred thirty-four thousand, five hundred sixty-seven and eighty-nine hundredths. So, we say 1,234,567.89 (or 1.234.567,89 for countries that use the comma for decimals). 0.5 in base 10 is the same as 0.1 in base 2, which is the same as 0.11111... in base 3. And the choice of base is completely arbitrary, with some societies using others, like base 12 or base 60.

cyphar 8y ago

Your proposed enumeration of decimals (counter-intuitively) would miss an uncountably infinite number of values. This enumeration is not possible in any fashion, which you can prove fairly easily with Cantor's Diagonal Argument[1]. The punch-line is that there are more real numbers between 0 and 1 than there are whole numbers greater than 0. The proof basically shows that even if you imagine that you had a countably-infinitely-long list of all the real numbers between 0 and 1, you can construct a number that must be missing from the list -- which is a contradiction, and thus no such list can exist (implying that there are more numbers between 0 and 1 than numbers greater than 0). For instance, your enumeration is missing every irrational (or even recurring decimal) number. That set of numbers is uncountably infinite. [1]: https://en.wikipedia.org/wiki/Cantor's_diagonal_argument https://en.wikipedia.org/wiki/Cantor's_diagonal_argument

windows_tips 8y ago
>The proof basically shows that even if you imagine that you had a countably-infinitely-long list of all the real numbers between 0 and 1, you can construct a number that must be missing from the list -- which is a contradiction, and thus no such list can exist (implying that there are more numbers between 0 and 1 than numbers greater than 0). So, there is no list of all the real numbers between 0 and 1, but you are claiming there are uncountably infinite of them?
- leephillips 8y ago
  That's the definition of uncountably infinite: can not be put in 1-to-1 correspondence with the integers (can not be listed).
- filmor 8y ago
  That is pretty much the definition of uncountability :)
- deleted 8y ago
  [deleted]
- cyphar 8y ago
  Yes, because if there were such a list then you could assign a 1-to-1 mapping (by list index) of each number between 0 and 1 to a whole number which would prove they have the same size. If it is impossible to have a complete list of all real numbers between 0 and 1 then there cannot be such a mapping, and thus you'll "run out" of integers before you've counted all of the reals (more correctly you're showing that the size must be larger because if it was smaller or of equal size it could fit in such a list). Numberphile did a pretty good introductory video to this if you want to learn more: https://www.youtube.com/watch?v=elvOZm0d4H0 https://www.youtube.com/watch?v=elvOZm0d4H0.

quickthrower2 8y ago

I'll be generous and assume you mean decimal as in the data-type: an interesting set of "floating point" numbers that behaves really badly (not a field, for example)