[FOM] FOM Cantor's argument

[Neil Tennant]

The quick answer to your concerns is that one can prove Cantor's Theorem:

"for every set X there is no many-one relation mapping X onto all subsets
of X"

in a form that does NOT presuppose or entail the existence of the power
set of X. 

To get the "onto" condition expressed without commitment to the power set,
simply write

   for every subset Y of X, there is a member x of X such that R(x,Y);

i.e.

(1)   for every Y if (for all z if z is in Y then z is in X) 
      then there is a member x of X such that R(x,Y)

The many-oneness of R is easy to express also:

(2)   for all x, for all Y, for all Z, if R(x,Y) and R(x,Z) then Y=Z. 

Cantor's Theorem is essentially a constructive reductio ad absurdum of (1)
and (2), schematic in R.

Since the theorem shows that there is no function from X onto all subsets
of X, it follows, a fortiori, that there is no 1-1 function from X onto
all subsets of X. Nowhere have we assumed the existence of the power set
of X. Nor do we need the power set in order to confer meaning on our
quantification over all subsets of X. The logical rules governing the
universal quantifier confer all the meaning that is required.

___________________________________________________________________
Neil W. Tennant
Professor of Philosophy and Adjunct Professor of Cognitive Science

http://www.cohums.ohio-state.edu/philo/people/tennant.html

Please send snail mail to:

		Department of Philosophy
		230 North Oval
		The Ohio State University
		Columbus, OH 43210

Work telephone 	(614)292-1591 
Private Fax 	(614)488-3197


On Mon, 10 Feb 2003, Giuseppina Ronzitti wrote:

> Neil Tennant wrote
> 
> 
> > There is an easy argument for Cantor's Theorem that is both constructive
> > and predicative. See
> >
> > http://www.cohums.ohio-state.edu/philo/people/Faculty/tennant.9/650_3.pdf
> >
> 
> In that 1-page paper you prove the statement:
> 
> (A) "For no set is there a function mapping its member onto all its
> subsets"
> 
> and claim that  "this proof does not require that one be able to form
> the power set of X".
> 
> I  understand the statement (A) only if  I am allowed to read it as:
> 
> "For no set is there a function mapping its member onto *the set* of all
> its subsets". So, i do not understand the claim. Which kind of thing is
> "all subsets" of something if not the power set of that something ?  The
> proof, it is claimed,  "shows the impossibility, for any set X, of a
> formula \phi(x,y) purporting to represent a function from the members of
> X to all subsets of X, i.e. a formula \phi(x,y) for which the following
> conditions would hold: " the conditions have the following form:
> 
> \forall x \forall y [...]
> 
> Now, it  means \forall x \in X and for all y \in Y, and this Y must be
> something. Which kind of thing if not P(X) ?
> 
> G. Ronzitti
> Genova, Italy,
> Europe
> 
> 
>