I'm reading a textbook from my country (Serbia) on mathematical logic and there's a part of the proof AC $\implies$ Zorn's lemma which I'm unclear on. Here's the part of the proof, up to and including the point I'm concerned with:
Let $(P, \leq)$ be a non-empty poset in which every chain has an upper bound. Assume, for the case of contradiction, that there is no maximal element. We construct a one-to-one function $F: Ord \to P $, which is a contradiction.
Let $f: \mathcal{P}(P)\setminus\{\emptyset\} \to P$ be the choice function for $\mathcal{P}(P)\setminus\{\emptyset\}$. We define $F(0)=f(P)$. Then, we define $F(s(\alpha)) (= F(\alpha \cup \{\alpha\}) ) = f(\{x \in P : x>F(\alpha)\}).$
All that's left is to define $F$ for limit ordinals $\lambda$. So let $\lambda$ be a limit ordinal and assume that $F$ is defined for all $\gamma < \lambda$. Now, this is where the trouble lies, in my opinion. First, the authors notice that $F[\lambda]$ is a chain, because it can be proven by induction in $\lambda$ that $\alpha < \beta \implies F(\alpha) < F(\beta)$. Then, since every chain in $P$ has an upper bound, the set $M$ of upper bounds of $F[\lambda]$ is non-empty, and so we define $F(\lambda)=f(M)$.
I've tried proving this induction (by $\beta$), but I'm confused; what if $\beta$ itself is a limit ordinal; how is it defined? How do we deal with it, which of the properties of $F(\beta)$ do we use? It says in one of the previous sentences that we assume that $F$ is defined for all $\gamma < \lambda$, therefore $\beta$ as well, but there is no conrete property to use for $F(\beta)$ to assert that if $(\forall \alpha \in \lambda) \alpha < \beta \implies F(\alpha) < F(\beta).$
Note that there is no definition or statement of the transfinite recursion theorem in the textbook; there are only several variants of transfinite induction (the three-case for $0$, successor and limit ordinals, one that's "inside" an arbitrary well-ordered set, the one I assume needs to be used here, and one that's analogous to the "inside a well-ordered set", but concerning all ordinals).
I'm looking for a confirmation if this is at all in fact an error in the proof or just an unclear explanation; if it's correct, but I'm just unable to prove the induction, I'd very much appreciate such a proof; if this is in fact a semantic "circle-jerk", I'd love to know if the argument can be corrected without changing the whole proof landscape too much, and if it can't, I'd appreciate a recommendation for a simple and elegant proof of this kind.
EDIT: I should've probably been more clear about which kinds of induction are listed and proven in the book:
- Let $X$ be a well-ordered set and $P$ a property which elements of $X$ can satisfy (or not satisfy, of course). If, for every $x \in X$, the following holds: $((\forall y<x) P(y)) \implies P(x)$ ($y \in X$, obviously), then $P(x)$ holds for all $x \in X$.
- Let $P$ be a property which ordinals can satisfy (or, again, not satisfy). If, for every ordinal $x$, we have: $((\forall y < x) P(y)) \implies P(x)$, then $P(x)$ holds for all ordinals $x$.
- Let $P$ Let $P$ be a property which ordinals can satisfy (or not). If $P(0)$ holds, along with: for all ordinals $\alpha$, $P(\alpha) \implies P(s(\alpha))$, where $s$ denotes the successor, and: if $\lambda$ is a limit ordinal and $P(\alpha)$ holds for all $\alpha < \lambda$, then $P(\lambda)$ also holds, then $P(\alpha)$ holds for all $\alpha$.
No, the proof is just fine.
When you prove that $F[\lambda]$ is a chain, then $F(\beta)$ already satisfies being an upper bound of $F[\beta]$, and therefore it is enough that $F[\beta]$ is a chain (as adding an upper bound to a chain preserves its property of being a chain). But of course, that is exactly the inductive hypothesis when $\beta$ is a limit ordinal.
Another way to look at this part is that what we prove is by induction up to $\lambda$, for every $\beta<\lambda$, by induction up to $\beta$, $F(\alpha)<F(\beta)$. Now if $\beta$ is a limit ordinal, then $F(\beta)$ is an upper bound of $F[\beta]$, since for all $\gamma<\beta$, the induction hypothesis of the first induction, states that $\alpha<\gamma$ implies $F(\alpha)<F(\gamma)$, and thus the proof is complete.