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

7886578673647905035523632139321850622951359776871732632947425332443594499
6340334292030428401198462390417721213891963883025764279024263710506192662
4952829931113462857270763317237396988943922445621451664240254033291864131
2274282948532775242424075739032403212574055795686602260319041703240623517
0085879617892222278962370389737472000000000000000000000000000000000000000
0000000000

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.