I'm reading Introduction to Modern Set Theory by Judith Roitman, and I'm having some trouble with the section on the axiom of choice. In particular, I'm confused about a step in the proof that Well Ordering implies Zorn's Lemma. I think my problem boils down to not understand how to define functions recursively over the ordinals. Rather than repeat the proof, I'll just start with my confusion.
The setup: We have a partial order $P$ and by Well Ordering we have written $P$ as a sequence of elements indexed by ordinals, $P = \{ p_\beta \vert \beta < \alpha \}$ for some ordinal $\alpha$. We wish to define a function $f(\beta)$. We suppose we know the function for $\gamma < \beta$, which is the same as saying we know the image $f[\beta]$ since $\gamma \in \beta$ when $\gamma < \beta$. We then want to define $f(\beta)$.
The question: Roitman defines $f(\beta) = p_\delta$ where $\delta$ is the least ordinal such that $p_\delta > p$ for all $p \in f[\beta]$. How do we know that such a $\delta$ exists?
My approach: Form the collection $\{\delta \vert p_\delta > p \forall p \in f[\beta] \}$. If this is a set of ordinals, then we can take the minimum. But, how we do know this is a set? I can't use separation because I am not taking the $\delta$ from another set, i.e. I don't have $\{\delta \in \alpha \vert \cdots \}$. Or does the construction go through even if $\{\delta \vert \cdots \}$ is a class and not a set?
Thanks for any help you can provide.
You can use seperation in exactly the way you suggested! Notice that $p_\delta$ is only defined for $\delta<\alpha$ and hence $$\{\delta\mid \forall p\in f[\beta]\ p_\delta>p\}=\{\delta\in\alpha\mid \forall p\in f[\beta]\ p_\delta>p\}$$ is a set. In any case, it is not necessary for this particular construction that this is a set, as you have a canonical way of choosing an element, namely taking the minimum. To take the minimum however, this set must not be empty. At some point, all possible $\delta$ will be exhausted, so eventually this set is empty for some $\beta$ and you cannot prolong this construction. In that case, you have to invoke the asumption of $P$ being inductive to complete the proof.