[FOM] NBG, Subsets and Cantor's Theorem

[Thomas Forster]

Dear Paul,

The answer to your question is: yes.   You do indeed need some form of 
the axiom of separation.   This is shown by the fact that there are 
consistent set theories in which Cantor's theorem canot be proved: 
Church's 1976 system for one.  Such systems have weakened versions
of the separation scheme.

On Tue, 3 Apr 2007, Studtmann, Paul wrote:

> I have a question about the way in which one proves Cantor¹s Theorem that
> there is no one to one function from a set onto its power-set within NBG.  I
> should say that I am taking as my example of NBG the presentation that
> Mendelson gives in his Introduction to Mathematical Logic, third edition.
> My question is simply: is the axiom of subsets needed in order to prove
> Cantor¹s Theorem within NBG?
>  
> I will state briefly why I came to the thought that it might be, though I
> would not be at all surprised to learn that my mathematical reasoning has
> gone awry somewhere ­ it normally does.  I shall also try to keep the
> reasoning as informal as possible.
>  
> Any variable or constant that is in lower case refers to a set.
>  
> The axiom of subsets states that the intersection, I, of any class, X, and
> any set, y, is a set.
>  
> Suppose there is a 1-1 function, f, from the set, a, onto the power-set of
> a, P(a). Then, there exists a class, C, such that for all sets, y, y E C if
> and only if y E a and it is not the case that y E f(y), where 'E' is the
> membership relation. (By the comprehension schema)
> Now, on the assumption that C is in P(a), a contradiction eventually follows
> in the familiar way. But how does one prove that C is in P(a)?  Well, as far
> as I can tell, what one needs to do is prove that C is a subset of a.  This
> requires proving that (i) every member of C is in a, which follows easily
> from the defining condition of C; and (ii) C is a set.  Why does one have to
> prove that C is a set?  Because if C is not a set, then it could be the case
> that everything that is in it is in the set, a, even though C is not in the
> power-set of a ­ the power-set axiom in NBG says that every sub-set, x, of
> another set, y, is in the power-set of y, not that every sub-class, X, of
> another set, y, is in the power-set of y.  Now, with the axiom of subsets,
> the fact that C is a set follows easily from the facts that (i) the
> intersection of C and a is C, and (ii) a is a set. But without the axiom of
> subsets I do not see how one would derive the fact that C is a set.  And so
> that has led me to my present question.
>  
>  
> I would not be surprised to find out that I am making some kind of mistake
> here ­ my grasp on mathematical fact is flimsy at best.  But I would very
> much like to know the answer to the question.  So if anyone could either
> tell me the answer or cite some relevant source, I would be very much
> obliged.
> 
> 
> Paul Studtmann
> 
> 
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
> 

-- 
www.dpmms.cam.ac.uk/~tf;  Home phone +44-1223-704452. 
work: +44-1223-337981. Mobile in UK +44-7887-701-562