[FOM] Cantor Lemma

[David Auerbach]

That lemma is in James Thomson's wonderful little paper "On Some
Paradoxes".

David Auerbach
Sent from my iPhone

On Aug 10, 2015, at 9:30 PM, Alex Blum <Alex.Blum at biu.ac.il> wrote:

What does Kripke say?

Alex Blum



*From:* fom-bounces at cs.nyu.edu [mailto:fom-bounces at cs.nyu.edu
<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

_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20150810/f1405689/attachment.html>