wade-w

Please do. I'm not sure that I understand what you mean, because your initial explanation doesn't make sense to me.

Obviously, the total number of sentences that can be constructed is not only less than the number of reals, (which is not just infinite, but uncountable. The set of irrationals is also uncountable.), that number, while it may seem very large to us, is finite. Since the english language has a finite vocabulary, the total number of possible combinations of that vocabulary is also finite, and is then further restricted by the rules of grammar to some smaller total number of valid sentences. Thus there is not nor can there ever be any kind of correspondence between the total number of sentences and the real numbers. However, this does not stop us from being able to define or describe any given number, as far as I know.

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

Principia

If we can describe any number, it seems to me that there is a one-to-one correspondence between a number and a sentence. But, this topic ties in well with lpetrich's original observation about determining an algorithm of least (finite?) complexity for any real. If such minimum length descriptions are possible, then these should also be translatable to finite sentences.

Jesse

Ordinary human languages can be a little problematic for describing numbers--you can get paradoxical descriptions like "The smallest number that cannot be described using less than thirteen words" (a description which contains 12 words). It's better to have a way of formalizing "descriptions", like the set of all possible <a href="http://www.science.gmu.edu/~jsteidel/801-prj/turing.html" target="_blank">Turing machine</a> outputs (every distinct Turing machine can be described as a finite string of symbols which serves as the input needed to simulate that machine on a universal Turing machine--see <a href="http://www.wikipedia.org/wiki/Turing_machine" target="_blank">here</a> for more). However, any formalized list of descriptions will leave off certain real numbers that are clearly describable in a more general sense--this can be shown using a "diagonalization argument". Suppose you have a list of real numbers between 0 and 1 expanded out in some base--base 2, let's say. Now you can define a new number where the nth digit is always the opposite of the nth digit on the list; for example:

1. 0.10101010101...
2. 0.00010100010...
3. 0.11101001010...
4. 0.11010101010...
5. 0.01100001101...

..and so on. Your new number will be 0.01001... Notice that this number is different from every number of the list--it differs from the first number in its first digit, it differs from the second number in its second digit, etc. But as long as the rule for generating the list is itself describable in a finite way (like my 'set of all Turing machine outputs' above), then "the diagonalization of the list generated by rule X" also qualifies as a finite description, at least in english. So there can never be a one-to-one correspondence between the set of real numbers which are "describable" in this sense and the natural numbers--the set of describable real numbers would seem to be itself "uncountable", as a set theorist would say.

On the other hand, if you confine yourself to numbers that can be described within some formal language, like symbols which code for Turing machines, the set of numbers you can "describe" with this language will be countable, since it's always possible create a one-to-one correspondence between strings containing a finite number of symbols and the natural numbers. For example, you can list them alphabetically, with shorter strings coming before longer ones...for example, if your symbols were "A" and "B" your list would start out like this:

1. A
2. B
3. AA
4. AB
5. BA
6. BB
7. AAA
8. AAB

...and so on. The odd thing is that this argument should apply just as well to descriptions in ordinary language, which also consists of strings of a finite number of symbols. Yet the earlier argument suggests that any time you try to come up with a list of all describable numbers, you can always generate a new number that is describable in ordinary language as the diagonalization of the previous list, and is therefore not on the list. So actually, I'm not sure whether to say the set of describable numbers is countable or uncountable--there seem to be arguments for both. Again, the problem seems to be that informal language can be ambiguous (what is 'the most interesting number under 10'?) but at the same time it is more general than formal languages where it is unambiguous which description corresponds to which number (like Turing machine descriptions), because for any such language you can always describe a new number in terms of the diagonalization of all numbers describable in that formal language. Yet "the diagonalization of all symbol-strings in english" would not describe any particular number, precisely because so many ordinary-language strings are ambiguous.

So now I'm puzzled about whether the set of describable numbers is countable or uncountable, and I've probably confused everyone else along the way. Sorry about that.

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

wade-w

My original post was based on my initial musings about what Thomas Metcalf may have meant. I may in fact be wrong, but my intuition goes against it. Of course, we all know that is really meaningless in the end. I am still thinking about this, and I think I see a way to use the axiom of choice to show that it must be possible to identify any given real number.

Consider the class C of all unique subsets of the real numbers with a cardinal number of 1. By the axiom of choice, there is a function f such that for each S in C, f(S) is in S. Thus f will provide a way distinguish any given real.

Though it may be prudent to wait and see what Thomas actually has to say before we go much further with this!

lpetrich

As to the finiteness of an algorithm, there are two kinds:

(1) The algorithm has only a finite number of statements (finite length). This finiteness implies that its numerical values can be found with a finite number of steps starting from 0 and 1, namely, the rational numbers.

(2) The algorithm is guaranteed to have a finite number of steps.

If the algorithm includes loops, it can easily satisfy (1) without satisfying (2). Thus, to compute pi/4, this algorithm will work:

[code]
val = 0;
for (n=0,s=1; /* will never stop */ ; n++,s*=-1)
{
val += s/(2*n+1);
}
</pre>[/quote]

A finite length, but an infinite number of steps. One with a finite number of steps can only calculate rational numbers.

The number of finite-length algorithms can easily be shown to be countable. This means that there will always be real numbers that cannot be calculated with such an algorithm. These real numbers will be transcendental, since all algebraic ones can be found with some numerical-mathematics successive-approximation algorithm.

wade-w

Jesse, that looks a lot like the usual argument for showing that R is uncountable.

Edited because I'm not really awake.

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

Jesse

Wade-w, I added some to my post--could you read the rest of it and tell me if you think my question is answerable?

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

wade-w

Interesting question, Jesse. I am a bit tired right now, but my inital impression is that if you restrict yourself to just the numbers that can be described by some finite set of symbols then the set must necessarily be countable. For example, any integer or rational can all be described uniquely using just the 10 numerals that we all know. Also, the number of symbols really doesn't matter.

But all that shows is that using ONLY a finite set of symbols in a formal language is inadequate for our purposes. By using the turing machine, and then constructing diagonals, it appears that you have added enough complexity to overcome the problem of a finite set of symbols.

The question here, it seems to me, is can we develop an algorithm, or a set of algorithms, that can be used to generate any given number.

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

wade-w

On another note, I seem to recall that Cantor defined irrational numbers in terms of convergent series of rational numbers. Its been a LONG time, and I am looking for details, but that may be an answer.

Of course, this all may be premature, since we don't know for sure what Thomas' argument actually is . (But I suspect that it is along the lines of Jesse's second argument.)

wade-w

One last thought, and then I'm going to bed, and will take this up tomorrow. If what Thomas means is that we will never be able to name all the real numbers, in the sense that there are not enough names to go around, even if we can use sentences to contsruct these names, then I agreee. The total number of possible names is at best only countable, as Jesse has shown above. There will never be enough names to go around.
However, I don't think that this means that there are numbers that we will never be able to know.

I'm looking forward to hearing what you really mean. And I apologize if I have been going off in a completely different direction from what you intend!