5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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\}$? $\endgroup$ – josh Sep 9 '13 at 17:51
  • 1
    $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Sep 9 '13 at 19:17
  • $\begingroup$ @BrianM.Scott: That makes perfect sense. Thank you! $\endgroup$ – josh Sep 9 '13 at 20:27
  • $\begingroup$ @josh: You’re welcome! $\endgroup$ – Brian M. Scott Sep 9 '13 at 20:28
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

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

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.