23
$\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$
1
  • $\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$ Mar 2, 2016 at 3:47

5 Answers 5

25
$\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$
0
11
$\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$
2
  • $\begingroup$ I've realized my method actually gets to the same answer; namely $\{B\}$. Sorry for being so absentminded. $\endgroup$
    – user26486
    Sep 3, 2014 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, 2015 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$
3
  • $\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, 2013 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, 2013 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, 2013 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.