In my first math class at a university a professor introduced us into set axioms in an informal way. Specifically he listed the following axioms:

1) There is a set.

2) Two sets are equal iff they contain equal elements.

3) if $A$ is a set and $p(x)$ is a set property (e.g. $x = x$), then $\{a \in A : p(a)\}$ is also a set.

4) if $A$ and $B$ are sets, then there is a set which contains only elements of $A$ and $B$.

5) if $\mathbb A$ a set, then $\{a | \exists A \in \mathbb A : a \in A\}$ is also a set.

6) For each set there is its power set.

The professor claimed that from those axioms alone the following follows: there is not set of all sets.

I am wondering why.

As I said, the introduction in the set theory was rather informal, so I would also need an informal answer (a formal one I probably would not be ably to comprehend).

My attempt

Assume there exists a set of all sets $A$, then $B = \{a \in A : a \notin a\}$ according to 5 is a set. Then neither $B \in B$ nor $B \notin B$ is true which is nonsense, so $A$ does not exist. I am using here the idea of Russell's paradox but I am not sure whether this qualifies as a proof.

  • 2
    $\begingroup$ That's essentially correct. In this axiomatic system, Russel's paradox essentially becomes a proof by contradiction that there is no universal set. $\endgroup$ – florence Mar 30 '17 at 16:31
  • 1
    $\begingroup$ "Neither $B \in B$ nor $B \notin B$" doesn't directly contradict given axioms. $\endgroup$ – Abstraction Mar 30 '17 at 16:37
  • $\begingroup$ The second sentence in your attempt should be "then $B\in B$ iff $B\not\in B$ which is nonsense ... It doesn't follow that $B\in B$ and $B\not\in B$ both are wrong. But you have that if $B\in B$ then $B\not\in B$ and the other way around. $\endgroup$ – martin.koeberl Mar 30 '17 at 16:43
  • $\begingroup$ @martin.koeberl Actually you have to prove that both $B \in B$ and $\neg(B \in B)$ would be theorems. Otherwise you're leaving option that neither is a theorem which is actually allowed. $\endgroup$ – Abstraction Mar 30 '17 at 16:48
  • 1
    $\begingroup$ Possible duplicate of Why is "the set of all sets" a paradox? $\endgroup$ – Rob Arthan Mar 30 '17 at 20:43

Your method is basically correct, but needs a few more details and corrections:

First, $B = \{a \in A : a \notin a\}$ is a set according to axiom 3, not 5.

Then, you need to explicitly specify that since $B$ is a set, and $A$ is the set of all sets, then $B \in A$

And then you need to derive the contradiction a little bit more carefully:

Suppose $B \in B$. Then it must be the case that $B \notin B$, since the only sets we put in $B$ are the sets that don't contain themselves. But this contradicts $B \in B$. Hence, it can't be that $B \in B$, and so $B \notin B$. But that means that $B$ ends up in $B$, so we also have $B \in B$. Contradiction!

  • $\begingroup$ I see the same problem as martin.koeberl stated in a comment to my question: the last paragraph in your answer (I had the same line of thoughts in my attempt) shows that we get a nonsense, but I do not see a contradiction to an axiom in there. That is the reason why I was not sure that my attempt was a real proof. $\endgroup$ – Sergey Zykov Mar 30 '17 at 17:45
  • 2
    $\begingroup$ @SergeyZykov The result does indeed not contradict a specific axiom ... it is a logical contradiction in and of itself. In (classical) logic we assume that statements cannot both be true and false. Of course, we could specify that as an axiom of classical logic, and now it would contradict that. But your instructor assumes that we are working in classical logic already, which is what we typically do as mathematicians. $\endgroup$ – Bram28 Mar 30 '17 at 17:50

One way to prove this (not necessarily the easiest). It can be proved that the power of a set A always has strictly greater cardinality than set A itself. $C( A) < C( P(A) )$ But since $A$ is a set which contains all sets it contains $P(A)$ ($P(A) \subset A$) This implies that $C( P(A) ) \leq C(A)$ This is a contradiction, so there is no set A which contains all sets.

  • $\begingroup$ "It can be proved". Quite a long shot, though, since you are yet to define what a function is (which involves a considerable number of cultural choices). $\endgroup$ – user228113 Mar 30 '17 at 16:43

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.