0
$\begingroup$

I was on /r/math the other day and I saw a "proof" that interested me. I slightly modified it to make it less convoluted.

Consider the statement "the smallest natural number that is not described by this statement". We prove that every natural number can be uniquely described by this statement. Assume, on the other hand, that not every natural number can be uniquely described by this statement. Then there must be the smallest such number n. But n can be uniquely described by the statement "the smallest number that is not described by this statement", which is a contradiction. Therefore every natural number can be uniquely described by this statement.

This is obviously incorrect, but I'm having trouble pinpointing exactly where the proof goes wrong.

Here's what I think: the trouble lies in the definition of the word "describe," which is a vague term. A natural definition for "describe" with respect to a statement S would be to regard the statement S as a collection of objects (intuitively, the collection of objects are the things that S describes). Regarding the statement "the smallest natural number that is not described by this statement" as a collection of objects in this manner, we simply prove that such a collection can never exist. Thus, the statement is incompatible with the word "describe" and the question is rendered meaningless.

But I feel like there's something wrong in my explanation. What if the statement was instead "a collection of objects that does not contain itself"? Then if we similarly regard this statement as the collection of objects it describes, this collection would be exactly the collection of collections of objects that do not contain themselves, and we run into Russel's Paradox.

TL;DR I'm lost on how to resolve this seemingly paradoxical proof in a satisfying way.

$\endgroup$
  • 1
    $\begingroup$ You are right that it is on the vagueness of the word "described" that this paradox hinges. A random redditor will not have been the first person to think of this. See this wikipedia article. $\endgroup$ – Arthur Mar 3 at 20:16
  • $\begingroup$ Assuming even the most liberal definition of describe wouldn't make the statement describe a number. You might as well say "The smallest natural number not jumped over by this statement." $\endgroup$ – Matt Samuel Mar 3 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.