Here are three paradoxes, all based on the same idea.

1. Let A be the set of all positive integers that can be defined in under 100 words. Since there are only finitely many of these, there must be a smallest positive integer n that does not belong to A. But haven't I just defined n in under 100 words?

2. Let B be the set of all reasonably interesting positive integers. Let n be the smallest integer not belonging to B. But surely the defining property of n makes it reasonably interesting.

3. Let X be the set of all definable real numbers. Since there are only countably many definitions, X is countable. Indeed, we can explicitly count X - just list the elements in alphabetical order of their definitions. Now apply to this list some explicit diagonal process, obtaining a number y that does not belong to X. But haven't I just defined y?

The solution to these paradoxes is usually explained as follows: they depend on being imprecise about what is meant by defining a number, or being interesting. Consider for example the third paradox, known as Richard's paradox. Suppose you specify an exact set of rules T that tells you (i) which strings of symbols define real numbers and (ii) which numbers they define when they do. Let us call a number x T-definable if there exists some string that defines x according to the rules T. Then there is no particular reason to suppose that the diagonal element y is T-definable, since it depends on the complicated process of arranging all T-definitions in alphabetical order, and it is not at all obvious how the rules T could themselves determine which strings were T-definitions.

To kill off the paradox completely, one has only to
look at the argument in more detail. It will then become
clear exactly why the element y cannot be T-definable, and
hence why the rules T * cannot * specify which
strings are T-definitions.

Let us assume, then, the reverse, i.e., that the rules T
tell us which strings are T-definitions and which real numbers
are defined by those that are. Let us assume also
that the rules are sufficiently powerful to tell us which strings
precede which others in alphabetical order. (Without this second
assumption the paradox doesn't really get off the ground.) Write S for
the set of finite strings and R for the set of real numbers. We are
assuming that the rules T specify which strings T-define which numbers.
To make this more precise, let us suppose the function f:SxR-- > {0,1},
which takes (s,x) to 1 if the string s defines the real number x and
0 otherwise, is T-definable. Now, assuming again that T isn't
hopelessly weak, I can T-define the list to which we shall apply
a diagonal process. I could do it, for example, as follows.
First, I T-define a function g:S-- > {0,1} by setting g(s)=1
if and only if there exists x such that f(s,x)=1.
Then I T-define s_{m} to be the m^{th} string
in alphabetical order. Next, I T-define h(m) to be the sum of
g(s_{k}) over all k at most m. Then I T-define m(n) to
be the minimal m such that h(m)=n. Finally, I T-define x_{n}
to be the real number T-defined by the string s_{m(n)}.

In words, s_{m(n)} is the n^{th} string that
makes T-sense, and this notion itself makes T-sense because the function
f is T-definable (by hypothesis) and hence so is g. x_{n} is
the real number defined by s_{m(n)}.

Now I apply an explicit, T-definable, diagonal argument to the
list x_{1},x_{2},x_{3},... obtaining the
number y. This of course gives a contradiction, since y is both
T-definable and not T-definable. We could simply stop at this point
and say that what we have contradicted is the hypothesis that the
function f could be T-defined. However, it is instructive to see
exactly where the argument breaks down. So let us imagine that
we are trying to produce the diagonal number y and see what
happens.

As is usual with this sort of argument, the problem
arises when we find ourselves faced with the string that is
supposed to T-define y. Since, assuming f to be T-definable,
y is also T-definable, there must be some string s that
T-defines y, and we eventually get to it on our list. Let
us suppose that s is the n^{th} string that T-defines
a real number. What real number does it define? On the one
hand, it defines y=x_{n}. On the other hand, it T-defines
a number which differs from each x_{k} in the
k^{th} decimal place. In particular, it differs from
y in the n^{th} decimal place.

Thus, from the assumption that f is T-definable, we arrive at the absurd conclusion that there is some string s that defines two distinct real numbers. To put this another way, if definability is itself definable, then it is also ambiguous.

Even after one understands the above argument, it is still
tempting to think along the following lines: yes, the paradoxes
go away if one is precise about what is meant by `definable',
but, given any precise notion T of definability, we can always
stand outside it and * genuinely understand * the definition
of a number, even if it is not T-definable. For example, if I
grasp the definition of T-definable, then I will grasp the
definition of the non-T-definable number y produced by a
diagonalization process. Could we not obtain a paradox as
follows?

4. Let X be the set of all real numbers that can be defined,
not necessarily according to some formal system, but just in
some unambiguous way that any mathematically trained person could
in principle understand. (Such a number might, for example, be
defined as the result of a diagonal argument applied to the
T-definable numbers, where T was some previously specified
formal system.) Now list all the unambiguous definitions in
alphabetical order and let x_{n} be the real number
defined by the n^{th} one. Construct a number y not in X, by
letting the n^{th} digit of y be 4 if the n^{th}
digit of x_{n} is 7 and 7 otherwise. But surely
you have now understood the definition of y.

Well, you may think you have, but you haven't, as you will
rapidly see if you imagine trying to work out the first few
digits of y (over the course of the next 10^{1000} years,
say). At some point you will reach the n^{th} supposedly
unambiguous string, consisting of the following definition:

Let X be the set of all real numbers that can be defined,
not necessarily according to some formal system, but just in
some unambiguous way that any mathematically trained person could
in principle understand. (Such a number might, for example, be
defined as the result of a diagonal argument applied to the
T-definable numbers, where T was some previously specified
formal system.) Now list all the unambiguous definitions in
alphabetical order and let x_{n} be the real number
defined by the n^{th} one. Construct a number y not in X, by
letting the n^{th} digit of y be 4 if the n^{th}
digit of x_{n} is 7 and 7 otherwise.

What is the n^{th} digit of y? It is 7 if and only
if it is not 7. This is obviously a bit of a problem, and we
are forced to conclude that, despite appearances, we have * not
* just defined a real number unambiguously. After all, an
unambiguous definition ought to leave us in no doubt about what the
n^{th} digit is.