1
$\begingroup$

The question below has been taken from Fundamentals of Mathematics by Bernd Schroder. It's an interesting one and I'm not sure if my proof holds.

Prove that there cannot be a set of all sets. That is, prove that the axioms of set theory that we have introduced so far, together with the assumption that there is a set A that contains all existing sets as elements, leads to a contradiction.


My attempt:

Axiom of Existence:

There is a set.

Axiom of Belonging:

If x is an object and S is a set, then x $\epsilon$ S is a proposition.

Axiom of Specification:

If p(x) is a given open sentence about the elements of a set S, then there exists a set A = { x $\epsilon$ S | p(x) }.

So, we let A be a set that contains all sets. Let B be defined as follows:

B = { x $\epsilon$ A | (x $\not$$\epsilon$ x) }

By the Axiom of Specification, the above must be a set. However, through reasoning that is similar to that presented in Russell's Paradox, we can see that the B cannot be a set. That is a contradiction. Hence, the set A of all sets does not exist.

I was wondering if my reasoning above is correct or can be improved upon. Any comments that criticize every bit of it will be appreciated (I'm trying to learn Math, so that kind of criticism has to be acceptable)

$\endgroup$
  • $\begingroup$ Oh I’m so sorry, I am very stupid. $\endgroup$ – Abhijeet Vats Nov 29 '19 at 6:25
  • $\begingroup$ You repeated the Russel paradox. If the set theory that you are using distinguishes between between classes and sets, then you have shown that the set of all sets cannot be a set, that it is a class. $\endgroup$ – William Elliot Nov 29 '19 at 6:27
  • $\begingroup$ HUGE hint: Consider the Axiom of Regularity. $\endgroup$ – fleablood Nov 29 '19 at 6:38
  • $\begingroup$ There’s no such axiom listed in the book. That is, no such axiom listed before this question comes up as an exercise. I’m determined to use only the axioms that have been given. $\endgroup$ – Abhijeet Vats Nov 29 '19 at 6:39
  • $\begingroup$ Which axioms are you given. There is almost certainly an axiom that a set can not be a member of itself. $\endgroup$ – fleablood Nov 29 '19 at 6:40
1
$\begingroup$

You're right in copying Russell's paradox, as from the given axioms it seems to me the only way to derive a contradiction.

You also use what you call the "Axiom of belonging", which is a weird axiom, and usually not mentioned: the language of set theory is supposed to include the symbol $\in$, ensuring that $x \in S$ is a term that can be used in logical formulae.

Then suppose $A$ is the set of all sets, so $$\forall x: x \in A\tag{1}$$

Define indeed $$B=\{x \in A: \lnot(x \in x)\}\tag{2}$$

which is well defined, as $A$ is a set and $\lnot (x \in x)$ is a valid proposition.

By (1), we have $B \in A$. Now by (2): $B \in B$ iff $\lnot(B \in B)$ which is a logical contradiction as we cannot have a logical equivalence between a proposition and its negation (by simple propositional logic.., no axioms of set theory)

$\endgroup$
  • $\begingroup$ Ah, the 'Axiom of Belonging' and 'Axiom of Existence' are names that I have given to the axioms in the book. It sort of helps me remember them easily if they have an identifiable name attached to them.I'd be open to better suggestions, though. Also, didn't you make use of the Axiom of Specification by introducing the set B, which would've been illegal had we used Russell's assumptions? So, the proof does use propositional logic and the axioms (or an axiom, more appropriately). $\endgroup$ – Abhijeet Vats Nov 29 '19 at 10:58
  • 1
    $\begingroup$ @AbhijeetVats axiom of existence is a commonly used name. One often sees the existence of the empty set $\emptyset$ as the first axiom, but if we have a set $A$ we can use "Comprehension" (the more common term for Specification) to define $\emptyset = \{x \in A: \lnot (x=x)\}$, assuming, as is usual, that $=$ (and its 3 axioms) are part of the logical language too. Naming the axioms is commonly done. See the Wikipedia entry for ZFC. $\endgroup$ – Henno Brandsma Nov 29 '19 at 11:02
  • $\begingroup$ Yeap, the book that I'm using made use of the Axiom of Specification to prove the existence of the empty set. My proof is correct, though, right? Like, the presentation is obviously really bad but the argument is fine, right? $\endgroup$ – Abhijeet Vats Nov 29 '19 at 11:09
  • $\begingroup$ @AbhijeetVats Your $B$ is fine. You did not give a complete argument in your post, just "reasoning like Russell's paradox". You do have to make it explicit, certainly at this level. $\endgroup$ – Henno Brandsma Nov 29 '19 at 11:11
  • $\begingroup$ Ah yes, of course. Thank you so much! $\endgroup$ – Abhijeet Vats Nov 29 '19 at 11:12

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.