Theorem. Let \(J\) and \(C\) be well-ordered sets; assume that there is no surjective function mapping a section of \(J\) onto \(C\) . Then there exists a unique function \(h \colon J \to C\) satisfying the equation
(*)
\[ h (x) = \text { smallest } [ C - h (S _ {x}) ] \]
for each \(x \in J\), where \(S_x\) is the section of \(J\) by \(x\) .
If \(h\) and \(k\) map sections of \(J\), or all of \(J\), into \(C\) and satisfy (*) for all \(x\) in their respective domains, show that \(h(x) = k(x)\) for all \(x\) in both domains.
If there exists a function \(h: S_{\alpha} \to C\) satisfying (*), show that there exists a function \(k \colon S_{\alpha} \cup \{\alpha\} \to C\) satisfying (*).
If \(K \subset J\) and for all \(\alpha \in K\) there exists a function \(h_{\alpha} \colon S_{\alpha} \to C\) satisfying (*), show that there exists a function
\[ k: \bigcup_ {\alpha \in K} S _ {\alpha} \longrightarrow C \]
satisfying (*).
Show by transfinite induction that for every \(\beta \in J\), there exists a function \(h_{\beta}: S_{\beta} \to C\) satisfying (*). [Hint: If \(\beta\) has an immediate predecessor \(\alpha\), then \(S_{\beta} = S_{\alpha} \cup \{\alpha\}\) . If not, \(S_{\beta}\) is the union of all \(S_{\alpha}\) with \(\alpha < \beta\) .]
Prove the theorem.
Solution
Let \(D_h,D_k\) be the respective domains. Suppose \(h\) and \(k\) disagree somewhere in \(D_h\cap D_k\), and let \(x\) be the smallest point of disagreement. For every \(y<x\) in the common domain, \(h(y)=k(y)\). Since the domains are sections (or all of \(J\)), this gives \[ h(S_x)=k(S_x). \] Therefore the recursion formula yields \[ h(x)=\min(C-h(S_x))=\min(C-k(S_x))=k(x), \] a contradiction. Thus the two partial solutions agree wherever both are defined.
Suppose \(h:S_\alpha\to C\) satisfies (). By hypothesis no section of \(J\) maps surjectively onto \(C\), so \(h(S_\alpha)\ne C\). Hence \[ c=\min(C-h(S_\alpha)) \] exists. Define \(k\) on \(S_\alpha\cup\{\alpha\}\) by \(k|_{S_\alpha}=h\) and \(k(\alpha)=c\). For \(x<\alpha\), the recursion formula is unchanged, and at \(\alpha\) it holds by definition. Thus \(k\) satisfies ().
For \(x\in\bigcup_{\alpha\in K}S_\alpha\), choose any \(\alpha\in K\) with \(x\in S_\alpha\) and set \[ k(x)=h_\alpha(x). \] Part (a) shows this value is independent of the choice of \(\alpha\), so \(k\) is well-defined. For a fixed \(x\), choose \(\alpha\in K\) with \(x<\alpha\). Then all of \(S_x\cup\{x\}\) lies in \(S_\alpha\), and \(k\) agrees there with \(h_\alpha\). Hence \(k\) satisfies () at \(x\). Therefore it satisfies () throughout its domain.
Let \(J_0\) be the set of all \(\beta\in J\) for which there exists \(h_\beta:S_\beta\to C\) satisfying (*). We show \(J_0\) is inductive.
Assume \(S_\beta\subset J_0\). If \(S_\beta=\varnothing\), the empty function works. If \(\beta\) has an immediate predecessor \(\alpha\), then \[ S_\beta=S_\alpha\cup\{\alpha\}, \] and part (b) extends \(h_\alpha\) to \(S_\beta\). If \(\beta\) has no immediate predecessor, then \[ S_\beta=\bigcup_{\alpha<\beta}S_\alpha, \] and part (c), applied to \(K=S_\beta\), glues the functions \(h_\alpha\) to a solution on \(S_\beta\). Thus \(\beta\in J_0\) in every case. By transfinite induction, \(J_0=J\).
- Part (d) gives a compatible partial solution on every section. If \(J\) has no largest element, part (c) with \(K=J\) glues them to a function \(h:J\to C\). If \(J\) has largest element \(\beta\), part (d) gives a solution on \(S_\beta\), and part (b) extends it to \(J=S_\beta\cup\{\beta\}\). Thus a global solution exists. Uniqueness follows from part (a).