Set of real numbers in a finite number of words

[Deveno]

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

 

[SteveL27]

DevEno. sheesh.

My most humble apologies for misspelling your handle.