Lesson 3

The next theorem formulates how to define a function recursively. Theorem. Let \(A\) be a well-ordered set. Let \(B\) be an arbitrary set. Suppose there exists a recursive rule, that is, a mapping \(F\), which assigns to each element \(x \in A\) and each function \(g \colon [0, x) \to B\) a certain element of the set \(B\). Then there exists a unique function \(f \colon A \to B\) such that \[f(x) = F(x, f|_{[0, x)})\] for all \(x \in A\). (Here, \(f|_{[0,x)}\) denotes the restriction of the function \(f\) to the initial segment \([0, x)\)—that is, we disregard all values of the function on elements greater than or equal to \(x\).)

Informally, one may argue as follows: the value of the function \(f\) at the minimal element is uniquely determined, since there are no previous values (the restriction \(f|_{[0,0)}\) is empty). At any later element, the value of \(f\) is also uniquely defined, since \(f\) has already been defined (more precisely, uniquely defined) at all preceding elements.

For the proof we need to recall that we already showed that if for a partially ordered set \(X\) every nonempty subset of \(X\) has a minimal element, then the set \(X\) satisfies the induction principle in the following form: if (for every \(x \in X\)) the truth of \(A(y)\) for all \(y < x\) implies the truth of \(A(x)\), then the property \(A(x)\) holds for all \(x\). Formally, this is written as: \[\forall x \left( \forall y\ ((y < x) \Rightarrow A(y)) \Rightarrow A(x) \right) \Rightarrow \forall x\ A(x).\]

Now we are ready to prove the recursion Theorem. Proof. Let us prove by induction the following statement for an arbitrary element \(a \in A\):

There exists a unique mapping \(f\) from the segment \([0, a]\) to \(B\) for which the recursive definition (equality with \(F\) applied to the restriction) holds at all \(x \in [0, a]\).

Thus, we aim to show that for each \(a \in A\) there exists a unique correct mapping from \([0, a]\) to \(B\). Assuming this holds for all \(c < a\) (that is, there exists a unique correct mapping \(f_{c} \colon [0, c] \to B\)), we must establish the existence and uniqueness of a correct mapping on \([0, a]\). (Correctness means that for every \(d \leq c\), the value \(f_{c}(d)\) agrees with the recursive rule.)

Suppose, for contradiction, that there exist two distinct such mappings, say \(f_{c_1}\) and \(f_{c_2}\), with \(c_{1} < c_{2}\). The mapping \(f_{c_2}\) is defined on the larger segment \([0, c_{2}]\). Its restriction to \([0, c_{1}]\) must agree with \(f_{c_1}\), since the restriction of a correct mapping is also correct (this is evident), and uniqueness was assumed on \([0, c_{1}]\). Thus, all the mappings \(f_{c}\) are consistent with one another, meaning that if two are defined on overlapping domains, they assign the same values.

By taking their union, we obtain a single mapping \(h\) defined on \([0, a)\). Applying the rule \(F\) to \(a\) and \(h\), we get some value \(b \in B\). Extending \(h\) to the point \(a\) by setting \(h(a) = b\), we obtain a mapping \(h \colon [0, a] \to B\), which is easily seen to be correct.

To complete the inductive step, it remains to verify uniqueness on \([0, a]\). Indeed, any function defined on \([0, a]\) must coincide with \(f_{c}\) on \([0, c]\) for each \(c < a\), and thus agrees with \(h\). Therefore, the only point requiring verification is the value at \(a\), which is determined via the recursive rule from preceding values. This completes the inductive proof.

It remains to observe that the correct mappings on different segments \([0, a]\) are compatible with each other (the restriction of a correct mapping to a smaller segment is correct, and uniqueness applies), and therefore together define a function \(f \colon A \to B\) satisfying the recursive definition. Existence is thus proved; uniqueness is also clear, since the restriction of the function to any segment \([0, a]\) is correct and therefore uniquely determined, as we have shown.◼