We want to prove that the set of all sets do not exist.

We suppose that the set of all sets, let $V$, exists. So, for each set $x, x \in V$. We define the type $\phi: \text{ a set does not belong to itself , so } x \notin x$.

From the axiom schema of specification, we conclude that there is the set $B=\{ x \in V: x \notin x \}$

$$\forall y(y \in B \leftrightarrow y \notin y)$$

How can we continue?

  • 1
    $\begingroup$ a set cannot have its power set as an element. try proving this $\endgroup$ – Vignesh Manoharan Nov 9 '14 at 17:47
  • $\begingroup$ @VigneshM How could I prve this? $\endgroup$ – evinda Nov 9 '14 at 17:51

$B \in B$ iff $B \notin B$ (this is how $B$ is defined: a set is in it, if it is not an element of itself. So $B \in B$ implies $B \notin B$, contradiction. So $B \notin B$. But then again: $ B \in B$ (as $B$ is a set, so in $V$ and it's not an element of itself..). Contradiction again. So both $B \in B$ and $B \notin B$ lead to contradictions....

So $V$ cannot have been a set (this is where the trouble started..)

  • $\begingroup$ Henno Brandsma Do we use the sentence $\forall y(y \in B \leftrightarrow y \notin B)$. If so, why can we replace $y$ with $B$?Do we know that $B \in B$? I am confused now... :/ $\endgroup$ – evinda Nov 9 '14 at 18:03
  • $\begingroup$ Yes, you can replace $y$ by $B$. So $B \in B \leftrightarrow B \notin B$, which is absurd. $\endgroup$ – Henno Brandsma Nov 9 '14 at 18:08
  • $\begingroup$ Henno But, why can we replace $y$ by $B$? Do we know that $B \in B$ ? $\endgroup$ – evinda Nov 9 '14 at 18:11
  • $\begingroup$ When we have $\forall y$ (which really means for all sets $y$, and we assume $B$ is a set), we can subsitute $y$ by $B$. If it's true for all sets $y$, it must be true for $B$ in particular. $\endgroup$ – Henno Brandsma Nov 9 '14 at 18:13
  • 1
    $\begingroup$ Yes, and this contradiction shows that $B$ is not a set. The $\forall y$ is implicitly $\forall y \in V$, so substituting $y = B$ is allowed by the assumption that $B$ is a set. $\endgroup$ – Henno Brandsma Nov 9 '14 at 18:19

The set $B$ is commonly used in Russell's Paradox. Now that $B$ exists, it is well-defined to ask if $B\in B$ or not. Derive a contradiction from this.

  • $\begingroup$ Hayden No, a set does not belong to itself.. Or am I wrong? $\endgroup$ – evinda Nov 9 '14 at 17:48
  • $\begingroup$ So, knowing that a set is well-defined, does this mean that this set belongs to itself? $\endgroup$ – evinda Nov 9 '14 at 17:50
  • $\begingroup$ @evinda If you're working in ZF, then yes, this follows from the Axiom of Regularity. But you don't really need this; if $B\notin B$, what does that imply (hint: how is $B$ defined?)? $\endgroup$ – Hayden Nov 9 '14 at 17:51
  • $\begingroup$ I am working in ZF, but we haven't done the axion of regulaity so far... I haven't understood what I have to do.. :/ $\endgroup$ – evinda Nov 9 '14 at 17:53
  • $\begingroup$ @evinda That's fine, you don't need the Axiom of Regularity for this. If $B\in B$, then _____. If $B\notin B$, then _____. Fill in those blanks using the definition of $B$. $\endgroup$ – Hayden Nov 9 '14 at 17:55

The argument that a set cannot be an element of itself is quite convincing, but it's not the real reason that the collection of all sets isn't a set.

Assume we do allow sets to be elements of themselves (the set of all sets would necessarily be such a set). Then look at the subset $R$ of the universe defined by $$ x\in R \leftrightarrow x\notin x $$ i.e. it contains all sets that do not contain themselves.

Here's a question: Do we have $R\in R$? This is known as Russel's paradox, and it was a decisive factor against naive set theory.

Edit A few more details: If the universe $V$ of all sets is a set, then in particular we have $V\in V$, so we have to allow sets to be elements of themselves.

Also, for any two sets $x,y$ we either have $\color{red}{x\in y}$ or we have $\color{blue}{x\notin y}$. Now, if we let $x=y=R$, which one is it?

It cannot be the first case, $\color{red}{R\in R}$ since if that's the case then by definition of $R$ we have $R\notin R$ and we have a contradiction.

Then it must be the case that $\color{blue}{R\notin R}$. But then, by construction of $R$, we must have $R\in R$. Which means that $R$ neither is nor isn't an element of itself. This is the paradoxical result that carries Bertrand Russell's name.

  • $\begingroup$ Arthur Could you explain it further to me? $\endgroup$ – evinda Nov 9 '14 at 18:05
  • $\begingroup$ @evinda I've added an explanation. $\endgroup$ – Arthur Nov 9 '14 at 18:24

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.