Set of real numbers in a finite number of words

mathman

The original question is about naming real numbers, not jusr integers.

SteveL27

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

By the Well Ordering Principle, the set can be well ordered. Such a set has a first element under the well ordering.

Hurkyl

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

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

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

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

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

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

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

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.

SteveL27

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, 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

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

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

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

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