1
$\begingroup$

This is basically a two part question, as the title indicates. I understand why unrestricted comprehension will produce paradoxes like the Russell set, but I'm less clear on the question how the axiom of separation (or specification) solves this issue (and even whether it is able to solve it). Is the point that any set B defined in terms of having exactly those sets as members that are not members of themselves can never itself be a member of some arbitrary set A? In that case does this simply show that the Russell set is necessarily excluded from the things that one can meaningfully say about sets?

Any help on any aspect of this question would be appreciated!

$\endgroup$
3
$\begingroup$

See Russell's Paradox :

Zermelo replaces NC [Naïve Comprehension principle] with the following axiom schema of Separation (or Aussonderungsaxiom):

$$∀A ∃B ∀x (x \in B \iff (x \in A \land \varphi)).$$

Again, to avoid circularity, $B$ cannot be free in $\varphi$. This demands that in order to gain entry into $B$, $x$ must be a member of an existing set $A$. As one might imagine, this requires a host of additional set-existence axioms, none of which would be required if NC had held up.

How does Separation avoid Russell's paradox? One might think at first that it doesn't. After all, if we let $A$ be $V$ – the whole universe of sets – and $\varphi$ be $x ∉ x$, a contradiction again appears to arise. But in this case, all the contradiction shows is that $V$ is not a set. All the contradiction shows is that “$V$” is an empty name (i.e., that it has no reference, that $V$ does not exist), since the ontology of Zermelo's system consists solely of sets.


Consider a set $z$, we can still form the set $R = \{ x \in z : x \notin x \}$;

This only implies that :

if $R \in z$, then $R \in R \ \text { iff } \ R \notin R$, which means (reductio ad absurdum) that $R \notin z$.

Thus :

there is no universal set : $\forall z \exists R(R \notin z)$.


It can be worth to note that the "non-existence" of the Russell's set $R$ can be proved by logic alone :

1) $\exists y \forall x(A(x,y) \iff \lnot A(x,x))$ --- assumed [a]

2) $\forall x(A(x,c) \iff \lnot A(x,x))$ --- with $c$ a new constant

3) $A(c,c) \iff \lnot A(c,c)$ --- by instantiation.

The last line gives us a contradiction, because : $\vdash A(c,c) \iff A(c,c)$; thus, we conclude with :

$\vdash \lnot \exists y \forall x(A(x,y) \iff \lnot A(x,x))$ --- (*)

discharging the assumption [a].

Now, if we apply (*) to the language of set theory with the binary predicate $\in$ in place of $A$, we get :

$\lnot \exists y \forall x((x \in y) \iff (x \notin x))$.

$\endgroup$
0
$\begingroup$

The point with the formal axioms of set theory is that whenever we want to create a new set, we need to start from an old set. Russels paradox uses the "set" $$S=\{x: x\notin x\}$$ However $S$ does not take its elements from an already existing set, which is required by the Axiom of separation. Thus this does not need to be a set, as it was not constructed using our formal axioms. Note however that Gödels incompletenes theorem gives that we may never prove that Set theory is consistent and thus we are never be able to prove that $S$ is not a set (since set theory may be incosistent, but we cant prove this). However using the axiom of separation, none has found a contradiction so far.

$\endgroup$
0
$\begingroup$

I'd say that not only axiom schema of specification helps in fighting with paradoxes, but the whole axiomatization.

The existence of the set in Russel's paradox $R = \{x|x\not\in x\}$ cannot be proven via axioms of ZFC, roughly because it uses specification and the latter is restricted to subsets of other sets.

Furthermore, using axiom of regularity, we can show that in ZFC $\forall x : x \not\in x$, so $R$ must be the set of all sets, which is known not to exist in ZFC.

$\endgroup$
  • $\begingroup$ Dedekind,in an early book on set theory,gave a "proof" of the existence of an infinite set: The set $S$ of things I can think of cannot be $S=\{s_1,...,s_n\}$ because I can think of $S$ also. He admitted the error and removed this from later editions. $\endgroup$ – DanielWainfleet Nov 25 '15 at 16:46
  • $\begingroup$ @user254665 very interesting, thank you! :) Do you know of any sources of that fact? $\endgroup$ – lisyarus Nov 27 '15 at 17:14
  • $\begingroup$ It was in a small introductory book on set theory.Sorry I can't recall title or author. Note that $\{s|( $I can think of $s)\}$ is an instance of $NC$. $\endgroup$ – DanielWainfleet Nov 27 '15 at 17:21
0
$\begingroup$

The paradox arose from an early attempt to axiomatize set theory. Using this system, it was possible to both prove and disprove the existence of the Russell Set. You could prove its existence by using an axiom of unrestricted comprehension. You could disprove it by using only the rules of FOL. So, simply eliminating unrestricted comprehension alone would have "solved" the problem, but it would have left us with a severely crippled set theory.

The axiom of unrestricted comprehension was replaced by the much weaker axiom of restricted comprehension as well as additional, new axioms for power sets, pairwise unions, etc. to infer the existence of other sets as required.

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