0
$\begingroup$

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.

$\endgroup$
8
  • 3
    $\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, 2017 at 16:31
  • 1
    $\begingroup$ "Neither $B \in B$ nor $B \notin B$" doesn't directly contradict given axioms. $\endgroup$ Mar 30, 2017 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$ Mar 30, 2017 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$ Mar 30, 2017 at 16:48
  • 1
    $\begingroup$ Possible duplicate of Why is "the set of all sets" a paradox? $\endgroup$
    – Rob Arthan
    Mar 30, 2017 at 20:43

3 Answers 3

3
$\begingroup$

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!

$\endgroup$
2
  • $\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$
    – zesy
    Mar 30, 2017 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, 2017 at 17:50
0
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2017 at 16:43
-2
$\begingroup$

In a case such as this that may be controversial, a formal proof is called for. Here is my formal proof of the non-existence of a set of all sets (only 25 lines of proof + commentary in blue text). It makes use of a form of natural deduction. Unlike standard ZFC, I make use of a unary predicate Set. Set(x) means that x is a set.

In gray text, under each formal statement is given the rule of inference used to generate that statement plus optional pointers to previous statement(s).

(A plain-text version follows this proof.)

enter image description here enter image description here enter image description here enter image description here

Plain-text version:

Prove: ~EXIST(u):[Set(u) & ALL(a):[a in u <=> Set(a)]]

Suppose to the contrary that u is the set of all sets

1   Set(u) & ALL(a):[a in u <=> Set(a)]
    Premise

2   Set(u)
    Split, 1

3   ALL(a):[a in u <=> Set(a)]
    Split, 1

Apply the Subset Axiom

4   EXIST(sub):[Set(sub) & ALL(a):[a in sub <=> a in u & ~a in a]]
    Subset, 2

Define: x  (A subset of u, similar to Russell's Paradox)

5   Set(x) & ALL(a):[a in x <=> a in u & ~a in a]
    E Spec, 4

6   Set(x)
    Split, 5

7   ALL(a):[a in x <=> a in u & ~a in a]
    Split, 5

Apply the definition of x to itself 

8   x in x <=> x in u & ~x in x
    U Spec, 7

9   [x in x => x in u & ~x in x] & [x in u & ~x in x => x in x]
    Iff-And, 8

10  x in x => x in u & ~x in x
    Split, 9

11  x in u & ~x in x => x in x
    Split, 9

    Prove: ~x in x
    
    Suppose to the contrary...

    12  x in x
        Premise

    13  x in u & ~x in x
        Detach, 10, 12

    14  ~x in x
        Split, 13

    Obtain the contradiction...

    15  x in x & ~x in x
        Join, 12, 14

By contradiction...

As Required:

16  ~x in x
    Conclusion, 12

Apply the definition of u

17  x in u <=> Set(x)
    U Spec, 3

18  [x in u => Set(x)] & [Set(x) => x in u]
    Iff-And, 17

19  x in u => Set(x)
    Split, 18

20  Set(x) => x in u
    Split, 18

21  x in u
    Detach, 20, 6

22  x in u & ~x in x
    Join, 21, 16

23  x in x
    Detach, 11, 22

Obtain the contradiction...

24  x in x & ~x in x
    Join, 23, 16

By contradiction...

As Required:

25  ~EXIST(u):[Set(u) & ALL(a):[a in u <=> Set(a)]]
    Conclusion, 1
$\endgroup$

You must log in to answer this question.

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