Solutions to selected exercises for week 1

  1. Prove that if $S$ is a set of ordinals, then the union $\alpha = \bigcup S$ is an ordinal, and $\alpha$ is the least upper bound of $S$ in the sense of $\le$ (which was defined for ordinals as $\subset$.)

    Solution: I decided that it might be good to split this into some general lemmas that could be used later, although I wouldn't expect your solutions to do this. Note that in this solution, most of the hard work is done by your proof that the class of ordinals is transitive and well-ordered by $\in$ and it is not necessary to repeat this work.

    First lemma: If every element of the set $S$ is transitive, then $\bigcup S$ is transitive. Proof: Let $x$ and $y$ be such that $x \in y \in \bigcup S$. By the definition of union, we have $y \in z$ for some $z \in S$. Because $x \in y \in z$ and $z$ is transitive we have $x \in z$. Because $x \in z \in S$ we have $x \in \bigcup S$.

    Now because $S$ is a set of ordinals, every element of $\bigcup S$ is an element of an ordinal. Because the class of ordinals is transitive, this means that every element of $\bigcup S$ is itself an ordinal. Therefore the set $\alpha = \bigcup S$ is a transitive set of ordinals.

    Second lemma: If $\alpha$ is a transitive set of ordinals, then $\alpha$ is an ordinal. Proof: Because $\alpha$ is a transitive set, we only need to show that it is well-ordered by $\in$. This follows from the fact that it is a subset of the class of ordinals, which is well-ordered by $\in$.

    So now we know that the set $\alpha = \bigcup S$ is an ordinal. It remains to show that it is the least upper bound for $S$ in the sense of $\subset$. This follows from the next lemma.

    Third lemma: If $S$ is any set then $\bigcup S$ is the least upper bound of $S$ in the sense of $\subset$. Proof: This is straightforward. For all $y \in S$ we have $y \subset \bigcup S$ by the definition of union. Therefore $\bigcup S$ is an upper bound for $S$. On the other hand, suppose that $U$ is also an upper bound for $S$. For every $x \in \bigcup S$ we have $x \in y$ for some $y \in S$; because $U$ is an upper bound for $S$ we have $y \subset U$, so $x \in U$. Therefore $\bigcup S \subset U$, which shows that $\bigcup S$ is the least upper bound.