Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Obviously this is a false proof. It relies on Berry's paradox.

Assume that $\mathbb{N}$ is infinite. Since there are only finitely many words in the English language, there are only finitely many numbers which can be described unambiguously in less than 15 words. Let $n$ be the smallest number which can't.

Then $n$ can be described as "the smallest number which can be described unambiguously in less than 15 words". Contradiction.

I know nothing of mathematical logic, but looking in a few books has told me that the problem here lies in the definition $n$ := "smallest number which can't be described unambiguously in less than 15 words". If this isn't a valid definition, then what exactly is a valid definition?

share|improve this question
1  
The problem is the definition of "described unambiguously" when applied to the English language. There is a way to formalize this argument to show that the Halting Problem is not solvable - if you could solve the Halting Problem, you could write a program to find "The smallest number which is not the output of a program of length $<N$ with input $<N$" and then reach a contradiction much as above. –  Thomas Andrews Jun 25 '12 at 14:01
    
@ThomasAndrews I can accept that the halting problem is not computable, and also that such an $n$ as in my question can't be computed. I don't see why it can't exist, though. –  Cocopuffs Jun 25 '12 at 14:05
1  
This cannot be a valid definition because it's self-referential, which leads to Liar's paradox in the form of Berry's paradox, as you have mentioned yourself. In formal logic, we do not allow formal language to refer to itself, which avoids this kind of problems. –  tomasz Jun 25 '12 at 14:11
3  
Alternatively, "unambiguously describes" is not an unambiguous phrase, so this sentence doesn't "unambiguously describe" a number. –  Thomas Andrews Jun 25 '12 at 14:40
2  
I would actually take issue with the statement that there are only finite many words in the English language, and then migrate this question over to english.stackexchange.com –  Greg L Jun 26 '12 at 2:23

3 Answers 3

up vote 21 down vote accepted

The problem is that you are using the concept of describability in your descriptions, and hence the definition is self-referential and paradoxical. It's much like if I tried to define: $$f(n) = \begin{cases}1 &\text{if }f(n)\text{ is even} \\ 2 &\text{if }f(n)\text{ is odd} \end{cases}$$

This is manifestly a nonsense definition, and the number which you propose to define is nonsense in much the same way: you define the interpretation of a string implicitly in terms of the interpretations of strings, and in such a way that you contradict your own definition.

It is, of course, possible to use self-referential definitions in mathematics, but you need to do some extra work to ensure your definition is both complete and non-contradictory. For a more complete explanation of recursion, and when it does or does not work, you may be interested in this answer.

share|improve this answer
    
I see what you mean. So how exactly does one avoid this sort of thing - is it enough that $f$ not be self-referential? I'm wondering how this might relate with Russell's paradox and precise definitions of what sets are, in particular. –  Cocopuffs Jun 25 '12 at 14:21
1  
But to "define the interpretation of a string implicitly in terms of the interpretations of strings" is not in itself paradoxical. The recursion theorem deals precisely with this sort of situation, and this self-referential kind of definition is common in computability theory. –  Andres Caicedo Jun 25 '12 at 14:21
1  
@Cocopuffs You "avoid this sort of thing" by giving clear meaning to your words. "Described unambiguously" is not clearly defined, and, it turns out what you've really proved is that "described unambiguously" is not something that can be clearly defined to be useful in this sort of proof. –  Thomas Andrews Jun 25 '12 at 14:33
    
@AndresCaicedo: sure, self-reference is not always paradoxical. But it can be so, as my definition of $f$ shows, and we would guess from the paradox here that it is so in this case. –  Ben Millwood Jun 25 '12 at 14:36
3  
@BenMillwood: But that doesn't help us pinpoint what is wrong with the argument. If you just say that self-reference is sometimes paradoxical and sometimes one, the only way to find out whether we did anything wrong is to see whether the conclusion is true or not. That's not really a satisfying way of delineating valid arguments. –  Henning Makholm Jun 25 '12 at 14:58

Essentially what your argument shows here is that "described unambiguously in less than $N$ words" is not itself an unambiguous description -- we can plainly see ambiguity arise in the form of the paradox. This defuses the paradox, because now description itself is not among those we quantify over.

It is of course easy to accuse natural-language phrases of being ambiguous, but the same problem carries over if we attempt to formalize the argument. For example, we could ask for the least natural number $n$ such that for every first-order formula $\phi(x)$ containing less than $20,000$ symbols in the language of basic arithmetic, $\forall x.(\phi(x)\leftrightarrow x=\bar n)$ is false in $\mathbb N$.

The wall we then hit is this: Even though we can represent the formulas $\phi(x)$ themselves inside arithmetic using Gödel numbers, there is no arithmetic formula that expresses the property of being the Gödel number of a true formula. So the number asked for in the previous paragraph is indeed not described by any arithmetic formula.

We can define arithmetic truth if we allow formulas in a stronger language, such as set theory. But that still doesn't produce a paradox, because the language of set theory cannot express set-theoretic truth.

share|improve this answer

Actually, your argument does not say anything about $\mathbf N$. You're only proving that there is no number that cannot be described unambiguously in less than 15 words: the contradiction is between the assumption that there is a smallest $n$ that can't and demonstrating that it can.

share|improve this answer
1  
But there's only finitely many words, say N, and hence at most N choose 15 such descriptions, which is a finite number. –  user29743 Jun 25 '12 at 15:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.