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
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.