TheoremProved

Foundation forbids self-membership

Statement

For every set $x$ (assuming the Axiom of Foundation together with Pairing), $x \notin x$ : no set can be an element of itself.

Why is it true?

Self-membership is exactly the kind of self-reference that powers Russell's paradox; Foundation rules it out not by deriving a contradiction each time, but once and for all, as a structural rule on how sets can be built. This is what lets mathematicians safely define things by induction/recursion on the membership relation, and it is why the sets that appear throughout ordinary mathematics never contain themselves.

Proof sketch

Suppose, for contradiction, that some set $x$ satisfies $x \in x$ .

By the Axiom of Pairing, the set $\{x\}$ exists (pair $x$ with itself). This set is nonempty, since it contains $x$ .

Apply the Axiom of Foundation to the nonempty set $\{x\}$ : there must exist $y \in \{x\}$ with $\{x\} \cap y = \emptyset$ . But the only element of $\{x\}$ is $x$ itself, so $y = x$ , and the conclusion becomes $\{x\} \cap x = \emptyset$ .

Now recall the contradiction hypothesis $x \in x$ . Since $x \in \{x\}$ (by definition of the pair) and $x \in x$ (our assumption), the element $x$ belongs to both $\{x\}$ and $x$ , so $x \in \{x\} \cap x$ . This means $\{x\} \cap x$ is nonempty, directly contradicting $\{x\} \cap x = \emptyset$ obtained above.

This contradiction shows the assumption $x \in x$ is impossible for any set $x$ ; hence $x \notin x$ for every set $x$ , as claimed.

Topics that use this theorem

The ZFC axioms

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Thomas Jech (2003). Set Theory
Paul J. Cohen (1963). The Independence of the Continuum Hypothesis