Set of real numbers in a finite number of words

  • Thread starter Jano L.
  • Start date
  • #1
Jano L.
Gold Member
1,333
74
Hello everybody,

Yesterday I've read that there exist a real number r which cannot be defined by a finite number of words. This result, although quite awesome, is so strange that it lead Poincaré to doubt Cantor's work and state "never consider objects that can't be defined in finite number of words".

In our course on analysis, our professor postulated the existence of a supremum for any bounded sequence of rational numbers and I think the existence of the set of real numbers followed.

I am not entirely satisfied by this approach though, because it postulates supremum, which is not particularly simple notion.

Do you think the set of real numbers can be defined in finite number of words, using only basic concepts? (whole numbers, simple logic, ...)

Or do you think it is impossible and the set has to be postulated by force?

What are your feelings about this?
Which possibility do you prefer?

Jano
 

Answers and Replies

  • #2
Fredrik
Staff Emeritus
Science Advisor
Gold Member
10,872
418
There are many ways to show that the field of real numbers "exists" in the sense that a field with the desired properties can be defined from the field of rational numbers. The most popular ones seems to be Dedekind cuts (see e.g. "Set theory for guided independent study" by Derek Goldrei), and metric space completion (see e.g. "Foundations of modern analysis" by Avner Friedman, for a proof that metric spaces can be "completed"). I very much doubt that there could be a way that's much simpler than those. I like the metric space completion method, because it has other uses that are significant to physicists, so it's less likely to be a waste of time to learn it.

These constructions clearly do use only a finite number of words. What your professor was talking about is how a field that's defined using one of those methods contains members that can't be specified in a finite number of words. The argument is simple: Every real number has an infinite decimal expansion (possibly ending with infinitely many zeroes). If we can specify that decimal expansion in a finite number of words, we can write a computer program that generates all those decimals, one at a time. The program may never finish its run, but the program itself is a representation of that number. The problem is that there's only a countable number of computer programs. This implies that a number that can be generated this way belongs to a countable subset of ℝ, but ℝ is uncountable, so that subset can't be equal to ℝ.
 
  • #3
Jano L.
Gold Member
1,333
74
Thank you Fredrik. I think what puzzles me is this:

The set of real numbers is defined with finite number of words (say, 500 words). But there is an element of this set which cannot be defined with finite number of words (say, 1,000,000,000 words is not enough). It seems that one element of the set is more complicated than the set itself.

This is very strange. I would believe it if it was exactly the opposite.

Jano
 
  • #4
Fredrik
Staff Emeritus
Science Advisor
Gold Member
10,872
418
Yes, it's kind of strange. It got even stranger when Max Tegmark used it to argue that a multiverse with infinitely many universes is a simpler idea than a single universe. Link.
 
  • #5
22,129
3,298
Yes, this is true, there are real numbers that are "more complicated" than the set of real numbers.

But it's quite unfair to say that this is a problem with real numbers only. The situation truly shows up everywhere.

For example, the set of prime numbers are very easy to describe, but the seperate prime numbers can be quite complicated.

This is just one example, but the more you progress in mathematics, the more that the situation shows up. It's generally easier to describe the set of elements than the individual elements.
 
  • #6
lavinia
Science Advisor
Gold Member
3,264
646
Hello everybody,

Yesterday I've read that there exist a real number r which cannot be defined by a finite number of words. This result, although quite awesome, is so strange that it lead Poincaré to doubt Cantor's work and state "never consider objects that can't be defined in finite number of words".

In our course on analysis, our professor postulated the existence of a supremum for any bounded sequence of rational numbers and I think the existence of the set of real numbers followed.

I am not entirely satisfied by this approach though, because it postulates supremum, which is not particularly simple notion.

Do you think the set of real numbers can be defined in finite number of words, using only basic concepts? (whole numbers, simple logic, ...)

Or do you think it is impossible and the set has to be postulated by force?

What are your feelings about this?
Which possibility do you prefer?

Jano

The number of finite sets of words is countable. So they can not specifically define each real number since there are uncountably many of them

one can define the reals from the rationals using the idea of Dedekind cuts. This require no other ideas than the euclidean metric on the rationals. I am not sure how ones extends the arithmetic to these without notions of Cauchy sequence. Maybe it is not possible.
 
  • #7
Fredrik
Staff Emeritus
Science Advisor
Gold Member
10,872
418
I am not sure how ones extends the arithmetic to these without notions of Cauchy sequence. Maybe it is not possible.
Goldrei does this. A real number is defined as a set ##\mathbf{r}\subset\mathbb Q## such that
(a) ##\mathbf{r}\neq\emptyset,\ \mathbf{r}\neq\mathbb Q##
(b) If ##p,q\in\mathbb Q## are such that ##q\in\mathbf{r}## and ##p<q##, then ##p\in\mathbf{r}##.
(c) ##\mathbf{r}## doesn't have a maximum element.

The definition of addition is simple: ##\mathbf{r}+\mathbf{s}=\{p+q|p\in\mathbf{r},\ q\in\mathbf{s}\}##. Multiplication is a bit trickier, but it doesn't look too hard. The hard (tedious) part is to verify that all the axioms of the real number field are satisfied.
 
Last edited:
  • #8
disregardthat
Science Advisor
1,866
34
The crux of the issue is the step where we define R to be the set of all dedekin cuts (or cauchy-sequences), without specifying each dedekin cut we are considering. Set theory allows us to do this through its axioms, some of which Poincare undoubtedly would have dismissed on the same token.

To be fair, it's not a meaningless criticism, but almost all mathematicians today accept set theory, or specifically ZFC, in mathematics.
 
  • #9
Jano L.
Gold Member
1,333
74
Thank you Fredrik! That is exactly the kind of definition I was thinking about. Clear and short. But still it is suspicious that you define real number and the set of real numbers at the same time. Is it possible to disentangle them? (First real number, then the set). Disregardthat, what would be the disputable step in this definition for Poincaré? Is it the fact that we are defining the whole set of real numbers without constructing its elements first?
 
  • #10
795
7
Do you think the set of real numbers can be defined in finite number of words, using only basic concepts? (whole numbers, simple logic, ...)

Yes, the real numbers are the unique complete totally ordered field.

http://en.wikipedia.org/wiki/Real_number

Each of those technical terms (complete, totally ordered, field) can be defined in terms of logic and set theory.

It's not mysterious that a set is simpler to describe than its elements. If you have a bag of groceries, then "bag of groceries" is its description. But a tomato has a complex molecular and physical structure that's not described by "bag of groceries." Sets are often simpler than their elements.
 
Last edited:
  • #11
Jano L.
Gold Member
1,333
74
Steve,
I agree there is nothing mysterious with the bag of groceries. You already know what grocery is, so you can imagine some of your favourite vegetables instead of "groceries".

But for reals it is kind of peculiar, because we are defining a very special set of elements and we do not have the definition of these elements in hand. It is like "bag full of krandak", where you (and I) do not know what krandak is.
 
  • #12
Fredrik
Staff Emeritus
Science Advisor
Gold Member
10,872
418
Thank you Fredrik! That is exactly the kind of definition I was thinking about. Clear and short. But still it is suspicious that you define real number and the set of real numbers at the same time. Is it possible to disentangle them? (First real number, then the set).
This definition already does it that way. The definition says that a subset of the rational numbers is said to be a real number if it's closed from the left (i.e. satisfies condition b), doesn't have a maximum element, and isn't equal to either ##\mathbb Q## or ##\emptyset##.

Edit: The justification for this is that one of the ZFC axioms says that given a set S and a property P, there's a set whose members are precisely the elements of S that have property P.
 
Last edited:
  • #13
Jano L.
Gold Member
1,333
74
Ah, of course you are right, you define what the real number is and then the set of them follows. My last post was silly. Thanks, I need to think about this more.
 
  • #14
mathman
Science Advisor
8,006
518
Yesterday I've read that there exist a real number r which cannot be defined by a finite number of words. This result, although quite awesome, is so strange that it lead Poincaré to doubt Cantor's work and state "never consider objects that can't be defined in finite number of words".

This looks like you could end up with one of those logical paradox puzzles. For example: "Smallest positive number than cannot be defined by a finite number of words" defines that number with a finite number of words!
 
  • #15
Jano L.
Gold Member
1,333
74
That is an interesting example. First it seems like it refutes the existence of those weird numbers. But I were on the other side I could still say that it is only your definition of the number which is inconsistent - there is no smallest positive number, because there is an infinite number of them (arbitrarily close to 0). But I like the example. Maybe it can be improved somehow?

Thinking about these weird numbers, everytime you would find such a number, you would contradict its property that it is undefinable in finite number of words. Seems to me much like claiming the existence of non-existing things.
 
  • #16
795
7
This looks like you could end up with one of those logical paradox puzzles. For example: "Smallest positive number than cannot be defined by a finite number of words" defines that number with a finite number of words!

I don't believe there is any positive integer that can't be described in a finite number of words. So the set you've defined is empty, and has no smallest member.

Any finite integer has an English-language name -- "eleven billion, eight hundred seventy million, six hundred two thousand, and 47" is the English language name for a particular number.

Every number has such a name, as long as we're allowed to keep making up names for the powers of 1000, like thousand, million, billion, trillion, humonga-gazillion, etc.

Currently only finitely many of these are defined.

But even this is not a problem. If you didn't have a name for a million, a thousand thousand would do. So in fact we can just say that "one thousand thousand thousand thousand" stands for 10^12, whether there's a name for it or not.

With that convention, every positive integer can be named in a finite number of words.

I believe the original paradox is "the smallest positive integer that can not be named is less than 1000 syllables." Now THAT defines a particular positive integer which we just named or characterized in less than 1000 syllables. So that's a valid paradox.

To repeat: "the smallest positive number than cannot be defined by a finite number of words" does not exist; because every positive number (assuming you mean integer) can be described in a finite number of words.
 
  • #17
Deveno
Science Advisor
908
6
This looks like you could end up with one of those logical paradox puzzles. For example: "Smallest positive number than cannot be defined by a finite number of words" defines that number with a finite number of words!

although as others have pointed out, "finite number of words" is a poor criterion, similar (and more strongly paradoxical) formulations are possible.

you might enjoy reading this:

http://en.wikipedia.org/wiki/Berry_paradox

under certain circumstances, this is equivalent to Godel's Incompleteness Statement, that there are (in certain formal systems) true, yet unprovable statements.

the "root cause" of most of these thorny questions, is in "defining "definable"". it's hard to avoid self-reference in giving a definiton of "definition". one way this is avoided, is to create separate "layers" of meaning, and only talk about "higher layers" from "lower layers".

so, for example, you can talk about the truth or falsity of a sentence, as long as that sentence itself isn't asserting it's own truth or falsity, which neatly side-steps the "this sentence is false" paradox as "ill-formed". perhaps you can see that doing this, is going to require a "lot" of layers, and keeping them all straight makes for some complicated bookkeeping.
 
  • #18
mathman
Science Advisor
8,006
518
I don't believe there is any positive integer that can't be described in a finite number of words. So the set you've defined is empty, and has no smallest member.

Any finite integer has an English-language name -- "eleven billion, eight hundred seventy million, six hundred two thousand, and 47" is the English language name for a particular number.

Every number has such a name, as long as we're allowed to keep making up names for the powers of 1000, like thousand, million, billion, trillion, humonga-gazillion, etc.

Currently only finitely many of these are defined.

But even this is not a problem. If you didn't have a name for a million, a thousand thousand would do. So in fact we can just say that "one thousand thousand thousand thousand" stands for 10^12, whether there's a name for it or not.

With that convention, every positive integer can be named in a finite number of words.

I believe the original paradox is "the smallest positive integer that can not be named is less than 1000 syllables." Now THAT defines a particular positive integer which we just named or characterized in less than 1000 syllables. So that's a valid paradox.

To repeat: "the smallest positive number than cannot be defined by a finite number of words" does not exist; because every positive number (assuming you mean integer) can be described in a finite number of words.
The original question is about naming real numbers, not jusr integers.
 
  • #19
795
7
The original question is about naming real numbers, not jusr integers.

If you take the set of positive reals that are not expressible in a finite number of words, what makes you think that set has a smallest element? The set is bounded below by zero, so at best we can say that the set has an inf.

I suppose you could fix this up by saying that your paradoxical number is the inf of all the positive reals not expressible etc.

Is that what you had in mind?
 
  • #20
lavinia
Science Advisor
Gold Member
3,264
646
If you take the set of positive reals that are not expressible in a finite number of words, what makes you think that set has a smallest element?

By the Well Ordering Principle, the set can be well ordered. Such a set has a first element under the well ordering.
 
  • #21
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
The problem is that there's only a countable number of computer programs. This implies that a number that can be generated this way belongs to a countable subset of ℝ, but ℝ is uncountable, so that subset can't be equal to ℝ.
A nitpick -- this is a (common) level slip.

It is true that, within a set theoretic universe, we can formulate the notion of an algorithm. And it is true that there does not exist a function within that universe that is an injection from real numbers to algorithms.

However, algorithms can also be specified in the metalanguage. It could very well be possible that every real number in the universe is given by some algorithm in the metalanguage. It may even be true if every algorithm in the metalanguage can be represented by an algorithm in the universe. (It's hard to find clear statements on these points, but I've asked and I'm pretty sure I've had someone knowledgeable tell me that both of the above really are possible)
 
  • #22
795
7
By the Well Ordering Principle, the set can be well ordered. Such a set has a first element under the well ordering.

If these are positive integers, then the set is empty hence has no first element.

If as Mathman says they are positive reals, then the inf of this set, no matter how you rigorously defined it, must be zero.

In either case, there is no paradoxical number.
 
  • #23
795
7
A nitpick -- this is a (common) level slip.

It is true that, within a set theoretic universe, we can formulate the notion of an algorithm. And it is true that there does not exist a function within that universe that is an injection from real numbers to algorithms.

However, algorithms can also be specified in the metalanguage. It could very well be possible that every real number in the universe is given by some algorithm in the metalanguage. It may even be true if every algorithm in the metalanguage can be represented by an algorithm in the universe. (It's hard to find clear statements on these points, but I've asked and I'm pretty sure I've had someone knowledgeable tell me that both of the above really are possible)

I've never heard of this. Can you provide more detail?

It seems to me that it's unquestionably the case that there are only countably many finite-length strings over a countable language. This applies to English as well as any logical system you might devise. Since there are uncountably many reals, it clear we can only name or algorithmise (if that's a word) countably many of them.

This reasoning would apply to the language or the metalanguage, whatever that means. There simply aren't enough finite-length strings to go around.

Of course if you allow infinite-length strings then any real can be named by its decimal expansion. But infinite-length strings defeat the intuitive meaning of an algorithm.
 
  • #24
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
It seems to me that it's unquestionably the case that there are only countably many finite-length strings over a countable language.
...
Since there are uncountably many reals, it clear we can only name or algorithmise (if that's a word) countably many of them....
There simply aren't enough finite-length strings to go around.
A good starting point would be to read up on http://en.wikipedia.org/wiki/Skolem's_paradox]Skolem's[/PLAIN] [Broken] (pseudo)paradox.


An introductory text on non-standard calculus (e.g. Keisler's free online text) might be a good practical introduction to notions of "internal" versus "external".
 
Last edited by a moderator:
  • #25
795
7
A good starting point would be to read up on http://en.wikipedia.org/wiki/Skolem's_paradox]Skolem's[/PLAIN] [Broken] (pseudo)paradox.


An introductory text on non-standard calculus (e.g. Keisler's free online text) might be a good practical introduction to notions of "internal" versus "external".

I don't see how downward L-S would let you name all the reals. I don't think anyone claims you can name all the reals, L-S or not. Perhaps I'm wrong. But I'm generally familiar with the reference you linked and I don't see how it implies that you can name all the reals. If there are names and/or algorithms for all the reals, that would pretty much demolish the entire field of algorithmic complexity theory. Nor would anyone have any further need to care about computable or definable sets of numbers.
 
Last edited by a moderator:

Related Threads on Set of real numbers in a finite number of words

  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
4
Views
3K
Replies
5
Views
2K
Replies
7
Views
2K
Replies
4
Views
1K
Replies
3
Views
11K
  • Last Post
Replies
15
Views
12K
Replies
12
Views
7K
  • Last Post
Replies
18
Views
2K
Replies
4
Views
4K
Top