Lesson 4

Before applying this theorem to prove that, given two well-ordered sets, one of them is an initial segment of the other, we must first refine it slightly. We need to account for the situation where the recursive rule is not defined everywhere. For instance, consider defining a sequence of real numbers by the relation \(x_{n} = \tan x_{n-1}\) with the initial condition \(x_{0} = a\). For certain values of \(a\), the construction of the sequence may break down, since the tangent function is not defined for some arguments.

Theorem. Let the mapping \(F\), as discussed in the previous Theorem, be partial (that is, for some elements \(x\) and functions \(g \colon [0, x) \to B\), the value \(F(x, g)\) may be undefined). Then there exists a function \(f\) which satisfies one of the following:

• either it is defined on the entire set \(A\) and agrees with the recursive definition;


• or it is defined on some initial segment \([0, a)\) and agrees with the recursive definition on that segment, while at the point \(a\) the recursive rule is inapplicable (i.e., the mapping \(F\) is undefined).

Proof. Let us extend the set \(B\) by adding a special element \(\bot\) (denoting “undefined”), and modify the recursive rule accordingly: the new rule assigns the value \(\bot\) wherever the original rule was undefined. (If any of the values of the function on earlier arguments is already \(\bot\), the new recursive rule likewise returns \(\bot\).)

Applying the previous Theorem to the modified rule yields a function \(f'\). If this function never takes the value \(\bot\), then the first of the two possibilities stated in the theorem is realized (with \(f = f'\)). If, however, the function \(f'\) assumes the value \(\bot\) at some point, then it continues to do so at all greater points. Replacing the value \(\bot\) with “undefined” gives a function \(f\) derived from \(f'\). The domain of definition of \(f\) is an initial segment \([0, a)\), and the second case of the theorem is realized.◼