A gift for Frege: the disturbing postcard

We saw some of Cantor's work when we saw the proof of the
non-enumerability of (*N*). Cantor didn't work explicitly
from axioms, but it has been shown that he could have--and
specifically that he could have worked explicitly from three,
one of which is the so-called **axiom of abstraction**, which says
that given any property there exists a set whose members are just
those entities having that property.

Put more formally this axiom amounts to

where

Now for Russell's reasoning. Set (so that we can refer to the set of all those things which are not members of themselves), which gives us

And now, using two steps of elementary quantifier substitution, we can arrive at

which is a contradiction!

First, some short reminders.

We understand an **alphabet** to
be a finite set of symbols

A **string** from some alphabet is a finite sequence of symbols from
that alphabet; e.g., with , the following are
strings:

And we will mean by
(where *A* is some
arbitary alphabet) the set of all strings that can be assembled from
*A* by concatenating zero or more symbols from *A*.

For example, if , then the following strings are elements of :

, needless to say, is always an infinite set (even
when *A* has only one member). Recall that whenever you are
given an alphabet you can order
in a certain ``dictionary-like" way (called a lexicographic
ordering), as follows:

OK, now for the proof. The alphabet we are concerned with is the English alphabet

I may have missed some symbol here, but at any rate everyone knows
that *E*
is finite. Now consider ; and then consider ordered
lexicographically, a progression we'll denote by .

Now, some elements of will define real numbers; some will not. For example, the string

is in , but it doesn't define a real number; but the string

does. And so do the following strings in :

So let us subtract from all the strings that don't define real numbers; we are then left with an ordered set, every member of which does define a real number. Call this new set . That is,

Very well. Now define
a certain real number *N* with respect to as follows:

the real number whose whole part is zero, and whose n-th decimal is p plus one if the n-th decimal of the real number defined by the nth member of E*** is p and p is neither eight nor nine, and is simply one if this n-th decimal is eight or nine

By construction (try to verify it yourself),

since *N* differs from every real number in in at least
one decimal place. However, N is a sequence of symbols from E that
does define a real number given the progression E***. Hence

This is of course a contradiction.

You are encouraged to study this proof until you see that it is at the very lest formidable, to find a solution, and to find someone else (professors, parents, classmates) who can find a solution--if there is one.

Mon Dec 2 23:57:31 EST 1996