Go up to Every Natural Number can be Unambiguously Described in Fourteen Words or Less

Switch to text-only version (no graphics)

Go to University of Toronto Mathematics Network Home Page

Any sentence that tries to make claims about itself runs the risk of
being logically inconsistent. The classic example is the liar's
paradox "*this sentence is false*".

The problem in this case is the following phrase (let's call it *S*):

the smallest natural number that cannot be unambiguously described in fourteen words or less.

This means that *S* cannot be considered as a self-consistent
description of any natural number. This, however, does not mean that
the number *n* (in the proof) does not exist! There *is* such a number
*n*, and *n* *is* the smallest natural number that cannot be
unambiguously described in fourteen words or less; it's just that the
phrase "the smallest natural number that cannot be unambiguously
described in fourteen words or less" is not a description of it (in
the sense that is being used in the proof), because it is a phrase
that cannot be self-consistently asserted about any number.

Therefore, step 4 of the proof (which mistakes the self-inconsistent
nature of *S* with a mathematical contradiction arising from the
existence of *n*) is at fault.

This is also related to Russell's Paradox in set theory: there is no
such thing as the "set of all sets" (if there were, you could look
at "the set of all sets that do not contain themselves". Let *S* be
this set. Does *S* contain itself, or not? Either way leads to a
contradiction).

Finally, although this particular proof is fallacious,
it illustrates a common proof technique which, when used
correctly, is very powerful: the
*well-ordering principle*.

If you want to show that something is true for all natural numbers
*n*, one way to do it (which is mathematicall equivalent to a proof by
induction but is sometimes more convenient than it) is to reason as follows:

Suppose it's not the case that the statement in question is true for all.n. Then there is a smallestnfor which it fails. But this leads to a contradiction because . . . . Therefore, it must indeed be the case that the statement in question is true for alln.

Proofs that follow this pattern are using the well-ordering principle (which says that any non-empty set of natural numbers must have a smallest element), and this is a very common and powerful pattern of proof. When used correctly, that is.

This page last updated: May 26, 1998

Original Web Site Creator / Mathematical Content Developer: Philip Spencer

Current Network Coordinator and Contact Person: Joel Chan - mathnet@math.toronto.edu