Posted by Jason Polak on 23. November 2017 · 2 comments · Categories: elementary · Tags:

The smallest number paradox goes like this: consider the natural numbers: 0,1,2,3,… . Each can be specified by a string of characters. For example, “0” itself specifies 0. However, on my computer there are only finitely many bits. Therefore, only finitely many numbers can be specified as a string on my computer. In other words, there are some very huge numbers that just cannot be represented as a string on my computer. Now, the string doesn’t have to be the longhand decimal expansion. For example, I might write “200!” for the number


Because the natural numbers are well-ordered, there exists a smallest natural number $N$ that cannot be specified a a string on my computer. But wait, what about “the smallest natural number that cannot be represented as a string on my computer”? That string describes $N$. So there’s the paradox: I just wrote down a string on my computer specifying a number whose definition is that it cannot be described by any string.

Why is this not paradox? The problem is that the set $X$, defined by “the numbers that cannot be defined by a string on my computer” is just not well-defined. To define $X$, you need to specify in advance a set of valid strings, each of which represents a natural number in a formal system in which the natural numbers can be defined, like ZFC set theory. That’s because no string of characters means anything unless you have a predetermined meaning assigned to it: “43^2” might mean 1849 to a mathematician or 41 to a Python programmer.

Here is an example of such a predetermined meaning: allow valid arithmetic expressions involving only the symbols 0,1,2,3,… for every natural number and addition (“+” symbol), multiplication (“*” symbol), and exponentiation (“^”). In this system “123^5123+5” is a valid string, but “two hundred” is not, even though there is another valid string “200” that represents 200.

Now, “the smallest number that cannot be represented as a string in the aforementioned system on my computer” is a meta-statement that makes sense; this string itself is not valid for representing numbers in our fixed system, and the paradox disappears.


  1. The paradox is also known as Berry’s paradox, discussed by Bertrand Russell.

Leave a Reply

Your email address will not be published. Required fields are marked *