# How can we show that there is no such a set?

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?

• a set cannot have its power set as an element. try proving this – Vignesh Manoharan Nov 9 '14 at 17:47
• @VigneshM How could I prve this? – 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..)

• 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... :/ – evinda Nov 9 '14 at 18:03
• Yes, you can replace $y$ by $B$. So $B \in B \leftrightarrow B \notin B$, which is absurd. – Henno Brandsma Nov 9 '14 at 18:08
• Henno But, why can we replace $y$ by $B$? Do we know that $B \in B$ ? – evinda Nov 9 '14 at 18:11
• 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. – Henno Brandsma Nov 9 '14 at 18:13
• 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. – 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.

• Hayden No, a set does not belong to itself.. Or am I wrong? – evinda Nov 9 '14 at 17:48
• So, knowing that a set is well-defined, does this mean that this set belongs to itself? – evinda Nov 9 '14 at 17:50
• @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?)? – Hayden Nov 9 '14 at 17:51
• 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.. :/ – evinda Nov 9 '14 at 17:53
• @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$. – 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.

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