How to prove $\{t\} \notin t$

How to prove $\{t\} \notin t$ using the axiom of foundation (aka axiom of regularity):

$A = \emptyset \vee \exists x \in A \forall y \in x : y \not\in A$

-

1 Answer

If you are okay with Choice, the Axiom of Foundation implies that there can be no infinite descending chain of sets ordered by $\in$. You would have $t\in\{t\}\in t$, leading to such an infinite chain, and thus contradicting AF.

But you can do it directly. Let $t$ be a set, and suppose that $\{t\}\in t$. Let $$X = \{t,\{t\}\}.$$

Now, by Foundation there exists $x\in X$ such that $x\cap X=\emptyset$. So either $t\cap X=\emptyset$ or $\{t\}\cap X=\emptyset$. Now, $t\in \{t\}\cap X$, so the latter cannot hold. And since $\{t\}\in t$ and $\{t\}\in X$, then $\{t\}\in t\cap X\neq\emptyset$. So neither holds, hence $X$ contradicts Foundation.

-
As far as I know you don't need choice to prove that foundation implies that there doesn't exist an infinite descending $\in$-sequence. Choice is used to prove the converse. –  Apostolos Dec 18 '10 at 13:15
You need the Axiom of Union in order to form $\{t,\{t\}\}$. –  Justaskin_ Dec 13 '14 at 0:08