# Russell's paradox with bounded comprehension

Consider the set $S = \{A, \varnothing\}$ and define $A = \{x \in S|x \not\in x\}$; this is the same as Russell's paradox except with bounded comprehension, ie $A\in A\iff A\not\in A$.

I think the problem lies in the fact that the composition of $S$ depends on $A$, but the composition of $A$ depends on $S$. My question is: what about the Axiom of Separation (or the other axioms) precludes this construction?

NB: I haven't studied set theory except for reading a little bit in some introductory books in my own time.

• Or consider the set $S=\{\emptyset\}$ and define $A=\{x\in S:x\in B\}$ and $B=\{x\in S:x\notin A\}$. – bof Jun 29 '14 at 6:07

Your definition is circular. You define $S$ using $A$, and you define $A$ using $S$.

And that's what precludes the definition in this case.

• For those looking for an axiom, try Regularity: en.wikipedia.org/wiki/… – Eric Towers Jun 29 '14 at 5:43
• Eric, I don't quite get your comment here. – Asaf Karagila Jun 29 '14 at 5:44
• Just expanding on your answer. I've noticed a tendency for set theory questioners to demand an axiomatic response. – Eric Towers Jun 29 '14 at 5:45
• This has little to do with axioms; this is about the fact that the definition is circular. And just because we can write something on paper doesn't mean it has any actual content. – Asaf Karagila Jun 29 '14 at 5:51
• There is the related question of what prevents a set from having its "local Russel class" as one of its members, which is a sensible question. And one that has been answered several times even in my short time on m.se. – Malice Vidrine Jun 29 '14 at 6:02

User wrote:

My question is: what about the Axiom of Separation (or the other axioms) precludes this construction?

It has nothing to do with any axioms of set theory (or circularity). This problem can be resolved with a purely logical argument.

Theorem

There do not exist sets $A$ and $S$ such that $A = \{x \in S|x \not\in x\}$ and $S = \{A, \varnothing\}$.

Proof

1. Suppose to the contrary that we do have sets $A$ and $S$ such that $\forall x:[x\in A \iff x \in S \land x\notin x]$ and $S = \{A, \varnothing\}$.

2. From (1), $A\in A \iff A\in S \land A\notin A$

3. From (1), $A\in S$

4. From (2) and (3), we can obtain the contradiction $A\in A$ and $A\notin A$

5. Therefore, $\neg \exists A,S: [\forall x:[x\in A \iff x \in S \land x\notin x]\land S = \{A, \varnothing\}]$

Note

Similarly, we can prove that there do not exist sets $A$ and $S$ such that $A = \{x \in S|x \not\in x\}$ and $A\in S$.

• This wasn't quite what I was asking; you see, equally so, we could just say that the normal Russell's paradox set doesn't exist, but (from what I gather) axiomatic set theory was a way to develop axioms such that any set which could be constructed from the axioms was a valid set (ie didn't produce any contradictions). I didn't know about the axiom of regularity, which makes my construction not a set. – thedoctar Jul 3 '14 at 6:50
• @thedoctar My point was that you don't necessarily need to cite any axioms of set theory to resolve this problem. Although you would have to change the notation, the above proof also works with '$\in$' as an arbitrary binary predicate in FOL. – Dan Christensen Jul 3 '14 at 15:51