15
$\begingroup$

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?

  • 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 $ with input $" and then reach a contradiction much as above.2012-06-25
  • 0
    @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.2012-06-25
  • 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.2012-06-25
  • 0
    There is an important difference between a mathematical statement and a statement *about* math (meta-mathematical). When you conflate the two you get issues.2012-06-25
  • 0
    @Cocopuffs That's why I didn't make this an answer, just a comment - it is a lovely example of a verbal paradox which, when you try to make it rigorous, yields a nice result.2012-06-25
  • 3
    Alternatively, "unambiguously describes" is not an unambiguous phrase, so this sentence doesn't "unambiguously describe" a number.2012-06-25
  • 0
    There is a paradox but how it is related to in finiteness? It will work for a finite set also.2012-06-25
  • 0
    @Anixx No, it doesn't, because the set of numbers that can be expressed in 15 words or less might be all the natural numbers, so there there wouldn't be a least counter-example.2012-06-25
  • 0
    @Thomas, Anixx is correct: the argument "works" for any finite set guaranteed to have greater cardinality than the set of English words. Even if one cannot even agree on what the set of English words is, I think there would be general agreement that the set of *existing* English words is no greater than, say, $26^{100}$.2012-06-25
  • 0
    Ah, I read "for a finite set" as "for *any* finite set," not "for some finite set." @whuber2012-06-25
  • 0
    @Thomas I thought as much--there's no difference of opinion here, just different interpretations of English. I would like to clarify that in my previous comment I should have referred to the cardinality of all *descriptions* that can be made with $15$ English words, which will be far less than (say) $(26^{100})^{15}$.2012-06-25
  • 4
    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.com2012-06-26
  • 0
    @GregL: The question is mathematical. If you want, feel free to ask on English.SE whether or not analysts of the English language consider there to be only finitely many words in English, but the question could just as easily be about English${}'$, a fictional language with only finitely many words. The crux of the question is about the mathematical issue of self-reference.2012-06-26
  • 0
    @GregL I suppose I only considered words that have ever been used before, not words which might theoretically be constructed2012-06-26

3 Answers 3

22

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.

  • 0
    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.2012-06-25
  • 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.2012-06-25
  • 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.2012-06-25
  • 0
    @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.2012-06-25
  • 0
    @AndresCaicedo: I just edited the last sentence in a way that I hope addresses your concerns. The problem is not that you introduce recursion, it's that you do so in a contradictory fashion, like my definition of $f$ does.2012-06-25
  • 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.2012-06-25
  • 0
    @HenningMakholm: No, there's a better way to establish whether we did anything wrong, I just didn't elaborate on it in the answer because it's a bit fiddly. Interpret recursive definitions as defining an operator on partial functions that takes an approximation to the function and gives a better approximation. The recursion makes sense if this operator has a fixed point. My $f$ corresponds to an operator with no fixed points, and likewise if you formalise the notion of describability used in the question as a function from strings to maybe-numbers, it doesn't have a fixed point either.2012-06-25
  • 0
    @HenningMakholm: I linked to another answer which gives a fuller explanation of when recursion does or does not work.2012-06-26
  • 0
    It's not clear to me that there is any recursion going on at all here. The basic problem is that "described unambiguously" cannot be formalized in the same language as the descriptions it speaks about -- but that problem doesn't seem to fit well into the shape of a recursive definition. (Also, the answer you link to seems eerily familiar to me ...).2012-06-26
  • 0
    @HenningMakholm: suppose there is a function that for each string gives the number that it describes, if it describes one unambiguously, or gives the string "nope" if it doesn't. This function must be defined recursively, since strings may refer to descriptions. The paradox arises when you construct a string such that its description refers to itself, in such a way that the corresponding $\Phi$ cannot possibly have a fixed point, and hence the recursion can have no solution. I suppose this proves that "described unambiguously" cannot be formalised, since to do so would allow this paradox.2012-06-26
  • 0
    @HenningMakholm: I suppose your answer is technically more correct, or at least more precise and detailed, than mine. But mine provides an intuitive example of the phenomenon whereby just because you can provide a seemingly-valid description, doesn't mean it corresponds to any mathematical object. I believe that the analogy between my $f$ as a syntactically valid description that is nevertheless meaningless because it refers to itself in contradictory ways, and the notion of describing a number in terms of descriptions themselves, is a reasonable one.2012-06-26
  • 0
    As usual, Henning is right here. I think this answer sweeps all the interesting issues under the carpet. For example, the implication that self-referential definitions are paradoxical is just plain silly; mathematics is full of self-referential definitions such as "the negation of a statement is false if the statement is true", which is itself a statement, or "a natural number is either zero or the successor of some natural number".2012-09-03
  • 0
    @MJD: of course; like I said in the comments, I didn't mean to imply that self-reference was *always* bad, just that it could be a source of problems. I've edited the answer in an attempt to clarify this.2012-09-04
13

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.

1

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.

  • 1
    But there's only finitely many words, say N, and hence at most N choose 15 such descriptions, which is a finite number.2012-06-25