7
$\begingroup$

I learnt how Russell's paradox can be derived from Cantor's theorem here, but also from S C Kleene's Introduction to Metamathematics, page 38.

In his book, Kleene says that if $M$ is set of all sets, then $\mathcal P(M)=M$ but since this implies $\mathcal P(M)$ has same cardinality as $M$, so there exists a subset $T$ of $M$ which is not element of power set $\mathcal P(M)$. This $T$ is desired set for Russell's paradox, i.e., it is the set of all sets which are not members of themselves.

I can't understand how $T$ is desired set for Russell's paradox. Also, how is Kleene's argument similar to the quora answer?

$\endgroup$
  • $\begingroup$ Does Kleene really write "this ${\cal T}$ is desired set for Russell's paradox"? I would have expected his English to be much better than that. $\endgroup$ – Rob Arthan Jul 18 '16 at 21:57
10
$\begingroup$

Cantor's theorem shows that for any set $X$ and any function $f:X\to \mathcal{P}(X)$, there is some subset $T\subseteq X$ that is not in the image of $f$. Specifically, $T=\{x\in X:x\not\in f(x)\}$. Kleene is saying that if you apply this theorem to the identity function $f:M\to\mathcal{P}(M)$, the counterexample $T$ you get is exactly Russell's set. Indeed, this is immediate from the definition of $T$ given above. The Quora answer is just carrying out the diagonal proof that $T$ is not in the image of $f$ in this particular example.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I will be really obliged if you can answer me why $M\subset \mathcal P(M)$ when $M$ is set of all the sets. I asked this question here, but could not get satisfactory answer. $\endgroup$ – Silent Jul 17 '16 at 8:04
  • 4
    $\begingroup$ @Silent Let $x\in M$; you'd like to prove that $x\subset M$. If $y\in x$, then $y\in M$ (because everything belongs to $M$ by assumption); thus $x\subset M$ as required. $\endgroup$ – egreg Jul 17 '16 at 9:25
  • $\begingroup$ @egreg, thank you so much!! $\endgroup$ – Silent Jul 17 '16 at 10:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.