FOM: Boolos on Cantor's Theorem

[Mark Steiner]

Since Cantor's Theorem is under discussion, I thought I would send along
an letter I received about Cantor's Theorem from the late George Boolos,
not long before his untimely death.  I'm not sure whether he ever
published this.

Mark Steiner

----------

 Date: Fri, 29 Dec 95 09:15:50
 From: boolos at MIT.EDU (George Boolos)
 To: Mark Steiner <MARKSA at vms.huji.ac.il>
 Subject: Popularization
 
 Dear Mark,
         I liked your popularization and enjoyed going through it. Thanks
 for sending it to me.  Must have a look at what I wrote.
         Of late I've been brooding about Cantor's theorem and related
 matters.  The following combination of ideas struck me as possibly new,
 although of course there is a lot of *very* old stuff in it (Burali-
 Forti, Zermelo's proof of well ordering). Does it at all ring a bell
 with you?
 Cheers,
 George
 
         pA is the power set of A. The usual proof of Cantor's theorem,
 that if g:A -> pA, then g is not onto, contains an (explicit) definition
 from g of a counterexample to the statement that g is onto. The
 counterexample given by the proof is, of course, {x: - x e gx}.
         There is a corollary that immediately follows from Cantor's
 theorem: if f maps pA to A, then f is not one-one. But neither the
 obvious derivation of the corollary from the theorem nor the direct
 proof in which one considers S = {x:EB(x = fB & -x e B)} contains a
 definition from f of a counterexample to the statement that f is
 one-one. Such a counterexample would be a pair C,D such that -C=D and fC
 = fD.
         In the direct proof, if y = fS, then y e S and so for some B, y
 = fB and -y e B. Thus not: S=B. But no definition of B is provided
 there.
         But consider: Let rx = {y:yrx & -y=x}, the initial segment of r
 determined by x. Call r good if r is a (reflexive) well ordering and for
 each x in the field of r, x = f(rx). Let R be the union of all good
 relations. R is itself good. Let C = the field of R, x = fC, and D = Rx.
 Then x e C (since R is the maximal good relation), - x e D, and so -C=D,
 but fC = fD. (The reasoning here is, or is reminiscent of, that of the
 Burali-Forti paradox.)
         So there *is* a proof that contains a definition of a
 counterexample.
         Finally, since C is a subset of S (above), we may after all
 define B as D.