A few questions about “small” transitive sets.

I'm currently reading about ordinals, working on various exercises since I haven't formally studied the material before.

I'm looking at transitive sets. A set $z$ is said to be transitive if and only if $\forall y \in z [y \subset z]$. They also define

$$0 = \emptyset \quad \quad 1 = \{0\} = \{\emptyset\} \quad \quad 2 = \{0,1\} = \{\emptyset, \{\emptyset\}\}.$$

An exercise asks to show that every non-empty transitive set contains $0$, and that every non-singleton transitive set contains $1$, assuming the Axiom of Foundation. Showing the first part wasn't too bad, and I think I was able to show the second part using the first.

Then, it asks to show that $1$ is the only one-element transitive set, and $2$ is the only two-element transitive set. I'm having some difficulty showing this. Here's what I was able to come up with for $1$. As for $2$, I'm stuck.

My attempt

Suppose $x = \{y\}$ is a transitive set. Then, any arbitrary element $z \in y$ is also in $x$. However, the Foundation Axiom states

$$\exists y(y \in x) \rightarrow \exists y(y \in x \wedge \neg \exists z(z \in x \wedge z \in y),$$

and I interpreted this as saying that $\forall z(z \not \in y)$, which means that $y = \emptyset$, implying $x = {\emptyset} = 1$. $\square$

I would greatly appreciate any hints/help with this one.

Assume $\{a\}$ is transitive. As you have shown that $\emptyset\in\{a\}$, we immediately have $a=\emptyset$ and $\{a\}=1$.

Assume $\{a,b\}$ is transitive with $a\ne b$. As you have shown, $\emptyset$ is one of these, so assume wlog. $a=\emptyset$ and $b\ne\emptyset$. By transitivity, $b\subseteq \{\emptyset,b\}$. Using Foundation, we find $b\notin b$, hence $b=\emptyset$ (contradicting $b\ne a$) or as last option $b=\{\emptyset\}$. Hence $\{a,b\}=2$.

• Thank you for your response. I figured I was making the proof for $1$ a lot more involved. I understand most of your reasoning for the $2$ proof, but I'm not seeing how you were able to jump to the conclusion that $b = \{\emptyset\}$ Is it because $b \subset \{\emptyset, b\}$ and Foundation showed that $b \not \in b$, meaning that $b \neq \{b\}$ and $b = \{\emptyset\}$? – josh Sep 9 '13 at 17:51
• @josh: Since $b\notin b$, $b$ cannot be $\{b\}$ or $\{\varnothing,b\}$. The only other subsets of $\{\varnothing,b\}$ are $\varnothing$ and $\{\varnothing\}$, and the former has been ruled out, so $b$ must be $\{\varnothing\}=1$. – Brian M. Scott Sep 9 '13 at 19:17
• @BrianM.Scott: That makes perfect sense. Thank you! – josh Sep 9 '13 at 20:27
• @josh: You’re welcome! – Brian M. Scott Sep 9 '13 at 20:28

For $1$ just use the fact that every nonempty transitive set includes the empty set. For $2$ you can use that to conclude that if a transitive set had a nonempty and not a singleton member then it has at least three members. From there it's easy.

For one-element transitive sets:

If $x = \{ y \}$ is a one-element transitive set distinct from $1 = \{ \varnothing \}$, then $y \neq \varnothing$, and so there is some $z \in y$. By transitivity, $z \in x$, and since $z,y \in x$ and $| x | = 1$ we have $y = z$, but this then contradicts Foundation ($y = z \in y$).

The two-element case can be done via a similar analysis.

• Why do it by contradiction? It can be done directly. – Asaf Karagila Sep 9 '13 at 14:47
• @Asaf: Because reductio ad absurdum is how I roll. ;) – user642796 Sep 9 '13 at 14:50
• Proof. Assume by contradiction that this is not how you roll... ;-) – Asaf Karagila Sep 9 '13 at 15:35