Why is the Berry Paradox a paradox at all?

Question

The Berry Paradox arises from first assigning every combination of 12 english words to an integer and then asking for "the smallest positive integer not definable in fewer than twelve words".

This supposedly creates a paradox because the sentence is 11 words long an references an integer outside of the previously defined domain.

I don't see why this necessarily creates a paradox. Transforming this into mathematical notation, what we have is

• $A - The\ set\ of\ all\ english\ words$
• $X - All\ possible\ tuples\ of\ A $
• $Y - |Y| = |X|, \forall y \in Y, y \in \mathbb{N}, 0 \leq y \lt |X|$
• $f: X \leftrightarrow Y - The\ bijection\ between\ word\ tuples\ and\ integers$

The first part of the paradox is setting up the function $f$.

The second part then says that $\exists x \in X, f(x) \notin Y$.

But this is a direct contradication of what we just constructed. Clearly the 11 word sentence used in the paradox ($x$) has already been accounted for in $X$, and it must have a matching $f(x) \in Y$.

I'm not sure why it matters that this $x$ also has an English meaning. We can model the semantic meaning by the existence of another function $g$ which also maps between word tuples and integers, but it is a very different mapping.

Is the paradox not just a result of carelessly mixing between $f$ and $g$?

Answer 1

I think you are making the paradox more complicated than it is. Assigning numbers to the words is really irrelevant; we are only interested in the sentences' English meanings. Certain numbers can be defined in less than twelve words ("the smallest prime", "the square root of three", etc.). Thus one might want to construct a set out of these numbers. But then this set would contain "The smallest number not definable in fewer than twelve words". This is problematic, in that it becomes a paradox akin to the barber paradox ("the barber that shaves everyone who doesn't shave themselves") or Russel's paradox ("the set of all sets that do not contain themselves").

Answer 2

This question has two parts, an informal part and a formal part.

Informal.

First, the Berry paradox doesn't just concern "some assignment" of numbers to English expressions; the point is that this assignment is specifically, "the number $x$ is uniquely defined by the sentence $S$." It's here - at "uniquely defined" - that the issue of the meaning of a sentence comes into play.

The point is, clearly the sentence "The least positive integer not uniquely defined by some English sentence of length $<n$" uniquely defines some number $x_n$ - there are only finitely many English sentences of length $<n$, after all. But setting $n=100000$ (or rather, just $n$ big enough) leads to a clear paradox.

Formal.

Of course, you might object that "uniquely defines" is vague, and so this paradox doesn't really hit home. That's a perfectly valid response, and - like many paradoxes - part of the takeaway from the Berry paradox is, and should be, "Natural language is silly."

However, this is not capturing the full force of the Berry paradox; let me try to convince you that there is real meat here. I'm going to use the idea behind the Berry paradox to prove an actual theorem of mathematics. (Interesting historical note: the question of whether paradoxes could have any "serious content" was a philosophically contentious issue in the early 1900s - in particular, Wittgenstein would be very displeased with what I'm writing here!)

Let's think about Turing machines - that is, formalized computer programs - and we can define the Kolmogorov complexity of a natural number $n$: $$K(n)=\min\{e: \Phi_e(e)=n\}$$ (here $\Phi_e(n)$ denotes the $e$th Turing machine run on input e). Think of the expression "$\Phi_e(e)$" as uniquely defining some number. Note that every number has a description of the form $\Phi_e(e)$ for some $e$ - given $n$, consider the program which just outputs $n$ on every input. So $K(n)$ is well-defined.

Now think about the map $n\mapsto K(n)$; is this map computable? Well, suppose it were - that is, suppose there were some $e$ such that $\Phi_e(n)=K(n)$ for every $n$. Then - in $PA$ - for any $m$ we can define $$Berry(m)=\min\{i: K(i)>m\};$$ moreover, using $\Phi_e$, we can compute $Berry(m)$. So for some $d$, $\Phi_d(m)=Berry(m)$ for every positive integer $m$.

But now consider $\Phi_d(d)$. On the one hand, clearly $K(\Phi_d(d))\le d$; on the other hand, $\Phi_d(d)=Berry(d)=\min\{i: K(i)>d\}$, so $K(\Phi_d(d))$ must be $>d$. Whoops.

What we've done is give a rigorous proof that a natural function in mathematics - at least, in mathematical logic - is not computable; and a variant of the above argument can prove Godel's incompleteness theorem. Now maybe logic isn't your cup of tea, but to my mind this - the fact that, using the Berry paradox, we can prove new theorems - shows pretty clearly that there is more to the Berry paradox than just confusing some details.