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

Switch to graphical version (better pictures & formulas)

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):

S refers to itself (because it makes claims about descriptions of numbers, and S is such a description). Moreover, it does so in a logically inconsistent fashion: if you try to apply the description S to a number, then it ends up stating that S does not apply to that number.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 smallest n for 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 all n..

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

Navigation Panel: Up | Graphical Version | U of T Math Network Home