FOM: Cantor'sTheorem & Paradoxes & Continuum Hypothesis

[Neil Tennant]

On Mon, 12 Feb 2001, Kanovei wrote:

> > From: "Robert Tragesser" <rtragesser at hotmail.com>
> 
> >...the proof of Cantor's Theorem really
> >seems to be very much more intractably
> >dependent on tricks of logic and language
> 
> Hardly one can find *tricks* of anything 
> (especially in plural) in few lines of the 
> diagonal argument. 
> What Cantor's theorem is really dependent on is 
> the assumption that P(N) (the continuum) *already exists* 
> to the moment of writing the proof and, say, will not 
> gain new elements until the proof is finished. 

This is incorrect. Cantor's theorem does not depend on the assumption that
the power set of the continuum exists. In its general form, where in place
of the continuum one has an arbitrary set X, Cantor's theorem does not
depend on the existence of the power set of X.

The theorem can be stated in the following form:

	for every set X, there is no relation R such that
	(i) if xRy then x is in X and y is a subset of X;
	(ii) if xRy and xRz then y=z;
	(iii) if x is in X then for some y xRy;
	(iv) if y is a subset of X then for some x xRy;
	(v) if xRy and zRy then x=z.

(i) says R maps members of X to subsets of X.
(ii) says that R is a function, i.e. a many-one relation.
(iii) says that R is defined on all of X.
(iv) says that R is "onto" the subsets of X (but without
necessarily committing one to the existence of the power set of X).
(v) says that R is 1-1.

If the reader is puzzled by my parenthetical comment in (iv), note that
the theorem can be construed as a second-order statement,
whereby one is not (yet) committed to the existence of R as a set.
Without Replacement, there is no commitment to the existence of the range
of R as a set. (This range would of course be the power set of X, if it
existed.)

The proof of Cantor's theorem proceeds by letting X be any set, and
letting R be any relation satisfying conditions (i)-(v) above, and
pursuing the well-known contradiction. Taking the condition C(x) to be

	x is in X and x is not in the set y such that xRy,

one invokes only Separation to be assured of the existence of the set D
defined as

	{x in X | C(x) }.

The existence of this set D is of course contingent on the existence of X
itself, which is being assumed, anyway, for the purposes of reductio ad
absurdum.
Now invoke (iv) and (v) to get D's pre-image d under R, so that dRD.
Then ask whether d is in D, for the resulting contradiction. This last
piece of the argument uses only (i), (ii), (iii), and analytic principles
governing set-existence, set-membership and satisfaction of the defining
condition within a set-abstract.

The whole proof is constructive, and existentially very non-committal.