Transfinite Construction, an intuitive interpretation.

Question

Theorem (Transfinite Construction). Let $W$ be a well-ordered set, and $E$ an arbitrary class. Assume:
For each $x\in W$, there is a given rule $R_x$ that associates with each $\varphi\colon W(x)\to E$, a unique $R_x(\varphi)\in E$.
Then there is one, and only one, $F\colon W\to E$ such that $F(x)=R_x\big(F\mid W(x)\big)$ for each $x\in W$.

(I'm using Newman Bernaid Gödel [NBG])

I'm having trouble understanding this from an intuitive pov. Is there a way to visualice this theorem (much like one can visualice Transfinite Induction)? Any tips on understanding this are more than welcomed. Thanks.

Answer 1

I suppose by $W(x)$ you mean the initial segment determined by $x$ under the well-ordering, which is probably better denoted as $W_x$. In general $W$ can be a class with a well-founded and set-like relation, such as $(V,\in)$, the class of all sets with membership relation.

Transfinite recursion is closely related to transfinite induction. The prototype example is ordinal arithmetic. Below is the definition of ordinal addition.

1. $\alpha+0=\alpha$;
2. $\alpha+(\beta+1)=(\alpha+\beta)+1$;
3. $\alpha+\eta=\sup_{\beta<\eta}(\alpha+\beta)$, for limit ordinal $\eta$.

You can think of the first argument $\alpha$ as fixed and we are defining addition by induction on the second argument. 1 is the initial case, 2 is the successor case, and 3 specifies what to do in limit case. The value at $\beta+1$ only depends on the value at $\beta$, but the value at $\eta$ really utilizes all the values up to that point; this is similar to strong induction.

The process should be quite intuitive...But wait, what does definition even mean? A normal definition looks like this: define a number to be even if it is a multiple of $2$. In other words "even" is an abbreviation of "being a multiple of $2$". That's not what is happening here. Although we are introducing a new operation called ordinal addition, we are really saying that there exists an operation that satisfies our requirements 1, 2 and 3. It may seem obvious that such an operation exists, but nevertheless one needs to prove it.

Proposition: For any ordinal $\gamma$, there exists a map $f$ with domain $\gamma$ that takes values in ordinals and satisfies: (i) $f(0)=\alpha$; (ii) $f(\beta+1)=f(\beta)+1$; (iii) $f(\eta)=\sup_{\beta<\eta}f(\beta)$ for limit ordinal $\eta$.

Proof: First notice that if $f,g$ are two such maps then they must be the same. This is proved by transfinite induction: certainly $f(0)=g(0)$; if $f(\beta)=g(\beta)$ then by (ii), $f(\beta+1)=f(\beta)+1=g(\beta)+1=g(\beta+1)$; if $\eta$ is a limit and $f(\beta)=g(\beta)$ for all $\beta<\eta$, then by (iii) we have $f(\eta)=\sup_{\beta<\eta}f(\beta)=\sup_{\beta<\eta}g(\beta)=g(\eta)$; consequently $f=g$. Similarly if $f$ is such a map with domain $\gamma_1$, $g$ is such a map with domain $\gamma_2$ and $\gamma_1<\gamma_2$, then the restriction of $g$ to $\gamma_1$ must be the same as $f$.

Now we show that such a $f$ exists for every $\gamma$, again by transfinite induction. (a) For successor case, we assume $f_\gamma$ exists and want to find $f_{\gamma+1}$. According to our definition, the domain of $f_\gamma$ is $\gamma$, which does not contain $\gamma$; to find $f_{\gamma+1}$ we need to add $\gamma$ to the domain. If $\gamma=\beta+1$ is a successor, then just let $f_{\gamma+1}=f_\gamma\cup\{\langle\gamma,f_\gamma(\beta)+1\rangle\}$. If $\gamma$ is a limit ordinal, let $f_{\gamma+1}=f_\gamma\cup\{\langle\gamma,\sup_{\beta<\gamma}f_\gamma(\beta)\rangle\}$. (b) For limit case, we assume $f_\gamma$ exists for all $\gamma<\eta$, where $\eta$ is a limit ordinal. Because of the coherence property mentioned above, the union $\bigcup_{\gamma<\eta}f_\gamma$ is the desired map $f_\eta$. Here if it's ZFC then we are using the Axiom Schema of Replacement, which guarantees that $\{f_\gamma\mid\gamma<\eta\}$ is a set, so we can take its union; I'm not super sure how this is formulated in NBG. Together (a)+(b)+transfinite induction prove the existence of $f_\gamma$ for any $\gamma$.

In short, transfinite recursion is like usual recursion, except that the domain can be transfinite numbers (ordinals) or more generally some set or class equipped with a well-founded and set-like relation. Back to your notation, in the above example $W$ is $\text{Ord}$, the class of ordinals, $E$ is also $\text{Ord}$, $W_\gamma=\gamma$. $R_\gamma$ corresponds to (ii) and (iii), so $R_\gamma(\varphi)$ is $\varphi(\beta)+1$ if $\gamma=\beta+1$ is a successor and is $\sup_{\beta<\eta}\varphi(\beta)$ if $\gamma=\eta$ is a limit. Note that $R_\gamma(\varphi)$ needs to be applicable to all $\varphi$ for the proof to work, not just $f_\gamma$.