What's a "well founded definition"?

Question

Reading wikipedia:

Because the av are totally ordered, this is a well-founded definition.

What's a well-founded definition?

Answer 1

Saying that a definition is well-founded is a (somewhat annoying, in the context of transfinite recursion) way of saying that it works as implicitly promised: it actually defines some object.

The issue here is that the map $b$ is defined only on chains - so when we write "Let $x=b(Y)$," this doesn't make sense unless $Y$ is in fact a chain.

But in this case, our $Y$ is the set $\{a_v: v<w\}$, and - by induction - this set is linearly ordered, that is, is a chain. So it makes sense to apply $b$ here, and so the definition of $a_w$ in terms of the already-defined $a_v$s (for $v<w$) makes sense.

Answer 2

I've not heard the term "well-founded" used in this context myself, but I presume the phrase is meant to assert that the transfinite recursive definition is correctly formed, so that it really does define something.

The contexts where I have heard the term are all examples of a well-founded relation.

Answer 3

At that point of the proof, we have to pull ourselves out of the swamp with our bootstraps: What we have, is a function $b$ that takes linearly ordered subsets of $P$ and produces a upper bound. But we apply $b$ not to an a priori totally ordered subset; instead, we apply it to $\{\,a_w\mid w<v\,\}$. So in order for the transfinite recursion to work, we must know that it works. In principle, some error may lurk at this place: the argument might be circular. The fact that this is not the case (and which one readily acknowledges to hold) is what makes this definition well-founded.

We could be more formal: We define the class function $\tilde b$ by setting $\tilde b(x)=b(x)$ if $x$ is a linearly ordered subset of $P$, and $\tilde b(x)=\emptyset$ (or $\tilde b(x)=\{\text{horseradish}\}$, it doesn't matter) otherwise. Now we use transfinite recursion to define a class function $B$ on $\operatorname{Ord}$ with the property that $$\forall \alpha\in\operatorname{Ord}\colon B(\alpha)=\tilde b(\{\,B(\beta)\mid \beta<\alpha\,\})$$ (the existence and uniqueness of $B$ is the very essence of the principle of transfinite recursion, which itself is proven by transfinite induction). Now that we have $B$, we can prove by transfinite induction that for all $\alpha$ the set $\{\,B(\beta)\mid \beta<\alpha\,\}$ is a linearly ordered subset of $P$ (in particular, contains no horseradish instead). As a consequence, we did not need $\tilde b$ after all and only use $b$, as promised.

The statement "... is well-founded" simply summarizes the fact that the above formalization indeed helps us get rid of the apparent circularity.