next up previous
Next: About this document

A gift for Frege: the disturbing postcard tex2html_wrap_inline48

We saw some of Cantor's work when we saw the proof of the non-enumerability of tex2html_wrap_inline50 (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 tex2html_wrap_inline58 (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 tex2html_wrap_inline66 , the following are strings:


And we will mean by tex2html_wrap_inline70 (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 tex2html_wrap_inline78 , then the following strings are elements of tex2html_wrap_inline70 :







tex2html_wrap_inline70 , needless to say, is always an infinite set (even when A has only one member). Recall that whenever you are given an alphabet tex2html_wrap_inline78 you can order tex2html_wrap_inline70 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 tex2html_wrap_inline124 ; and then consider tex2html_wrap_inline124 ordered lexicographically, a progression we'll denote by tex2html_wrap_inline128 .

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


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

does. And so do the following strings in tex2html_wrap_inline128 :

So let us subtract from tex2html_wrap_inline128 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 tex2html_wrap_inline140 . That is,


Very well. Now define a certain real number N with respect to tex2html_wrap_inline140 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 tex2html_wrap_inline140 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.

next up previous
Next: About this document

Selmer Bringsjord
Mon Dec 2 23:57:31 EST 1996