[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,

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/20150809/df9bce9d/attachment.html>
```