# Russell's paradox and axiom of separation

I don't quite understand how the axiom of separation resolves Russell's paradox in an entirely satisfactory way (without relying on other axioms).

I see that it removes the immediate contradiction that is produced by unrestricted comprehension, but it seems that we still need further axioms to guarantee that a well-formed set $S$ will never contain the set of all given elements (of $S$) which do not contain themselves.

Is that correct?

• No, not really. Sep 29, 2014 at 1:50
• Why was this question downvoted? It might not be the best formatted or put question ever, but surely it is a lot better than a lot of questions by new users we see here... Sep 29, 2014 at 2:08
• One approach I have found that may be useful is to not postulate a priori the existence of any actual sets in your set theory -- not the empty set and not some amorphous infinite set as in ZFC. In this way, you will not be able to prove the existence of any set, but you can prove that certain sets, e.g the Russell set do not exist. As Hurkyl pointed out, a set does not exist if postulating its existence leads to a contradiction. Sep 29, 2014 at 2:35
• @Dan: That's an insightful way to look at it. I like that, but I think I come to the same stumbling block when I want to introduce the Axiom of Separation. Can you explain why we know that there is no contradiction for the Russell Set, no matter the other axioms?
– AF3
Sep 29, 2014 at 2:37
• @af3 As I see it, there are just two kinds of axioms in any set theory: Those that postulate a prior that existence of certain sets, e.g. the empty set. And those that can be used to infer the existence of one or more sets assuming the existence of others, e.g. if $S$ is a set, then there exists another set, the so-called power set of $S$. If your axioms are only of the latter kind, you cannot actually prove the existence of any set -- not the Russell Set or any other. I'm no expert, but as far as I can tell, the latter kind of axiom is all you really need to develop most, if not all of math. Sep 29, 2014 at 2:53

The guarantee that such a set can't exist is already given by the argument of Russell's paradox: its existence leads to a contradiction therefore it can't exist.

The problem with unrestricted comprehension was that it guaranteed the set does exist, which causes a problem because of the conflicting guarantees.

• Well, that's not the complete answer. The complete answer is as Andres said in his comment: no, we don't need any other axioms. This is because of the inherent contradiction in the definition of the set in Russel's paradox. Sep 29, 2014 at 2:14
• Hurkyl: Your first sentence is certainly true, but it doesn't show that such a set will not exist within a given theory, it shows that it it will not exist within any theory that obeys the classical laws of thought.
– AF3
Sep 29, 2014 at 2:14
• @AF3: The argument of Russell's paradox is a proof that the Russell set doesn't exist (if it exists, then it is either a member of itself or it is not, and both cases lead to contradiction, therefore it doesn't exist); this is true even when applied to Cantor's set theory that has unrestricted comprehension. Despite that, it is indeed potentially possible that ZFC proves the Russell set exists; this happens if and only if ZFC is inconsistent. So far, we do not yet have any argument that shows ZFC is inconsistent.
– user14972
Sep 29, 2014 at 2:44
• You can prove it doesn't exist in Cantor's theory as well. It's inconsistent, so we expect to be able both to prove and disprove any claim. Anyways, in ZFC, you can prove that unless ZFC is inconsistent, ZFC cannot prove ZFC is consistent. So if you want an actual proof of consistency, you're going to have to suggest some other system in which such a proof is to be carried out.
– user14972
Sep 29, 2014 at 3:21
• In fact, I think (but am not really sure) there's an odd pseudoparadox here: I think that it is possible for ZFC to be consistent, yet for ZFC to be able to prove ZFC is inconsistent. (if I'm correct, this bears some relation to Skolem's paradox, and to nonstandard models and stuff)
– user14972
Sep 29, 2014 at 3:27

I don't think the axiom scheme of separation "resolves" Russell's paradox at all, but restricts the way of using predicates to determine sets.

The paradox is nothing but a proof that there is no one-to-one correspondence between predicates and classes: there are predicates that not defines a class. When writing sets as $\{x|p(x)\}$ that one-to-one correspondence is understood. Therefore axiomatic set theory is to show that sets exists and show rules how to create sets. If $A$ is a set, then the set $\{x\in A|p(x)\}$ never will cause any trouble, due to the theories.

• This is making more sense, but I still don't understand why the Russell Construction occurring as a subset does not cause problems. Is it because once you have this restriction, then when you consider the Russell Construction as a subset, you just end up with a "proof" by contradiction that the subset must actually be outside of your set, and therefore it does not exist inside your reference set? If that's the case, then why do we need the Axiom of Regularity?
– AF3
Sep 29, 2014 at 3:25
• I see where I'm getting it wrong (I think). We just have that if B is the set formed by taking all of elements of A who are not members of themselves, then B is not in A. There is no contradiction, it's just a proof (that B is not in A).
– AF3
Sep 29, 2014 at 3:28
• $\{x\in A|x\notin x\}$ is not a paradox at all, it is just an exclusion of all the $x\in A$ that belongs to itself, if that even is possible..
– Lehs
Sep 29, 2014 at 3:28

Axioms are used to show that under some circumstances, some sets exist.

Russell's paradox shows that not every definable collection can be a set. So we have to restrict what sort of definable collections we allow. The separation axiom schema essentially say that if $A$ is already a set, then every definable subcollection of $A$ is also a set.

If we repeat the Russell paradox over a set $A$ using Separation, then we don't get a contradiction. We get an interesting theorem:

For every set $A$ there is a set $B$ such that $B\notin A$.

• I actually just figured out the last part right before you wrote it. Let me just recap to make sure: We argue this theorem by the same reasoning as Russell's Paradox, but that doesn't mean that we have an inherent contradiction in our theory, because we're now safely insulated. In that way, the Axiom Schema of Separation does actually resolve that specific paradox.
– AF3
Sep 29, 2014 at 3:32
• @AF3 But you also need some way to be sure that it is impossible to construct the Russell Set using the axioms of ZFC. Perhaps Asaf can explain how this is accomplished? Sep 29, 2014 at 3:36
• I think you still have the Russell Set, it just doesn't produce a contradiction. Edit: I agree with Lehr. I was abusing the term "Russell Set".
– AF3
Sep 29, 2014 at 3:38
• @Dan Christensen: but there are no "Russell-sets", the paradox prove that. And if you mean the axiom of foundation, it doesn't show nothing of the kind, it just trying to avoid something that scares somebody.
– Lehs
Sep 29, 2014 at 3:39
• The ZFC Axiom of Separation replaced the axiom of unrestricted comprehension that allowed the construction of the Russell Set in naive set theory. It closed one door, but how can we be sure that it is not possible to prove the existence of the Russell Set by other means using the axioms of ZFC? Sep 29, 2014 at 4:08

You are correct.

Russell's Paradox exposed the inconsistency of a proposed formal set theory of his day. This so-called naive set theory allowed you to derive theorems of the form:

$\exists S: \forall a:[a \in S \iff P(a)]$ for any unary predicate $P$.

This was called the axiom schema of unrestricted comprehension.

For $P(a)\equiv a\notin a$, however, we could then prove to the contrary that:

$\neg\exists S:\forall a:[a\in S \iff a\notin a]$

The moral of the story: Just because you can "define" a set doesn't mean it actually exists. Some restrictions must apply.

These restrictions were described, at least in part, in the so-called axiom schema of restricted comprehension that replaced the above axiom:

$\forall X:\exists S: \forall a:[a \in S \iff a\in X \land P(a)]$ for any unary predicate $P$ where $S$ is not referred to in $P(a)$.

This eliminated the direct route to Russell's Paradox and plugged one hole in naive set theory. Various ways including effectively banning self-reference altogether (e.g. $x\in x$) were also introduced into set theory. This, it was hoped, would banish anything resembling Russell's Paradox for good.