Register to reply 
Set of real numbers in a finite number of words 
Share this thread: 
#19
Feb1312, 07:24 PM

P: 800

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
Feb1312, 09:54 PM

Sci Advisor
P: 1,722




#21
Feb1312, 10:19 PM

Emeritus
Sci Advisor
PF Gold
P: 16,091

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
Feb1412, 01:19 AM

P: 800

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
Feb1412, 01:29 AM

P: 800

It seems to me that it's unquestionably the case that there are only countably many finitelength 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 finitelength strings to go around. Of course if you allow infinitelength strings then any real can be named by its decimal expansion. But infinitelength strings defeat the intuitive meaning of an algorithm. 


#24
Feb1412, 08:02 AM

Emeritus
Sci Advisor
PF Gold
P: 16,091

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


#25
Feb1412, 01:14 PM

P: 800




#26
Feb1512, 06:40 AM

P: 38

Then you can consider sets as labelled by natural numbers, and then you have 11 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. 


#27
Feb1512, 11:06 AM

P: 800

I am still puzzled by this use of downward LowenheimSkolem 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 LS is invoked to object that well, actually, secretly, the reals are countable I have never heard of downward LS 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 wellknown fact on the basis of downward LowenheimSkolem? That would be a great misunderstanding of LS 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 LowenheimSkolem shows that the reals are countable." That would not be mathematically correct. 


#28
Feb1512, 11:49 AM

P: 38

This is why I referred to Skolem's paradox  even he got mixed up in this logic. I was actually trying to clarify Hurkyl's comment about propositions in the metalanguage, that can provide a description for objects in the model. 


#29
Feb1512, 11:55 AM

P: 800

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


#30
Feb1512, 12:42 PM

Sci Advisor
P: 906

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 LS 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 "setness". 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. 


#31
Feb1512, 06:40 PM

P: 800

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 finitelength 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 nonsequitur 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 LowenheimSkolem. 


#32
Feb1512, 09:11 PM

Sci Advisor
P: 839




#33
Feb1512, 09:17 PM

Sci Advisor
P: 1,722

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. 


#34
Feb1512, 09:20 PM

P: 800

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


#35
Feb1512, 10:06 PM

Sci Advisor
P: 839

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. 


#36
Feb1512, 10:10 PM

Sci Advisor
P: 906

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 semirelevant 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 "openended" 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 helterskelter with it, using classes (!) as "singleobjects" 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 bathwater" 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 ontopic, 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 nonempty. as a nonempty 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. selfreference 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 "metalevel" (because both use the same "terms"). it's really hard to "untangle" 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 "selfviolating 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 "recompressing" 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 