Thomas Metcalf

Originally posted by wade-w:

"I think that in the end, this is a philosophical issue. I fail to see the essential difference in saying that we can describe any arbitrary real, and saying that it is therefore possible to describe all of them." (Emphasis original.)"

Well, I have no math background other than a couple of quarters of calculus, so I'm not in a position to evaluate your arguments that we will indeed have a way to describe any arbitrary real. But you're right about it being a philosophical issue -- yet I think there is indeed an important difference between those two statements.

It is possible in principle to describe any arbitrary real, and therefore it is possible in principle to describe all reals. My point in the (obviously unclear) original post was more that, de facto, there are some reals that we can never know. That is, if you were to look at the universe after humanity had come and gone, you could make a list of some of the real numbers that humans never knew about. And even if we don't accept determinism, there will still be real numbers we'll never know about. If this is so, then, right now, there are some real numbers we'll never be able to discover, although this is a consequence of our finite time allowance rather than anything about the numbers themselves.

[ December 12, 2002: Message edited by: Thomas Metcalf ]</p>

Jesse

Thomas Metcalf:
It is possible in principle to describe any arbitrary real, and therefore it is possible in principle to describe all reals.

Only if you allow "descriptions" consisting of an infinite number of symbols (like just listing every single digit of the number). If you confine yourself to finite descriptions you can't describe them all, although as I argued above, there's some ambiguity about what is meant by the term "finite description".

lpetrich

Every real number has an infinite-length representation: its decimal representation.

Finite-length representations are another story, however; there are only countably many of them, which means that most real numbers do not have finite-length representations.

So be careful about whether one has in mind a finite-length or an infinite-length representation.

On a related subject, natural-language grammars allow for countably many finite-length sentences and uncountably many infinite-length ones. Which likely have the real numbers' cardinality.

This is because natural languages have some grammatical features that permit infinite extension. Here are some examples:

(coordination)
I saw a dog and a cat and a dog and a dog and a cat and ...

(subordination)
I saw a dog, that was chasing a cat, that was chasing a dog, that was chasing a dog, that was chasing a cat, that was chasing...

My use of dogs and cats was done to create an analogy with the binary number representation. This means that

card(infinite sentences) &gt;= card(real numbers)

wade-w

Thomas said:

I agree with you here, Thomas. I interpreted what you were saying as meaning that there are numbers that are unknowable.

Another way to look at this is in terms of geometry. It is easy to see that there is a one-to-one correspondence between the real numbers and all points on a line. Thus every real can be interpreted as the length of some line segment. To say that there are some numbers we can never know is to say that there are some line segments we can never draw.

As for being able to describe any arbitrary real, the Dedkind Cuts I described earlier rely only on rational numbers. Since we can write any rational with a finite number of symbols, what we have to do is find the Dedekind Cut that corresponds to the given real, and there we are, a description of the real using a finite number of symbols.

Yes, there is no way to represent every real directly. This is an obvious consequence of the fact that the total number of possible names is countable, while the reals are uncountable. But it seems to me that we can do it indirectly.

[ December 12, 2002: Message edited by: wade-w ]

[ December 12, 2002: Message edited by: wade-w ]</p>

Claudia

It is even worse (or better) than that. There is a bijective application between any line segment and R, the segment having a finite length (use simple ad-hoc transformation on tangent function to find this bijection, for example).

CardinalMan

I wanted to say a few words regarding Jesse’s paradox about the existence of seemingly sound arguments which prove and refute the statement "The collection of describable numbers is countable".

As Jesse points out, a lot of problems can arise when we use the word "describable" in a loose, non-formalized, sense. However, I think that the argument in favor of the uncountability of the collection of describable numbers suffers a deeper flaw, which is highlighted here:

Before getting into a discussion of describable, let’s go to the realm of computable numbers, since there is a precise definition of them in terms of Turing machines which allows us to prove mathematical theorems. We can prove that the collection of computable numbers is countable because there are only countably many Turing machines. So what goes wrong with the following version of your argument? List all of the Turing machines that output a number and label them 1,2,3,etc. Consider the Turing machine which on input n (to determine the n^th decimal position) simulates the n^th Turing machine in the above list, and changes its value. This argument seems to show that there is some computable number not in the list.

The error is that there is no "uniform" Turing machine capable of listing exactly the Turing machines which output a number. Now, there does exist a so-called Universal Turing Machine, one which can simulate all others, but there does not exist one which is able to "pick out" those which output a number (i.e. those which halt on every input). Actually, the above argument is a proof of this fact (if such a machine existed, then we could create a Turing machine which outputs a number which differs from all outputs of Turing machines). A closely related result is the unsolvability of the halting problem (if we could computably determine when Turing machines halt, then we could avoid the above wrinkle about only considering the Turing machines which output numbers, and hence we can computably diagonalize as above to create a Turing machine which outputs a number which differs from all outputs of Turing machines).

I think that a similar, but of course vaguer argument works in the situation of descibable numbers. In order to make the argument for the uncountability of the collection of describable numbers, we must argue the collection of describable numbers is in some sense "uniformly describable", and I think that this is a major problem. We can create a "uniformly describable" list of all English expressions (perhaps augmented with mathematical symbols), but how do we "describably" pick out those which uniquely describe some number in order to perform the needed diagonalization? I suppose that you could say that if a particular English expression does not uniquely describe a number, then we can use any digit in its corresponding position in the diagonalization, but then we run into self-referential problems (by the using the word "descibe" in a the definition of something describable, much like "The smallest number that cannot be described using less than thirteen words").

I hope that this makes sense. Anybody agree or disagree with what I’ve said?

CardinalMan

Jesse

Hi CardinalMan--I sort of tried to address the issue of why the diagonalization of the set of all Turing-computable numbers cannot itself be Turing-computable in my second long post on this:

However, it seems to me that the notion of an "x-order oracle machine", where x is a finite or countably infinite ordinal number, is just as well-defined as a "Turing machine." So if you can define a number in terms of a program for an x-order oracle machine, then I think you also have a clear and unequivocal "finite description" of that number. The problem here is that it does not seem that all countable ordinals can themselves have finite descriptions, since the set of all countable ordinals has cardinality aleph-one in set theory, which is uncountable. If we had some formal system for enumerating countable ordinals, that system would be able to generate only countably many of them, and thus there would be a larger set of countable ordinals which could not be named within that system.

[ December 17, 2002: Message edited by: Jesse ]</p>

Goliath

Be careful! If we're talking about the real numbers, then the limit as x goes to zero of 1/x is undefined, since it's infinity as we approach from the right, but negative infinity as we approach from the left.

On the other hand, on the complex plane, there is no negative infinity, merely infinity, so one can make the convention that for points on the complex plane, 1/0=infinity (this is because we can think of the plane as the sphere with the north pole taken out ala the stereographic projection map).

Sincerely,

Goliath

CardinalMan

Hi Jesse. I feel kind of silly seeing as how I must have completely overlooked that post of yours. Sorry about that. You explained everything quite well in it.

Well now that I've finally read that post, I can make some comments about what you said there. There is a well-defined notion of a computable ordinal. Call an ordinal computable if it the isomorphism type of a computable well-ordering of the natural numbers. For example, omega + omega is a computable ordinal because it is the order type of the computable well-ordering 1,3,5,7,...,2,4,6,8,... The set of computable ordinals forms a countable (since there are only countably many Turing machines) initial segment of the ordinals. Hence, there is a first noncomputable ordinal, which is usually denoted omega_1^CK (that's omega with subscript 1 and superscript CK. The CK stands for Church and Kleene, two pioneers in the study of this object). Omega_1^CK plays a similar role in computability theory as omega_1, the first uncountable ordinal, does in set theory.

The process that you suggest going through to get, in your terminology, higher-order oracle machines can be done with great success through the computable ordinals. Now there are only countably many computable ordinals, so this process only produces countably many real numbers, and hence avoids the difficulties you present. One could go further through more (noncomputable) ordinals, but these ordinals do not have a nice "finitistic" description, so there is good reason to think of the reals that you get by delving further into the ordinals to be qualitatively different and much less "describable" than you ones you meet at earlier stages.

In fact, the collection of real numbers that can be computed by an oracle machine at some computable ordinal level form a very important class of real numbers called the hyperarithmetic reals (the ones that occur at some finite stage are called the arithmetic reals). If you know some real analysis, there are strong analogies between the Borel hierarchy of sets of real numbers, and the hyperarithmetic hierarchy of real numbers. In the former case, you get a hierarchy through the ordinals up to omega_1, and in the latter case you get a hierarchy through the ordinals up to omega_1^CK.

CardinalMan