[FOM] Cantor Lemma

[Alex Blum]

What does Kripke say?
Alex Blum

From: fom-bounces at cs.nyu.edu [mailto:fom-bounces at cs.nyu.edu] On Behalf Of Harry Deutsch
Sent: Sunday, August 09, 2015 10:21 PM
To: Foundations of Mathematics
Subject: [FOM] Cantor Lemma

The following seems to be a fact of set theory:  Let F be any function with domain A and range B, and define C to be { x in A: x is not in F(x)}.  Then C is not an element of B.  (If C is in B, then for some a in A,
F(a) = C and so a is in F(a) iff it's not, a contradiction.)

This simple lemma is based of course on a step in the standard proof of Cantor's theorem, which step, I note, obviously generalizes to hold for any function. Cantor's theorem is the special case where B is the power set of A and F is assumed to be onto.  A form of Russell's paradox follows by taking A and B to be the same and F the identity function.

Is this fact found in the textbooks, perhaps buried in an exercise?  I haven't been able to find it.  I ask because in "A Puzzle About Time and Thought" Kripke formulates a paradox using essentially the reasoning employed above, but giving a reason for thinking that for a certain choice of F, C would be an element of B.  But he doesn't mention this simple lemma, and in fact asserts that his reasoning is compatible with conventional set theory.  That doesn't appear to be so.  According to the lemma, set theory allows no such exceptions.  But then, after all, Kripke is presenting a paradox!

My question is just whether this lemma can be found in the textbooks or published elsewhere.

Regards,

Harry Deutsch
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20150810/692e03ab/attachment.html>