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.