Berry paradox

December 2, 2010

« [Natural] numbers can of course be interesting in a variety of ways. The number 30 was interesting to George Moore when he wrote his famous tribute to “the woman of 30”, the age at which he believed a married woman was most fascinating. To a number of theorists 30 is more likely to be exciting because it is the largest integer such that all smallest integers with which it has no common divisor are prime numbers… The question arises: are there any uninteresting numbers? We can prove that there are none by the following simple steps. If there are dull numbers, we can then divide all numbers into two sets — interesting and dull. In the set of dull numbers there will be only one number that is smallest. Since it is the smallest uninteresting number it becomes, ipso facto, an interesting number. » ~ “A collection of tantalizing fallacies of mathematics”, M. Gardner, Scientific American 1958.

Berry paradox. Let S be the set of all positive integers that cannot be described with less than 11 words. By the well-ordering principle, S must have a smallest element s. But s can be defined by the string “The smallest positive integer not definable in under 11 words”, which has less than 11 words, a contradiction.

%d bloggers like this: