I'm filling in the gaps of the explanations of a logic textbook which has a very terse treatment of ordinals, so I was hoping someone could take a look at my proof of:
Proposition: Let $\alpha$ be an ordinal. Then $\alpha \neq \beta+1$ for all $\beta$ and $\alpha \neq \varnothing$ if and only if:
$$\alpha = \bigcup_{\beta < \alpha} \beta$$
Here is my proof:
Let $\alpha$ be an ordinal such that $\alpha \neq \beta + 1$ for all ordinals $\beta$ and $\alpha \neq \varnothing$. Proven in the textbook is that either $\alpha \in \beta$ or $\alpha = \beta$ for all ordinals, so it must be the case that for all $\beta + 1 < \alpha$, we have $\beta + 1 \in \alpha$. This is the same as $\beta \cup \{\beta\} \in \alpha$.
It follows that:
$$\bigcup_{\beta < \alpha} \beta \subseteq\bigcup_{\beta < \alpha} (\beta \cup \{\beta\}) \subseteq \alpha$$
since set membership holds for every $\beta < \alpha$. Now let $\gamma \in \alpha$, hence $\gamma < \alpha$; as $\gamma$ is a well-ordered set, it must be isomorphic to an initial segment (all elements less than) of $\{\beta, \{\beta\}\}$, proved in the textbook, hence $\gamma = \beta$ for a unique $\beta$ and $\alpha \subseteq \bigcup_{\beta < \alpha} \beta$.
For the other direction:
Let $\alpha$ be an ordinal such that $\alpha = \bigcup_{\beta < \alpha} \beta$. Assume for contradiction that $\alpha = \beta + 1$ for some $\beta < \alpha$. This must be the $\beta$ covered by $\alpha$, for if there was some $\beta < \beta + 1 < \alpha$, we would have $\alpha < \alpha$. Then:
$$\beta \cup \{\beta\} = \bigcup_{\beta < \alpha} \beta$$
Which implies that:
$$\{\beta\} = \bigcup_{\gamma < \beta} \gamma$$
However, the right-hand side, by the definition of an ordinal, is $\beta$ itself, so we have $\beta = \{\beta\}$, a contradiction.
$\square$
In particular, I am somewhat confused about how to show that if $\alpha$ may be written as a union, then it is not $\varnothing$. Can't we say that $\varnothing = \cup_{\beta < \varnothing} \beta$ trivially?
Best Answer
You're exactly right about $\varnothing$ -- it does satisfy $\varnothing = \bigcup_{\beta < \varnothing} \beta$, and $\varnothing$ is not a limit ordinal! I think the correct claim is:
or
These are equivalent, so I'll prove the first version. Before I do, some comments on your proof:
[Forwards Direction]
"Proven in the textbook is that either $\alpha \in \beta$ or $\alpha = \beta$" is a bad way to say this. It is not true that for all ordinals $\alpha$ and $\beta$, $\alpha \in \beta$ or $\alpha = \beta$. For example, let $\alpha = 1$ and $\beta = 0$. The correct statement is that $\alpha \in \beta$ OR $\alpha = \beta$ OR $\beta \in \alpha$. In other words, we have $\alpha < \beta$, or $\alpha = \beta$, or $\beta < \alpha$: the ordinals are totally ordered.
Did you mean to say that $\beta < \alpha \implies \beta + 1 \in \alpha$? What you said is also true, but less useful.
The fact that $\bigcup_{\beta < \alpha} \beta \subseteq \alpha$ is simpler than you make it out to be: this is just a union of subsets of $\alpha$ (ordinals are transitive sets, so $\beta < \alpha \implies \beta \in \alpha \implies \beta \subseteq \alpha$).
The rest of this part of the proof doesn't make sense to me. Notably, you never used the fact that $\alpha$ is not a successor ordinal! Also, it's unclear what $\beta$ is supposed to be. Instead, to show $\alpha \subseteq \bigcup_{\beta < \alpha} \beta$, we take an arbitrary $\gamma \in \alpha$ and note that $\gamma \in \gamma + 1$. Since $\alpha \neq \gamma + 1$, we have $\alpha < \gamma + 1$ or $\gamma + 1 < \alpha$. If $\alpha \in \gamma + 1 = \gamma \cup \{\gamma\}$, then $\alpha \in \gamma$ (but then $\gamma \in \alpha \in \gamma \implies \gamma \in \gamma$, contradiction!) or $\alpha = \gamma$ (but then $\gamma \in \gamma$, contradiction!). Thus, $\gamma + 1 < \alpha$, so $\gamma \in \gamma + 1 \subseteq \bigcup_{\beta < \alpha} \beta$.
[Reverse Direction]
What does "the $\beta$ covered by $\alpha$" mean? This is unclear, and (I think as a result) I don't understand the rest of that sentence.
The line $\beta \cup \{\beta\} = \bigcup_{\beta < \alpha} \beta$ is confusing because the $\beta$'s on the left- and right-hand sides mean different things. It would be better to write $\beta \cup \{\beta\} = \bigcup_{\gamma < \beta + 1} \gamma$, or something like that.
It's unclear how you're getting $\{\beta\} = \bigcup_{\gamma < \beta} \gamma$. I think the argument you're looking for should go something like "$\{\beta\} = (\beta \cup \{\beta\}) \setminus \beta = (\bigcup_{\gamma < \beta + 1} \gamma) \setminus \beta =$...", but you need to fill this in -- I don't see how to derive this at the moment.
The right-hand side is not equal to $\beta$ by definition -- I think you're thinking of the fact that $\beta = \{\gamma : \gamma < \beta\}$. The correct thing to say would be that the right-hand is equal to $\bigcup \beta$. The whole point of this exercise is that some ordinals are equal to their unions and some are not!
Ok, now here's a proof of the claim:
First, suppose $\alpha$ is a successor ordinal; let $\alpha = \beta + 1 = \beta \cup \{\beta\}$. Note that $\beta \in \alpha$. Now let $\gamma < \alpha$ be arbitrary. Then either $\gamma \in \beta$ or $\gamma = \beta$. Either way, we must have $\beta \notin \gamma$. Thus, $\beta \in \alpha \setminus \bigcup_{\gamma < \alpha} \gamma$, so $\alpha \neq \bigcup_{\gamma < \alpha} \gamma$.
Next, suppose $\alpha \neq \bigcup_{\gamma < \alpha} \gamma$. Clearly $\bigcup_{\gamma < \alpha} \gamma \subseteq \alpha$, so we can pick an element $\beta \in \alpha \setminus \bigcup_{\gamma < \alpha} \gamma$. Now let $\gamma < \alpha$ be arbitrary. Since $\beta \notin \gamma$, we have $\gamma = \beta$ or $\gamma \in \beta$. Either way, $\gamma \in \beta \cup \{\beta\} = \beta + 1$. Since $\gamma$ was arbitrary, $\alpha \subseteq \beta + 1$. Also, $\beta \in \alpha$ implies $\beta + 1 \subseteq \alpha$, so we conclude that $\alpha = \beta + 1$, and thus $\alpha$ is a successor ordinal.