[FOM] Cantor Lemma

Harry Deutsch hdeutsch at ilstu.edu
Sun Aug 9 15:21:14 EDT 2015

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.


Harry Deutsch

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20150809/df9bce9d/attachment.html>

More information about the FOM mailing list