Question

Let S be the set of all natural numbers that are describable in English words using no more than 50 characters (so, 240 is in S since we can describe it as “two hundred forty”, which requires fewer than 50 characters). Assuming that we are allowed to use only the 27 standard characters (the 26 letters of the alphabet and the space character), show that there are only finitely many numbers contained in S. (In fact, perhaps you can show that there can be no more than 27⁵⁰ elements in S). Now, let the set T be all those natural numbers not in S. Show that there are infinitely many elements in T. Next, since T is a collection of natural numbers, show that it must contain a smallest number. Finally, consider the smallest number contained in T. Prove that this number must simultaneously be an element of S and not an element of S – a paradox!

Answer 1

Let us consider N, which is the set of all Natural Numbers. The cardinality of the set is infinite and hence there are a countably infinite number of elements in this set.

Now, the set S is defined to consist of elements that are describable in English words with no more than 50 characters. Each of the characters can be either of 27 possibilities and this also includes a space. Therefore, a random arrangement of these characters can give rise to 27^50 combinations. Several of them will not be meaningful and hence, the maximum number of natural numbers that belong to S will be less than 27^50 which is a finite number.

Now, the set T has all the natural numbers that are not in set S. Therefore, T is a complementary set of S. Taking out finite numbers from an infinite set, still leaves infinite numbers and hence there are infinite elements in set S.

Lastly, natural number set has a smallest number i.e. 0. This number belongs to set S. We can continue counting upwards until we reach a number that requires more than 50 letters to describe and hence will belong to set T. This will be the first element of set T and also will be the smallest element in T. However, this number X which cannot be described with 50 characters can also be described as "smallest element of T". This phrase is an element of set S and hence the smallest number in T does indeed belong to S.

Therefore, this is a paradox.