Set of real numbers in a finite number of words

[Jano L.]

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

 

[Fredrik]

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

 

[Jano L.]

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

 

[Fredrik]

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.

 

[micromass]

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

 

[lavinia]

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.

 

[Fredrik]

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.

 

[disregardthat]

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.

 

[Jano L.]

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?

 

[SteveL27]

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.

 

[Jano L.]

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.

 

[Fredrik]

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.

 

[Jano L.]

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.

 

[mathman]

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!

 

[Jano L.]

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.

 

[SteveL27]

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.

 

[Deveno]

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

 

[mathman]

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.

 

[SteveL27]

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?

 

[lavinia]

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.

 

[Hurkyl]

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)

 

[SteveL27]

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.

 

[SteveL27]

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.

 

[Hurkyl]

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

 

[SteveL27]

A good starting point would be to read up on http://en.wikipedia.org/wiki/Skolem's_paradox]Skolem's[/PLAIN] (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.

 

[Amir Livne]

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.

Consider a countable model of ZFC, or a countable elementary submodel of your model-of-choice-for-sets. (this exists by Skolen_Lowenheim)

Then you can consider sets as labelled by natural numbers, and then you have 1-1 correspondence between the sets of algorithms (as that term means in the model) to the set of reals (again, reals that are in your submodel). This is the basis of Skolem's paradox.

 

[SteveL27]

Consider a countable model of ZFC, or a countable elementary submodel of your model-of-choice-for-sets. (this exists by Skolen_Lowenheim)

Then you can consider sets as labelled by natural numbers, and then you have 1-1 correspondence between the sets of algorithms (as that term means in the model) to the set of reals (again, reals that are in your submodel). This is the basis of Skolem's paradox.

Yes, agreed. But mathematicians haven't stopped talking about uncountable sets, or started believing that the reals are secretly countable. When someone talks about the uncomputable reals or the undefinable reals, their argument is not immediately dismissed with "Oh everyone knows that Skolem showed there is a countable model of the reals." NOBODY does that.

I am still puzzled by this use of downward Lowenheim-Skolem in this thread. The statement is made that most reals are unnameable. This is because there are only countably many names/algorithms but uncountably many reals.

Then downward L-S is invoked to object that well, actually, secretly, the reals are countable

I have never heard of downward L-S used in this manner, to cut off discussion of the reals being uncountable. It is true that there is a nonstandard model of the reals that is countable, but that model would not be recognizable to anyone as the usual real numbers.

The real numbers are uncountable. Are people in this thread now objecting to that well-known fact on the basis of downward Lowenheim-Skolem? That would be a great misunderstanding of L-S in my opinion.

Is the next undergrad who shows up here to ask, "I heard that the reals are uncountable, I don't understand Cantor's proof," to be told, "Oh, don't worry about it, downward Lowenheim-Skolem shows that the reals are countable."

That would not be mathematically correct.

 

[Amir Livne]

The real numbers are uncountable. Are people in this thread now objecting to that well-known fact on the basis of downward Lowenheim-Skolem? That would be a great misunderstanding of L-S in my opinion.

It is a misunderstanding, but one that is very easy to have.
This is why I referred to Skolem's paradox - even he got mixed up in this logic.

Is the next undergrad who shows up here to ask, "I heard that the reals are uncountable, I don't understand Cantor's proof," to be told, "Oh, don't worry about it, downward Lowenheim-Skolem shows that the reals are countable."

That would not be mathematically correct.

Of course. This thread has gone beyond freshman level, I think, after the OP got an answer that being able to describe a set concisely doesn't mean you can label each of its element concisely.

I was actually trying to clarify Hurkyl's comment about propositions in the meta-language, that can provide a description for objects in the model.

 

[SteveL27]

It is a misunderstanding, but one that is very easy to have.
This is why I referred to Skolem's paradox - even he got mixed up in this logic.
Of course. This thread has gone beyond freshman level, I think, after the OP got an answer that being able to describe a set concisely doesn't mean you can label each of its element concisely.

I was actually trying to clarify Hurkyl's comment about propositions in the meta-language, that can provide a description for objects in the model.

Yes, thanks for clarifying. I am still not understanding Hurkyl's pont. The existence of a nonstandard countable model of the reals in no way invalidates fact that most numbers are not computable due to there being uncountably many reals and only countably many finite-length strings.

I'm just trying to point out that invoking Lowenheim-Skolem is wildly off the mark when it's employed to object to the existence of uncomputable reals.

 

[Deveno]

Yes, agreed. But mathematicians haven't stopped talking about uncountable sets, or started believing that the reals are secretly countable. When someone talks about the uncomputable reals or the undefinable reals, their argument is not immediately dismissed with "Oh everyone knows that Skolem showed there is a countable model of the reals." NOBODY does that.

I am still puzzled by this use of downward Lowenheim-Skolem in this thread. The statement is made that most reals are unnameable. This is because there are only countably many names/algorithms but uncountably many reals.

Then downward L-S is invoked to object that well, actually, secretly, the reals are countable

I have never heard of downward L-S used in this manner, to cut off discussion of the reals being uncountable. It is true that there is a nonstandard model of the reals that is countable, but that model would not be recognizable to anyone as the usual real numbers.

The real numbers are uncountable. Are people in this thread now objecting to that well-known fact on the basis of downward Lowenheim-Skolem? That would be a great misunderstanding of L-S in my opinion.

Is the next undergrad who shows up here to ask, "I heard that the reals are uncountable, I don't understand Cantor's proof," to be told, "Oh, don't worry about it, downward Lowenheim-Skolem shows that the reals are countable."

That would not be mathematically correct.

yes, it is true that there is a "non-standard" model of the reals that is countable. presumably, this is meant to contrast with a "standard" model of uncountably many reals. the trouble is, the "standard model" doesn't exist, at least not in the way people think it does.

what i mean is this: give me an example of a collection of things that satisfy ZFC that includes all sets. i mean, i'd like to know that SOME "version" or "example" of set theory is out there, it would be reassuring. given the group axioms, for example, we can demonstrate that, oh, say the integers under addition satisfy the axioms. it is, to my understanding, an open question whether or not there is a structure, ANY structure, that satisfies the ZFC axioms. at the moment, ZFC appears to describe the class of all sets (let's call this V), and since V is not a set, V is not a model for ZFC (close, but no cigar).

that is to say: it's not logically indefensible to disallow calling any uncountable thing "a set". in this view of things, what cantor's diagonal argument shows is:

there exists collections of things larger than sets (which we certainly know is true anyway).

this is somewhat of a different question than the consistency of the ZFC axioms, although existence of a model would establish its consistency. since great pains have been taken to disallow "inconsistent sets" (the last big push being restricting the axiom of comprehension, for which we previously had great hopes of defining a set purely in terms of its properties), the general consensus is that ZFC is indeed "probably consistent" (it's been some time since anyone has found a "contradictory set").

downward L-S does not show "the real numbers" (with any of the standard constructions) are uncountable, rather, it shows that "the set of real numbers" might not be what we hope it is, in some variant of set theory. indeed the Skolem paradox can be resolved by noting that any model of set theory can describe a larger model, which is what (i believe) current set theory DOES: it shows we can't get by "with only sets", we need a background of things not regulated by the axioms (classes, and larger things).

in other words: there is a deep connection between cardinality, and "set-ness". what cardinals we are willing to accept, determines what things we are willing to call sets. and: what things we are willing to call sets, affects a set's cardinality (cardinality isn't "fixed" under forcing).

1) only finite sets <--> countable universe (first notion of infinity as "beyond measure")
2) countable infinite sets <--> uncountable universe (infinity can now be "completed")
3) uncountably infinite sets <--> strongly inaccessible universe (an infinity beyond all prior infinities)

cantor took step (2) for us, and ever since, we have decided that that pretty much justifies step (3). note that even step (1) is not logically obvious, the axiom of infinity had to be added as an axiom, because we desired the natural numbers to be a set, it does not follow from the other axioms. it is apparently known that (2) is logically consistent, and unknown if (3) is logically consistent (but if (3) is assumed, then (2) follows).

geometrically, the situation seems to be thus: there seems to be a qualitative difference, between "continua" and "discrete approximations of them". the analog and digital worlds are different, although at some levels of resolution, nobody cares.

going back to the real numbers: some mathematicians feel uncomfortable with uncountable sets, including the set (as usually defined) of the real numbers. there are some good philosophical (not mathematical) reasons for feeling this way: most uncountable set elements are "forever beyond our reach", so why use them if we don't need them? perhaps the best answer is that having a wider context (a bigger theory), often makes working in our smaller theory more satisfying: treating "dx" as a hyperreal number, makes proofs about differentiation more intuitive (where we only care about what happens to the "real part").

knowing that sup(A) is a real number, means we can prove things about sets of real numbers in ways that would be difficult, if we had no such assurance. the "background" logic of our set theory (which gets more complicated with uncountable sets) makes the "foreground" logic of the real numbers, easier to swallow.