19
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Vladimir Reshetnikov Mar 2 '16 at 3:47
20
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Jan 6 '13 at 14:44
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I've realized my method actually gets to the same answer; namely $\{B\}$. Sorry for being so absentminded. $\endgroup$ – user26486 Sep 3 '14 at 20:49
  • $\begingroup$ 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. $\endgroup$ – skyking Sep 5 '15 at 11:58
4
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Lord_Farin Mar 6 '13 at 12:23
  • $\begingroup$ @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\}$. $\endgroup$ – William Mar 7 '13 at 9:19
  • $\begingroup$ 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. $\endgroup$ – Lord_Farin Mar 7 '13 at 10:44
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

Here is a formal proof in Fitch:

enter image description here

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