Lesson 2

For the proof of the Well-Ordering Theorem, we need to generalize the notion of induction to transfinite induction.

The terms “induction” and “recursion” are often used interchangeably. For example, the definition of the factorial \(n! = 1 \cdot 2 \cdot 3 \cdot … \cdot n\) as a function \(f(n)\), where \(f(n) = n \cdot f(n - 1)\) for \(n > 0\) and \(f(0) = 1\), is referred to as both “inductive” and “recursive.” We shall endeavor to distinguish these notions as follows: when we are proving a statement first for \(n = 0\), then for \(n = 1, 2, …\), with each case relying on the preceding one, we shall call this induction. When, on the other hand, we are defining an object first for \(n = 0\), then for \(n = 1, 2, …\), with each new value defined in terms of the previous ones, we shall call this recursion. Our goal is to learn how to carry out inductive proofs and give recursive definitions not only for natural numbers, but also for other well-ordered sets.

How can this scheme be generalized to arbitrary well-ordered sets in place of the natural numbers? Let \(A\) be a well-ordered set. We wish to define a function \(f \colon A \to B\) recursively, where \(B\) is some set. Such a definition should relate the value \(f(x)\) at a given element \(x \in A\) to the values \(f(y)\) for all \(y < x\). In other words, a recursive definition specifies \(f(x)\) assuming the restriction of the function \(f\) to the initial segment \([0, x)\) is known.