2
$\begingroup$

Some time ago I asked why a given collection of objects could not be a set (something to do with abstract algebra). I got three answers, one was close to the Russell's paradox, two other explanations involved cardinality. But I am wondering if the answers involving cardinality are simply consequences of Russell's paradox?

The two statements I got was:

But the class of all sets of a given nonzero cardinality is not a set.

..

Since the class of sets equipotent to $K\setminus F$ and disjoint from $F$ is not a set, we're done.

I have two questions:

  1. Are these two statements equivalent?

  2. When proving these statements, do you use Russell's paradox, so in a sense the are equivalent to Russell's paradox? (Alternatively, does Russell's paradox imply them?)

$\endgroup$
3
$\begingroup$

Where are we proving things? This matters a lot, because different choices of axioms for set theory will give different answers. According to the standard set of axioms - ZFC - both statements are true; however, in (say) NF, another set of axioms, they are false! So to show (in some system) that these aren't sets, we need to use some specific axioms in addition to Russell's paradox.

In ZFC, we use the axioms replacement and separation. Take for example the class $C$ of sets of cardinality 1. Then I can define a map from $C$ to the universe of all sets, sending $\{x\}$ to $x$. If $C$ were a set, then by replacement the image of $m$ - that is, the whole universe - would be a set. But separation, together with the argument of Russell's paradox, implies that the whole universe cannot be a set.

(Actually, replacement implies separation, so we only needed replacement, but whatever.)


Let me address the (non-)role of Foundation/Regularity here, based on the comments below.

Foundation sounds very relevant to questions of this sort, since Russell's paradox deals with self-containing sets. In particular, in many set theories without foundation (e.g. NF), there is a set-of-all-sets. So it is tempting to guess that, without foundation, we can't disprove the existence of a set of all sets.

However, it turns out that foundation is really a red herring here. It is easy to prove that there is no universal set in ZF minus foundation, as follows:

  • Suppose a universal set $U$ existed.

  • By Separation, we get the set $R=\{x: x\in U, x\not\in x\}$. Note that all we need here is that "$x\not\in x$" is a formula in the language of set theory - it doesn't matter what sort of formula it is, the Separation scheme applies to all formulas.

  • Now the usual Russell argument goes through. If $R\in R$, then $R\not\in R$; this is immediate (and more generally shows that for any set $A$, the set $R_A=\{X: X\in A, X\not\in X\}$ is not an element of $A$, although it is a set by Separation). More substantively, we know by assumption that $R\in U$ (since our assumption was that everything is in $U$); so if $R\not\in R$, that means $R\in U$ and $R\not\in R$, so $R\in R$.

  • So we have a contradiction; and this means that our initial assumption - that a universal set exists - was incorrect.

Note that this is a proof inside the theory ZF minus Foundation. I'm not arguing "If there is a universal set, then ZF minus Foundation is inconsistent;" I'm saying "ZF minus Foundation proves that there is no universal set." This proof inside ZF minus Foundation is a proof by contradiction, but that's fine.

$\endgroup$
  • $\begingroup$ I would think using union would be preferable to replacement - since it generalizes to larger cardinality better. $\endgroup$ – Milo Brandt May 22 '15 at 2:09
  • $\begingroup$ I might be missing something obvious, but I don't see how to do this with union. We could also use Foundation, as Tim Carson does - if $C$ is the class of sets which are equinumerous with $X$, and $a\in X$ with $a\not=C$, then let $C'=\{C\}\cup(X-\{a\})$. Then $C'\in C$ but $C\in C'$. $\endgroup$ – Noah Schweber May 22 '15 at 2:11
  • 1
    $\begingroup$ @TimCarson "If I remove foundation from ZFC, I won't be able to prove that there is no set $U$ such that $\forall x, x\in U$." I'm sorry, but that's completely incorrect. Separation alone proves that such a $U$ can't exist: supposing such a $U$ existed, apply Separation to $U$ using the formula "$x\not\in x$" and we get the set $R=\{x\in U: x\not\in x\}$. But now we can easily argue that both $R\in R$ and $R\not\in R$, and this yields a contradiction; so our initial assumption, that $U$ existed, is false. Foundation really isn't relevant here, even though it sounds like it would be. $\endgroup$ – Noah Schweber Aug 14 '17 at 22:44
  • 2
    $\begingroup$ To summarize: while the existence of such a $U$ contradicts Foundation, Foundation is not needed to show that such a $U$ exists. ZF minus Foundation proves that no such $U$ exists purely by invoking Separation. As to "You are using "ZFC is consistent" in your proof," no I'm not: my claim is e.g. "ZFC proves that the class of singletons is not a set," and this is true via the argument I give. ZFC's consistency has nothing to do with it; I've provided a proof in ZFC of the desired statement, so the statement "ZFC proves ---" is true, regardless of whether ZFC is consistent. $\endgroup$ – Noah Schweber Aug 14 '17 at 22:48
  • 1
    $\begingroup$ Thanks, I don't know why I was so confident with that idea. Somehow I had it stuck in my head that the paradox only helped to guide us and not that it also gave us a path through proof by contradiction. Your explanation was really helpful. $\endgroup$ – Tim Carson Aug 15 '17 at 2:03

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.