Analysis for Realsies: 1

If you were in one of my B-tutorials last week, you might recall this little "wrong" proof:

Claim: Every natural number can be unambiguously described in fourteen words or fewer.

Proof: (let's break this up into steps) We're going to attempt a proof by contradiction.
1) Assume that there exists a natural number \(n\in\mathbb{N}\) that cannot be unambiguously described in fourteen words or fewer.
2) Then (by the well-ordering principle), there is a smallest number \(n_0\in\mathbb{N}\) that cannot be unambiguously described in fourteen words or fewer.
3) Then, \(n_0\) is "the smallest natural number that cannot be unambiguously described in fourteen words or fewer".
4) But this is an unambiguous description of \(n_0\), thus contradicting our initial claim that there exists a natural number that cannot be unambiguously described in fourteen words or fewer.

...Q.E.D.???

Now, there's something that feels pretty darn wrong about this "result" - after all, if I write down an epically epically HUGE number, I shouldn't expect to be able to unambiguously express it in fewer than fifteen words. I mean, this English language is finite, and the number of sentences that you can build with fourteen words is finite, but the number of natural numbers is infinite. So, the claim is totes wrong.

But where does it go wrong?

And the answer is kinda subtle...the problem at the heart of this proof is the following description:

(*): "the smallest natural number that cannot be unambiguously described in fourteen words or fewer",

whilst it certainly intuitively makes sense to us as a description, it is self-referential, and you've already seen from class what can happen if you allow for self-referential statements: Russell's Paradox! In particular, in our case, assigning this description to a number contradicts the very description: it's totes logically inconsistent.

So, we see that in step 4), we can't actually conclude that we've contradicted our initial assumption; all we've done is shown that (*) is a sucky sucky description.

Logic, fo'shizzle and stuff.

=)