How does the axiom of regularity forbid self containing sets?

The axiom of regularity basically says that a set must be disjoint from at least one element. I have heard this disproves self containing sets. I see how it could prevent $A=\{A\}$, but it would seem to do nothing about $B=\{B,\emptyset\}$. It is disjoint from $\emptyset$. What is a disproof of the existence of $B$, and how is it related to the axiom of regularity?

• It says "a set is disjoint from all its elements OR from at least one of its elements". Your wording precludes existence of the empty set. – Vladimir Reshetnikov Mar 2 '16 at 3:47

Let $A$ be any set. Then $\{A\}$ is a set, and by regularity $\{A\}$ must contain an element disjoint from $\{A\}$. The only element of $\{A\}$ is $A$, so $A\cap\{A\}=\varnothing$, and it follows immediately that $A\notin A$.

• @PyRulez: I inadvertently dropped the braces: as I defined it, $A=\{B\}$, not $B$ as I wrote. It doesn’t matter for the important part of the answer, which shows how to derive $A\notin A$ for any $A$. – Brian M. Scott Jan 6 '13 at 14:44

No. The axiom of regularity says this: every non-empty set contains an element disjoint from it. So suppose there were a set $B$ such that $B = \{ B, \emptyset \}$; then the set $\{ B \}$ contains no element disjoint from $\{ B \}$: $$B \cap \{ B \} = \{ B \} \ne \emptyset$$ so there is no such set $B$.

• I've realized my method actually gets to the same answer; namely $\{B\}$. Sorry for being so absentminded. – user26486 Sep 3 '14 at 20:49
• However together with the axiom schema of separation this would mean that ${x\in B: x = B}$ would be a set containing only ${B}$ yet would not be disjoint to any of it's members. – skyking Sep 5 '15 at 11:58

The axiom of foundation or regularity alone can not show that there is no $x$ such that $x \in x$.

The axiom of regularity (also called the axiom of foundation) asserts that every set has a $\in$ minimal element. That is, for all $x$, there exists a $y \in x$ such that there are no $z \in x$ with $z \in y$.

The axiom of foundation is not exactly equivalent to the fact that there does not exists an $x$ such that $x \notin x$. There is a two element model of foundation (extensional, union, and pairing) such that there exists a $x$ with $x \in x$. Let $M = \{x,y\}$ where $x$ and $y$ two different objects. Define $\in^\mathcal{M} = \{(x,y), (y,y)\}$. You can verify foundation holds in this model $\mathcal{M}$, but $y \in y$.

Note that the axiom of comprehension and foundation can show that there is no $x$ such that $x \in x$

• This is not a model of pairing, for there is no set $\{y,y\} = \{y\}$. This set cannot exist in your purported model because if $y \in y$ then $\{y\}$ does not satisfy foundation. On a deeper level, inspecting the other answers it seems Extensionality, Foundation and Pairing suffice to rule out $x \in x$. – Lord_Farin Mar 6 '13 at 12:23
• @Lord_Farin I am using Kunen's definition of pairing ($\textit{Set Theory}$ page 16): $(\forall x)(\forall y)(\exists z)(x \in z \wedge y \in z)$. In the absence of comprehension, this is not equivalent to the existence of $\{x,y\}$. – William Mar 7 '13 at 9:19
• Ah, such explains everything. I'm used to the strict interpretation $\exists z: w \in z \iff (w = x \lor w = y)$ (cf. e.g. Jech's Set Theory, pp.6-7 ). Never mind, then. – Lord_Farin Mar 7 '13 at 10:44

Together with axiomschema of separation:

Assume that $A\in A$, then there's a set $B = \{x\in A: x=A\}$ which is non-empty since $A\in B$. Now for any $x\in B$ it's true that $x=A$, so $\forall x\in B: x\cap B = A\cap B$, but since $A\in A$ and $A \in B$ it would be that $A\cap B \ne \emptyset$. But that's equivalent to $\neg\exists x\in B: x\cap B = \emptyset$ which contradicts the axiom of regularity.

Therefore we can conclude $A\notin A$.

Here is a formal proof in Fitch: 