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$
1
  • $\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, 2016 at 21:57

1 Answer 1

11
$\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.

$\endgroup$
3
  • $\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, 2016 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, 2016 at 9:25
  • $\begingroup$ @egreg, thank you so much!! $\endgroup$
    – Silent
    Jul 17, 2016 at 10:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .