# [FOM] FOM Cantor's argument

Neil Tennant neilt at mercutio.cohums.ohio-state.edu
Tue Feb 11 16:21:27 EST 2003

On Tue, 11 Feb 2003, Giuseppina Ronzitti wrote:

> Neil Tennant wrote:
>
> > 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"
>
> I am sorry I am not able to understand  the use of the locution "there is no
> function from X onto *all subsets * of X". Onto *what* ? Would you write
> something like: f : X ---> *all subsets of X* ?

Here is how to express the condition that a given relation R is a function
from X onto all subsets of X. Let ySx mean that y is a subset of x. [This
is unpacked as (w)(w in y -> w in x), NOT as (y in P(x)).]

(z)(z in X -> (Ey)(ySX & Rzy))
[i.e. R is total on X, and takes subsets of X as values]
&
(x)(y)(z)((Rxy & Rxz) -> x=z)
[i.e. R is many-one]
&
(y)(ySX -> (Ex)(x in X & Rxy))
[i.e. every subset of X is the R-image of some member of X]

Note that the quantification

(y)(ySX -> ...y...)

is meaningful, with the intended restriction to subsets of X, without our
needing to assume the existence of P(X) as a set itself.

This is strictly analogous to maintaining that a numerical quantification

(n)(n is a natural number -> ...n...)

is meaningful, with the intended restriction to natural numbers, without
our needing to assume the existence of omega as a set itself.

There is really nothing more to be said. If you continue to insist on the
need for P(X) in order to understand universal quantifications over all
subsets of X, I can't cure you of that felt need. There is no twelve-step
program to be rid of P(X). There is no organization P(X)-ers Anon. There
are only the introduction and elimination rules for the universal
quantifier. Remember how superglue used to come in two tubes, whose
contents had to be mixed? Think of the intro and elim rules like that.
They will make the meaning stick. Come to think of it, you need to master
that meaning *before* feeling entitled to the existence of P(X).
Otherwise, how will you know what goes into P(X)?

Neil Tennant