h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

"HenryS, your argument about expressing number in a "short way" doesn't work. Just consider "the smallest number not expresible in a short way". I think you are assuming that the expression describing the number must be somehow canonical."

Is this the issue Marijn brought up?:

"Actually I think it is impossible to write down a number, and then not being able to describe it in some short way."

I took that as meaning that its impossible to write down a number in a clearly defined (but possibly very large) way (eg in decimal with 10^100 digits), then not be able to describe it in a short way (eg on a sheet of paper understandable by a human mathematician).

Is that what you were referring to? Perhaps I misunderstood what Marijn was saying?

I'm not sure I understood what Marijin said apart from the fact that what Marijin expresses is a belief "I think it is ...." whereas I claim to have proved that one can alway write down a number "in a short way" (Suppose not, consider the set of numbers that can't be written down in the a short way, it has a least element which can be described by "the smallest number not expressible in a short way". Contradiction, hence result)

I think the whole paradox arises because of ambiguity about what it means to say that sentence T expresses the natural number n. I argued in my previous post that when we say "sentence T expresses n" we implicitly assume that T describes an algorithm (and the inputs for that algorithm) which outputs the number n. We know that there are algorithms which don't stop and give an output, and we know that in general we cannot tell whether an algorithm will ever stop, so our implicit assumption is invalid, and indeed when we consider the algorithm that S describes we see that to evaluate it must call itself, and so gets stuck in an infinite loop.

Do you agree with me when I say we are implicitly assuming sentences describe algorithms, or can you think of another possible interpretation of the meaning of "sentence T expresses the number n".

Nice

Your proof is really the same paradox again.

I agree that we should really be talking about algorithms (Turing machines even), in which case the paradox disappears because of the halting problem.

Well, perhaps there are things that a human could interpret that could not be phrased in a way a Turing machine could be made for (i.e. is human thought computationally equivalent to Turing machines), but I don't think that's relevant for this paradox. Nothing can give a sensible answer for "the smallest number not expressible in a short way" if whatever is inside those ""s is a 'short way'.

Firstly, a short technical note: "We know that there are algorithms which don't halt" - there are not. In the definition of algorithm, there is a requirement that every algorithm may take only finite number of steps (i.e. it halts for every possible input), see e.g. http://mathworld.wolfram.com/Algorithm.html . You are talking about programs, not algorithms.

As for Turing machines, etc., there is an interesting theorem which is a sort of generalization of the Godel's theorem. It states that, in general, we cannot prove that a program we have created is the shortest possible.
Take a moment to think about the relationship about this theorem and the sentence...

Hmm, we all know Russell's paradox, from which we conclude that there is no universal set. (Assume there is an universal set U, by principle of selection let's define U0 = { x e U : x e! x }, now - is U0 e U0? no matter what you do, it's a contradiction)

Now, Cantor's postulation was this
"For every property FI expressible in human language, there is a set U(FI) = { x : FI(x) }"
This is wrong, since we can suggest FI(x): x=x, which would be true for any element, and then U(FI) would be an universal set, which contradicts what we seen before.

BUT,
Zermelo's postulation is "For every set A, and property FI expressible in human language, there is a set A(FI) = { x e A : FI(x) }". Since the contemporary set theory is the Zermelo-Frankel version, I think this postulation is true. If it's not then stop reading and tell me right away

Now let's take the set N (naturals) as A, and FI(x) = x is unexpressible in less than 100 words, we should obtain FI(x) like above. Every set has an infimum, and FI(x) being a closed set, it's infimum is within the set itself. An infimum within the set is a minimum, thus there is Y = max{ FI(x) }. But now we can express Y as "the minimum of set A(FI(x))", or "the smallest number unexpressible in less than 100 words".

So the paradox holds very well with our current set theory. What's the trick?

The trick is this bit:

"FI(x) = x is unexpressible in less than 100 words"

Maybe this is a property expressible in human language, but its not expressible in logic (I'm pretty sure), which is what you need in Zermelo Frankel set theory. The axiom is something like:

"For every set A, and formula with one free variable F(x), there is a set { x e A : F(x) }".

The formula needs to be expressed in logic, and you hit problems if you try and translate "FI(x) = x is unexpressible in less than 100 words" into logic. I think its going to turn out similar to problems with the halting problem for Turing machines - see post 15 of this thread.

Problem with the paradox lies in the fact that we are directed to think that words and strings of words take on the significance of their own. In fact when I utter a word , I mean no more by it than is conventionally thought this word implies. It is question of conventions.It is a question of simbolism too. One can express in one sentence a concept,which other devotes a book to. Numbers are nothing more than concepts and abstractions ,they do not exist independently of our mind. We can say "one million" or "ten to the power of six" , which is tantamount (two words instead of six , expressing the same concept). The paradox is flawed in a sense that it tends to equate the precision of concept (the number proper)with the vagueness of terminology arbitrarily implemented by human convention to denote the concept. I am firmly on the side of relativist logic as far as this paradox is concerned!

Couldn't the answer to the paradox just not be that there isn't such a number?
It's all about definitions: You could say a combination of words means a numer(like 'this is a sentence'= 5) HOwever, the frase the smallest number... doesn't say how you define your numbers. THe same frase as mentioned above could besides 5 also mean 6, 8 and 12 at the same time. Therefore Any number can be described by any word and therefore in fewer than eleven.
Alternatively, if this isn't allowed and one frase can only have one number attached to it(one to one mapping...) then the paradox itself is flawed: There will be some smallest number that can not be described in fewer than eleven words and is therefore described by the paradox. But then there is the 'next' smallest number which can't be described by the paradox because that already describes a number. And if then the paradox does describe this number then it's not one to one mapping and all the numbers would be describable in fewer than eleven words...
I think anyway...
Rod

The paradox assumes a one-to-many mapping, not a one-to-one mapping.

Thus, a number may be expressed in many ways. Example: 21 can be expressed as "twenty one", "three times seven", "twenty plus one", and many more.

However, if a phrase fits many numbers, such as "an even number", "a number less than seven", and so forth, then that phrase is not "expressing" a number within the framework of the paradox. Thus, it is a one-to-many.

> "the paradox itself is flawed"

Your logic is more a demonstration that the paradox is paradoxical, rather than being "flawed".