Hacker News Reader

Comment by windows_tips | Hacker News Reader

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.

View on HN

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

>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?

That's the definition of uncountably infinite: can not be put in 1-to-1 correspondence with the integers (can not be listed).

That is pretty much the definition of uncountability :)

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.

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

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.

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.

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.

Are you sure 1/3 is a real number?

Real numbers are defined as a particular extension of the rational numbers, which 1/3 is.

It's as "real" as 1/2, which is on your list.

I guess you also need to interpret each number in the list in each possible base.

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

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)

Reply on news.ycombinator.com