First of all, I apologixe if there is already an equivalent question with a satisfying answer on the site, but I couldn't find any.

The axiom schema of specification goes roughly like this:

$$ \forall A \ \exists B \ \forall x ( x \in B \Leftrightarrow x \in A \land P(x) ). $$

This doesn't end up in Russell's paradox, but there's still something that confuses me; to show it, I'll go through a reasoning similar to that of Russell's paradox.

First, this is an axiom schema, and as far as I understand we aren't arbitrarily excluding the statement $P(x):x \not \in x$.

So in the schema there is one axiom going like this:

$$ \forall A \ \exists B \ \forall x ( x \in B \Leftrightarrow x \in A \land x \not\in x ). $$

For this to be true $\forall x$, it must be true, for example, for $x=B$:

$$ \forall A \ \exists B( B \in B \Leftrightarrow B \in A \land B \not\in B ). $$

If we try to assume $B \in B$, we immediately encounter an absurd, since the axiom infers $B\in B \Rightarrow B \in A \land B \not \in B$.

Therefore we infer $B \not \in B $, and at first we don't encounter any issue, because we don't know if $B \in A$ necessarily.

But doesn't this imply that if a set $B$ doesn't contain itself, we cannot find any set $A$ such that $B \in A$?

To put this in perspective, what confuses me is the fact that... most sets don't contain themselves.

For example, take an element of Von Neumann's Integers:

$$ 2 = \{ \emptyset, \{ \emptyset \} \} $$

which, as far as I can see, doesn't contain itself. But (as we do when defining the other integers) surely we can find a set that contains it!

Shouldn't this contradict the axiom of specification relative to $P(x):x \not \in x$? What am I missing? Where am I going wrong in my reasoning?

  • $\begingroup$ Your statement $x\notin x$ is implied by the axiom of foundation, not by specification. $\endgroup$ – Arthur Oct 23 '16 at 11:35
  • $\begingroup$ How do you jump to "we cannot find any set $A$ such that $B\in A?$ The set $A$ was given to start with, and the set $B$ was defined in terms of $A$, and it turns out that $B\notin A.$ What this proves is that, given a set $A,$ we can find a set $B$ such that $B\notin A.$ (Under normal circumstances, i.e. assuming the axiom of foundation, it will turn out that $B=A.$) $\endgroup$ – bof Oct 23 '16 at 11:40
  • $\begingroup$ The paradox, if you want to call it that, is that there is no universal set: no matter what set $A$ you take, you find a set $B$ which is not in $A.$ If your intuition tells you that there must be a universal set, you may consider this fact paradoxical. $\endgroup$ – bof Oct 23 '16 at 11:45
  • $\begingroup$ @bof You're right, my leap in logic was in not realizing how $B$ is dependent from $A$. In a way, I was thinking as if the statement was actually $ \forall A \ \forall B ( B \in B \Leftrightarrow B \in A \land B \not \in B) $, which doesn't make any sense. $\endgroup$ – EducatedGuest Oct 23 '16 at 12:38

In order for $x$ to be an element of $B$ it needs to satisfy two conditions:

  1. $x\notin x$, and
  2. $x\in A$.

If $B\notin A$, then it is not possible that $B\in B$ anyway. If $B\in B$, then we derive the usual contradiction, by concluding that $B\notin B$. And if $B\in A$ but $B\notin B$, then we also derive a contradiction. So we can only conclude that $B\notin A$, and so we're fine (and in particular, $B\notin B$).

So Russell's paradox is now transformed to the following theorem:

If $A$ is a set, then $\{x\in A\mid x\notin x\}\notin A$. In particular, $\mathcal P(A)\nsubseteq A$.


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.