FOM: Boolos on Cantor's Theorem
Mark Steiner
marksa at vms.huji.ac.il
Mon Feb 12 11:31:59 EST 2001
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.
More information about the FOM
mailing list