2
$\begingroup$

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?

$\endgroup$
11
  • 1
    $\begingroup$ No, not really. $\endgroup$ – Andrés E. Caicedo Sep 29 '14 at 1:50
  • 2
    $\begingroup$ 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... $\endgroup$ – tomasz Sep 29 '14 at 2:08
  • $\begingroup$ 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. $\endgroup$ – Dan Christensen Sep 29 '14 at 2:35
  • $\begingroup$ @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? $\endgroup$ – AF3 Sep 29 '14 at 2:37
  • $\begingroup$ @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. $\endgroup$ – Dan Christensen Sep 29 '14 at 2:53
2
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ 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. $\endgroup$ – tomasz Sep 29 '14 at 2:14
  • $\begingroup$ 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. $\endgroup$ – AF3 Sep 29 '14 at 2:14
  • $\begingroup$ @AF3: what does that even mean? $\endgroup$ – tomasz Sep 29 '14 at 2:16
  • $\begingroup$ Editing: One Sec $\endgroup$ – AF3 Sep 29 '14 at 2:19
  • $\begingroup$ tomasz: Thanks for the answer. The reason I don't see why this has such a simple answer is because it seems like you still need to make sure that the "Russell Set" is still not a part of any larger set, though. If that was the case, then it seems that we would have the same contradiction. I certainly believe that I'm incorrect here, but I'm trying to figure out why. $\endgroup$ – AF3 Sep 29 '14 at 2:25
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ – AF3 Sep 29 '14 at 3:25
  • $\begingroup$ 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). $\endgroup$ – AF3 Sep 29 '14 at 3:28
  • $\begingroup$ $\{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.. $\endgroup$ – Lehs Sep 29 '14 at 3:28
0
$\begingroup$

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$.

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$ – AF3 Sep 29 '14 at 3:32
  • $\begingroup$ @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? $\endgroup$ – Dan Christensen Sep 29 '14 at 3:36
  • $\begingroup$ 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". $\endgroup$ – AF3 Sep 29 '14 at 3:38
  • 1
    $\begingroup$ @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. $\endgroup$ – Lehs Sep 29 '14 at 3:39
  • 1
    $\begingroup$ 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? $\endgroup$ – Dan Christensen Sep 29 '14 at 4:08
0
$\begingroup$

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.

$\endgroup$

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.