Hacker News Reader

Comment by flebron | Hacker News Reader

This is a similar argument to sqrt(2) being "not a number", back in the BC's, because it was not rational. And yet, you can construct it in a straightforward manner by making a right angled triangle with catheti of length 1, giving a hypotenuse of length sqrt(2). I suppose this would have made you equally uncomfortable back then.

One can definitely "work with" numbers that aren't easy to write. a + (-a) = 0, and this is valid for every real number a, not just "the ones which I can describe with a finite amount of information", or the ones I've written down at some point in my life.

View on HN

The 'problem' with the reals is that there are numbers that cannot be constructed.

Every number that we can construct can be constructed in a finite amount of symbols. For example sqrt(2) is an unambiguous description of itself. Without use of the sqrt function, we can also call it the number x such that x*x=2. However, every description is a finite string constructed from a finite alphabet. We can easily show that the set of all such descriptions is countably infinite. However, we can also show that the set of all real numbers is uncountably infinite. Therefore, there is an uncountable infinity of real numbers that cannot be constructed.

Indeed, and the constructable numbers are studied as a subset of the reals, as are the algebraics, and the computables. You can make a choice as to the domain of discourse. If you like, feel free to restrict it to the computables (or the constructables).

Then apply the diagonal argument. Take the computable numbers between 0 and 1, including 0, not including 1. These are countable, so we can write them in a list, taking a mapping k from the natural numbers: { 1, 2, 3, 4, ... } to the set of computable numbers in [0,1).

Now let's construct a new number. In the first decimal place we put 1 if the first decimal place of k(1) is 0, and 0 otherwise. In the second place we put 1 if the second decimal place of k(2) is 0, and 0 otherwise. And so on.

This results in a number that's not on the list, and is between 0 and 1. So it must, by our assumption, not be computable.

Things become tricky.

So there's a choice to be made, and most mainstream mathematicians have decided to talk about, use, study, and otherwise accept the existence of the real numbers because it's convenient.

Feel free to choose otherwise.

I can't find a flaw in your arguement, but it seems like it leads to a contradiction.

Let a constructable number be one which can be unambiguously described in a finite string. Because we are working from a finite alphabet, we can trivially see that their is a bijection between the constructables and the integers (if we have n symbols, then each string can be read as an integer in base n, so the amount of constructables is no larger than the integers. We can also show that all integers are constructable, so the amount of constructables is no smaller than the integers). Now, take the set of all constructables, and use the diagonal arguement to construct a new number. We can see that this number is not constructable, however, it would appear that I have just unambigously described it, meaning that it must be constructable.

The only potential hole I see is that the ordering of the constructables when I apply the diagonal arguement is ambigous, but we can unambiguously order them by the lexical ordering of their 'canocial' description, and we can unambiguous define the canonical description as the smallest one when translated into a base n integer.

I suspect that doing the above will run into problems with computable numbers (as it likely involves the halting problem), however it appears to be an unambiguous description of a real number that is not constructable. Obviously there is some flaw in this reasoning.

I reckon the flaw is that your bijection between N and your set of "constructable" numbers is not itself "constructable". In fact your argument can probably turned into a proof that there is no such "constructable" bijection.

You're using too many imprecise terms. First, what does it mean for something to be able to be "unambiguously" described? As opposed to ambiguously described? You have to define it.

Second, what does it mean for something to be described (unambiguously or otherwise) with a "finite string?" What is a "string" here?

You're playing too loose with these ideas and it's biting you. You have to start by defining them precisely. For example, I don't see at all how the new number not on your list is "described unambiguously." It's presumably not enough to say "there is some number not on my list, we will call it x" since we know there is more than just one such number. How is that unambiguous?

In any case, that's why you have to define these things precisely.

How do you know if a number is constructible? It is described by a computer program. Although the set of computer programs can be enumerated, determining if a program it will print out any digits is not something that cannot be determined. So yes, Halting Problem. :)

So you cannot list all constructables in a constructive manner because the list itself is not constructible.

A related concept

https://en.wikipedia.org/wiki/Chaitin%27s_constant

Reply on news.ycombinator.com