Proof that $\mathbb N $ is finite

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.