# defining a function recursively over the ordinals

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?

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.
• Ahh. That makes sense now that you tell me. Of course $\delta < \alpha$ and I can use $\{ \delta \in \alpha \vert \cdots \}$. Roitman starts the proof by defining $f(\beta)=p_0$. Does this get around the non-empty problem? Also, I'm not sure what you mean by "invoke the assumption that $P$ is inductive." – Robert Singleton Mar 1 at 15:55
• The set being nonempty is actually not a problem, you want this to happen! What you are trying to do is finding a maximal element of $P$. If at some point $\beta$, $f(\beta)$ is a maximal element, it is impossible to find $f(\beta+1)$! So if this set is empty, the hope is that you have come across a maximal element of $P$. If you have not, then the range of $f$ would be an increasing chain in $P$ without an upper bound, which contradicts the assumption of $P$ being inductive. – Andreas Lietz Mar 1 at 16:01
• Ok. That makes sense. BTW, I should have written $f(0)=p_0$ above. Thanks again. In fact, now that I think about it, I've been confused about this very point. I just didn't know how to articulate the question. – Robert Singleton Mar 1 at 16:05
• @AdreasLietz Does this mean that showing $f(\beta + 1)$ is empty is part of the proof/definition? Or does it follow trivially from choosing $\delta$ to be the least ordinal such that some condition is met (in this case $p_\delta > p$)? – Robert Singleton Mar 5 at 16:20