Exercise 8.1.3

Proof. Let $X=\left\{\alpha \in A\mid \alpha \text{ is an ordinal number}\right\}$. Then by Theorem 6.2.6e there is an ordinal $\alpha$ such that $\alpha \notin X$. It also has to be that $\alpha \notin A$ since, if it were, then $\alpha$ would be in $X$ since it is an ordinal number, which would be a contradiction. □

Proof. First, by Lemma 1, there is a $b\notin A$. Also, by the Axiom of Choice, there is a choice function $g$ on $𝒫\left(A\right)$. Now consider any $a\in A$. We then define a transfinite sequence $⟨a_{\alpha }\mid \alpha <h(A)⟩$ by transfinite recursion as follows. Set $a_0=a$. Then, having constructed the sequence $⟨a_{\xi }\mid \xi <\alpha ⟩$ for $0<\alpha <h(A)$, we define the set $A_{\alpha }=\left\{x\in A\mid a_{\xi }<x\text{ for all }\xi <\alpha \right\}$. We then set

We claim that there is an $\alpha <h(A)$ such that $a_{\alpha }=b$. To see this, suppose to the contrary that $a_{\alpha }\ne b$ for all $\alpha <h(A)$ so that it has to be that each $a_{\alpha }\in A$. Consider now any $\alpha <h(A)$ and $\beta <h(A)$ where $\alpha \ne \beta$. Without loss of generality we can assume that $\alpha <\beta$. Clearly then, by definition, we have that $a_{\beta }\in A_{\beta }$ so that $a_{\xi }<a_{\beta }$ for all $\xi <\beta$. But since $\alpha <\beta$, we have that $a_{\alpha }<a_{\beta }$ so that $a_{\alpha }\ne a_{\beta }$. Since $\alpha$ and $\beta$ were arbitrary, this shows that the sequence is an injective function from $h(A)$ to $A$. However, this would mean that $h(A)$ is equipotent to some subset of $A$, which contradicts the definition of the Hartogs number. Hence it has to be that $a_{\alpha }=b$ for some $\alpha <h(A)$.

So let $\lambda <h(A)$ be the least ordinal such that $a_{\lambda }=b$ and let $C=\left\{a_{\xi }\mid \xi <\lambda \right\}$. We claim that $C$ is a chain in $(A,\le )$. So consider any $a_{\alpha }$ and $a_{\beta }$ in $C$ so that $\alpha <\lambda$ and $\beta <\lambda$ Without loss of generality we can assume that $\alpha \le \beta$. If $\alpha =\beta$ then obviously $a_{\alpha }=a_{\beta }$ so that $a_a\le a_{\beta }$ clearly holds. If $\alpha <\beta$ then, by what was shown above, we have that $a_{\alpha }<a_{\beta }$ so that $a_{\alpha }\le a_{\beta }$ again holds. Hence, in every case, $a_{\alpha }$ and $a_{\beta }$ are comparable in $\le$, which shows that $C$ is a chain since $a_{\alpha }$ and $a_{\beta }$ were arbitrary.

Thus, since $C$ is a chain of $A$, it has an upper bound $c\in A$. We claim that $c$ is also a maximal element of $A$. To show this, suppose that there is an $x\in A$ such that $c<x$. Now consider any $\xi <\lambda$. Then, since $c$ is an upper bound of $C$, we have that $a_{\xi }\le c<x$ so that $a_{\xi }<x$ since orders are transitive. It then follows from the definition of $A_{\lambda }$ that $x\in A_{\lambda }$ so that $A_{\lambda }\ne \varnothing$. Also note that, by the definition of $\lambda$, we have that $a_{\xi }\ne b$ for any $\xi <\lambda$. Thus, by the recursive definition of the sequence, it follows that $a_{\lambda }=g(A_{\lambda })\ne b$, which contradicts the definition of $\lambda$ (as the least ordinal such that $a_{\lambda }=b$). So it has to be that there is no such element $x$, which shows that $c$ is in fact a maximal element of $A$.

Now, it has to be that $0\ne \lambda$ since $a_0=a\ne b=a_{\lambda }$. It then follows that $0<\lambda$ since $\lambda$ is an ordinal. Hence $a=a_0\in C$ by the definition of $C$. Then, since $c$ is an upper bound of $C$, we have that $c$ is a maximal element of $A$ where $a\le c$. Since $a$ was arbitrary this shows the desired result. □