Set is Not Element of Itself

From ProofWiki
Jump to navigation Jump to search



Theorem

There cannot exist a set which is an element of itself.

That is:

$\neg \exists a: a \in a$


Proof

Aiming for a contradiction, suppose $a$ is such a set.

Then $a \in a$ and $a \in \set a$.

$a \ne \O$ because the empty set has no elements by definition.


It is also seen that:

\(\ds a \cap \set a\) \(=\) \(\ds \set {x: x \in a \land x \in \set a}\) Definition of Set Intersection
\(\ds \) \(=\) \(\ds \set {x: x \in a \land x = a}\) Definition of Singleton
\(\ds \) \(=\) \(\ds a\)


By the Axiom of Foundation:

$a \cap \set a = \O$

Thus $a = \O$.

But it was previously established that $a \ne \O$.


From this contradiction it follows that there cannot exist such a set.

Hence the result.

$\blacksquare$


Axiom of Foundation

This theorem depends on the Axiom of Foundation.

Most mathematicians accept the Axiom of Foundation, but theories that reject it, or negate it, have found applications in Computer Science and Linguistics.