# Are there sets $A$ and $B$ such that $A \in B$ and $B \in A$?

I think that the question is clear from the title:

Are there sets $A$ and $B$ such that $A \in B$ and $B \in A$?

My feeling is that the definition of any two such sets will be circular (we can't define $B$ till we define $A$ and we can't define $A$ till we define $B$), and hence will be excluded by some axiom.

On the other hand, I can't see an inherent contradiction, though I wouldn't be surprised if some form of Russell's paradox pops up, pushed behind one more set of braces.

• It's ruled out in standard Zermelo-Frankel set theory but is not inherently contradictory. – Cheerful Parsnip Feb 14 '14 at 8:19
• @GrumpyParsnip Is it ruled out axiomatically? If so, could you tell me by which axiom, since it wasn't clear to me? – Joe Tait Feb 14 '14 at 8:25
• Axiom of regularity – Jose Antonio Feb 14 '14 at 8:27
• – MJD Feb 14 '14 at 13:51

One of the Zermelo-Frankel axioms is the axiom of regularity.

The Axiom of Regularity. For every nonempty set $A$ there exists an $a\in A$ such that $a\cap A=\varnothing$.

One may use this axiom to answer your question in the negative.

Proposition. Let $A$ and $B$ be sets. Then $A\notin B$ or $B\notin A$.

Proof. Seeking a contradiction, suppose $A\in B$ and $B\in A$. Then $B\in A\cap\{A,B\}$ and $A\in B\cap\{A,B\}$. It follows that $A\cap\{A,B\}\neq\varnothing$ and $B\cap\{A,B\}\neq\varnothing$.

Now, the axiom of regularity ensures an $X\in\{A,B\}$ such that $X\cap\{A,B\}=\varnothing$. But this implies $A\cap\{A,B\}=\varnothing$ or $B\cap\{A,B\}=\varnothing$, a contradiction. Hence $A\notin B$ or $B\notin A$. $\Box$

• Ah, thank you. I clearly wasn't clever enough to move up one level of sets. Thank you. – Joe Tait Feb 14 '14 at 8:33

Isn't the answer rather boringly "No according to some set theories, yes according to others"?

If we conceive of the universe of sets "bottom up" -- we start with some urelements (or nothing at all if you are feeling really mean), form sets of those, then form sets of what we've got, then form sets of everything so far, keep on going ... -- then natural theories of this cumulative hierarchy will take the membership relation to be well-founded (so, in particular, there are no chains like $A \in B \in A$).

If we conceive of the universe of sets "top down" -- a set (as it were) has arrows out pointing to its members (if any), which have arrows out pointing to their members, and so on -- then we might countenance looping chains of arrows.

The first hierarchical picture goes with ZFC (including foundation/regularity), and the variant graph conception of sets goes with e.g. Azcel's non-well founded theories.