Set of real numbers in a finite number of words


by Jano L.
Tags: finite, number, numbers, real, words
SteveL27
SteveL27 is offline
#19
Feb13-12, 07:24 PM
P: 799
Quote Quote by mathman View Post
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
lavinia is offline
#20
Feb13-12, 09:54 PM
Sci Advisor
P: 1,716
Quote Quote by SteveL27 View Post
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
Hurkyl is offline
#21
Feb13-12, 10:19 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
Quote Quote by Fredrik View Post
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
SteveL27 is offline
#22
Feb14-12, 01:19 AM
P: 799
Quote Quote by lavinia View Post
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
SteveL27 is offline
#23
Feb14-12, 01:29 AM
P: 799
Quote Quote by Hurkyl View Post
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
Hurkyl is offline
#24
Feb14-12, 08:02 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
Quote Quote by SteveL27 View Post
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 Skolem's (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
SteveL27 is offline
#25
Feb14-12, 01:14 PM
P: 799
Quote Quote by Hurkyl View Post
A good starting point would be to read up on Skolem's (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
Amir Livne is offline
#26
Feb15-12, 06:40 AM
P: 38
Quote Quote by SteveL27 View Post
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
SteveL27 is offline
#27
Feb15-12, 11:06 AM
P: 799
Quote Quote by Amir Livne View Post
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
Amir Livne is offline
#28
Feb15-12, 11:49 AM
P: 38
Quote Quote by SteveL27 View Post
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.

Quote Quote by SteveL27 View Post
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
SteveL27 is offline
#29
Feb15-12, 11:55 AM
P: 799
Quote Quote by Amir Livne View Post
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
Deveno is offline
#30
Feb15-12, 12:42 PM
Sci Advisor
P: 906
Quote Quote by SteveL27 View Post
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.
SteveL27
SteveL27 is offline
#31
Feb15-12, 06:40 PM
P: 799
Quote Quote by Deveno View Post
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).
I'm far from an expert on this subject, but isn't Godel's constructible universe a model of ZFC?

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

In any event, the discussion of alternate models of ZFC is not the point here.

The thread was originally about the claim that there exist real numbers that can not be finitely described.

The usual proof of that fact is to note that the set of finite-length strings over a countable alphabet is countable; and since the reals are uncountable, it follows that all but countably many reals reals cannot possibly be finitely described or characterized by algorithms.

I don't know ANYONE who would respond to that by saying, "Oh yeah? Well there are countable models of the reals, and anyway we don't even know what the reals are."

That is a complete non-sequitur response to the observation that the reals are uncountable.

Is anyone here -- Devano or Hurkyl or anyone else -- claiming that the reals aren't uncountable after all, so that perhaps all real numbers are constructible? That would be a gross abuse of downward Lowenheim-Skolem.
pwsnafu
pwsnafu is online now
#32
Feb15-12, 09:11 PM
Sci Advisor
P: 777
Quote Quote by SteveL27 View Post
Is anyone here -- Devano or Hurkyl or anyone else -- claiming that the reals aren't uncountable after all, so that perhaps all real numbers are constructible? That would be a gross abuse of downward Lowenheim-Skolem.
I think what people are trying to say is that non-computable real numbers cannot be defined in first order logic (of say RCF or ZF). For example Chaitin's constant is an infinite sum, to show that its a well defined real number you need monotone convergence, which in turn needs LUB.
lavinia
lavinia is offline
#33
Feb15-12, 09:17 PM
Sci Advisor
P: 1,716
Quote Quote by SteveL27 View Post
I'm far from an expert on this subject, but isn't Godel's constructible universe a model of ZFC?

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

In any event, the discussion of alternate models of ZFC is not the point here.

The thread was originally about the claim that there exist real numbers that can not be finitely described.

The usual proof of that fact is to note that the set of finite-length strings over a countable alphabet is countable; and since the reals are uncountable, it follows that all but countably many reals reals cannot possibly be finitely described or characterized by algorithms.

I don't know ANYONE who would respond to that by saying, "Oh yeah? Well there are countable models of the reals, and anyway we don't even know what the reals are."

That is a complete non-sequitur response to the observation that the reals are uncountable.

Is anyone here -- Devano or Hurkyl or anyone else -- claiming that the reals aren't uncountable after all, so that perhaps all real numbers are constructible? That would be a gross abuse of downward Lowenheim-Skolem.
Nicely put.

It also seems to me that if one assigns names to real numbers and uses up all possible finite length words then the paradoxes don't hold. For suppose you have a well ordering of those numbers that were unnamed. Then we say there is a first one and therefore that it is supposedly named.

First of all there is no specific number that we know of. So there is no number that we can identify to give a name to.

Second even if we agreed that we could somehow locate this number - we could not uniquely name it since all possible names would have already been used up.
SteveL27
SteveL27 is offline
#34
Feb15-12, 09:20 PM
P: 799
Quote Quote by pwsnafu View Post
I think what people are trying to say is that non-computable real numbers cannot be defined in first order logic (of say RCF or ZF). For example Chaitin's constant is an infinite sum, to show that its a well defined real number you need monotone convergence, which in turn needs LUB.
Ah, that's a good point.

But the definable numbers are those reals that can be defined by FLO.

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

And it's not too big a stretch from "definable" to "can be expressed in a finite number of words." So I think the basic discussion applies. Uncountably many reals aren't first-order definable.

The limit of my knowledge of all this is that I'm unclear on the distinction between computable and definable. I believe Chaitin's constant is definable but not computable. Someone may have linked to Chaitin earlier in this thread.

http://en.wikipedia.org/wiki/Chaitin's_constant
pwsnafu
pwsnafu is online now
#35
Feb15-12, 10:06 PM
Sci Advisor
P: 777
Quote Quote by SteveL27 View Post
But the definable numbers are those reals that can be defined by FLO.

http://en.wikipedia.org/wiki/Definable_real_number
My interpretation is that definable numbers means there exists a formula in FOL which the number satisfies, but you can't necessarily guarantee that the number exists in the first place with just FOL of RCF.

Edit: I shouldn't have used "defined" in my previous post. What I want is "provable existence". Just because a formula exists which the number is supposed to satisfy, you still need to show that it really is an element of R.
Deveno
Deveno is offline
#36
Feb15-12, 10:10 PM
Sci Advisor
P: 906
Quote Quote by SteveL27 View Post
I'm far from an expert on this subject, but isn't Godel's constructible universe a model of ZFC?

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

In any event, the discussion of alternate models of ZFC is not the point here.

The thread was originally about the claim that there exist real numbers that can not be finitely described.

The usual proof of that fact is to note that the set of finite-length strings over a countable alphabet is countable; and since the reals are uncountable, it follows that all but countably many reals reals cannot possibly be finitely described or characterized by algorithms.

I don't know ANYONE who would respond to that by saying, "Oh yeah? Well there are countable models of the reals, and anyway we don't even know what the reals are."

That is a complete non-sequitur response to the observation that the reals are uncountable.

Is anyone here -- Devano or Hurkyl or anyone else -- claiming that the reals aren't uncountable after all, so that perhaps all real numbers are constructible? That would be a gross abuse of downward Lowenheim-Skolem.
DevEno. sheesh.

Godel's constructible universe is an inner model of ZFC, the only problem with calling it a model of ZFC, is that it itself (i think it's usually called L) is "too big" to be a set. i mean, the "standard" take on things, is to assume that V (the set universe) is a model of ZFC (a structure for which all the axioms of ZFC hold), but it's really not a model per se, because it's not a set.

it's semi-relevant here, because if one is a minimalist, and only accepts those sets whose existence is necessitated by the axioms, one only has to accept countable sets (since the axiom of infinity requires the existence of one such set).

i certainly am not claiming the reals are uncountable. what i AM claiming, is that it is not quite "certain" that uncountably infinite collections deserve the term "set". it's a question of how "open-ended" you want your set theory to BE. cantor's famous diagonal argument shows that the power set is "bigger" than the original set...the decision of where to draw the line of "set size" (if indeed we draw one at all) is not forced upon us by nature, and only hinted at by logic. i'm ok with "big sets", personally, because certain algebraic constructions (ring ideals come to mind, as do bases for function spaces) need "big sets" (certainly category theory takes the idea of "big collections" and runs helter-skelter with it, using classes (!) as "single-objects" and considering mappings between them).

yes, it's strange entertaining such ideas, because certainly mathematicians had in mind subsets of the reals (such as open intervals) when the notion of set was gaining popularity. and i'm not a "throw the baby out with the bath-water" kind of guy. but i do like keeping my options open...i don't believe that "true is true", i believe that truth is a relative (contextual) concept. it's certainly worth considering what our foundational assumptions entail. it makes our choices more informed.

to elucidate a bit: when we say that the reals are uncountable, what we really mean is:

there is no bijection (indeed, no surjection) from N to R. the mapping itself (that either exists, or doesn't) is "carrying all the weight". if one stops and thinks about it, one realizes a function is just a certain kind of set, and so when one says:

there is no bijection....

what one means might be ambiguous:

a) there is no mapping that is bijective, at all, of any kind, as any sort of "morphism" whatsoever

b) such a mapping, if it exists, is "outside" of our theory (perhaps because as a set, it is "too big").

the whole point of the "Skolem paradox" is that people, even smart people, get (a) and (b) confused.

in any case...back on-topic, the classic statement is:

x = "The smallest positive integer not definable in under eleven words"

the numbers of words that exist are finite, and the positive integers are infinite, so the set of positive integers not definable in under eleven words is non-empty. as a non-empty subset of the positive integers, it possesses a smallest element, x, under the usual ordering of the integers. but, by construction, x is thereby defined in ten words.

the problem, of course, is that the definition of x is impredicative, in the worst possible way: it is only defined, if it is NOT that which it is defined as. self-reference is a b...erm, witch, not to be played with lightly. our "definition" (or definability condition), contains the word "definable", causing a very nasty sort of recursion. we're confusing "level" and "meta-level" (because both use the same "terms"). it's really hard to "un-tangle" these kinds of things, especially when linguistics and syntax get "put on the wrong layers".

as it turns out, there's no way to actually compute the minimum number of words needed to define every possible positive integer, as the problem is "too complex". and if we could, we could create an endless stream of "self-violating definitions" all of which encode the idea of x above. in essence, we could reduce the complexity of any system to a simpler one, by continually "re-compressing" the data, leading (at its rediculous extreme) to "nothing encoding everything".

in general:

some expressions can be encoded by simpler ones....and, more importantly:
some expressions can only be encoded by others at least as complicated.

for example, we can replace "1+1" by "2", but we can't replace "1" with a shorter string that still captures the same information (although a longer one, such as {∅} is fine).


Register to reply

Related Discussions
Given any real numbers a and b such that a<b, prove that for any natural number n... Calculus & Beyond Homework 9
Show that if a, b are real numbers with a < b, then there exists a number x ∈ 2 I wit Calculus & Beyond Homework 1
Between any two distinct real numbers there is a rational number Calculus & Beyond Homework 3
proving that a real number exists in between a real number, Calculus 19
It's only words...and numbers...2 in 1 General Discussion 2