The G.G. Berry paradox (...)

[Kyriakos]

Well, I am not reading this for itself, but for something else. However first I had to read it, so I thought of presenting my impressions... It is something first mentioned in a letter by Bertrand Russell.


You can read what this is in the wiki page (https://en.wikipedia.org/wiki/Berry_paradox).

Consider the expression:


"The smallest positive integer not definable in under sixty letters".

So, we have an expression according to which there is a smallest positive integer not definable in under sixty letters. Assuming this is so, the paradox goes to state that:

But the above expression is only fifty-seven letters long, therefore it is definable in under sixty letters, and is not the smallest positive integer not definable in under sixty letters, and is not defined by this expression. This is a paradox: there must be an integer defined by this expression, but since the expression is self-contradictory (any integer it defines is definable in under sixty letters), there cannot be any integer defined by it.

So, while the expression numbers 57 letters, it states that there is a smallest positive integer which cannot be defined in less than 60 letters. Therefore while it refers to such a number, it goes against the rule that anything which defines such a number must have had at least 3 more letters and furthermore it does not actually present the number itself (although it refers to it). The apparent paradox is about the first part: if such a number exists (ie if the statement is true) then such a number is already referred to by less letters than the statement claims (so the statement is false).




The issue here is that (due to lack of a strict definition of "definable", allowing for use both in and outside the original expression), one can claim that the expression "The smallest positive integer not definable in under sixty letters" is itself a definition of a specific integer (if it exists) and at the same time a statement that such a (smallest) integer exists. Now, due to numbering less letters than 60, it fails as a definition if it is taken as both a reference to a specific number and a claim about its existence.
Ultimately, the "paradox" has to do with the need to identify the statement as using another level of "definition" inside of the statement itself, and outside of the statement (when referring to an actual number).


Apparently some luckier countryman of mine (G. Boolos, of Mit) used this paradox as the basis of a faster/simpler proof of Gödel's incompleteness theorem, which is why I bothered with it. Unfortunately for me I had to first look it up, given it was mentioned already in the second sentence of his paper